There were total 4 rounds
- Machine coding
- Design Round
- Hiring manager Round
Machine Coding Round: Need to implement the multilevel cache design.
Each level will store Key-Value pairs of data. Both KEY and VALUE are of type String. L1 is the top most level and Ln is the last level.
You are given the following configuration and details about the system:
Max number of levels of cache. The system starts with only 1 level initially and grows to a max number of levels as per the config.
The capacity of each level, i.e. number of elements that can be stored. The size is fixed for every level, although each level could have a different capacity.
This Cache system should be able to perform following operations:
- READ KEY Operation
Read will start from L1 level. If KEY is found at this level, then this value will be returned. If KEY is not found at this level, then try to read from the next level. Keep doing this until the value of KEY is found at some level or the last level has been reached. If the value of KEY is found at some level, then this VALUE should also be written into the first level and the expected write behavior should follow as specified in the next section.
- WRITE KEY Operation
Writes will start from level L1. If a level is full, evict any key-value pair from this level and write the evicted k-v pair into the next level. If the next level is also full, evict any k-v pair from that level and insert in the next level and so on. If you reach the last level, add a new level and insert the evicted K-V pair in this new level.
- DELETE KEY operation
Deletes the given key from all the levels the key is present in.
Eviction Strategy: We need the strategy to be pluggable. For this problem, implement LFU (Least Frequently Used) i.e remove the key which has been used least frequently.
You will be evaluated based on
DS Algo Round: There were 2 problems it was conducted by interview vector:
- Variation of prefix sum. Given user and multiple logtime need to find user with max log time in last 1 hour
Design Round: Design flight aggregator system. Aggregator will get data from different airlines and user will be able to search and book flight from aggregator. Interviewee expecting the high level design. How the data will be fetched from airlines regarding the flights and how it will be stored in our database. Segregate the system in different microservices. As the traffic on search api is high so how it will be handled. Need to show connecting flight as well if no direct flight is available. How to handle booking of different airlines and api failures and all.
I told interviewee that we can use mysql for this application as it support ACID and our usecase are also satisfied. For searching we can use multiple slaves but he asked if traffic increases then how it will be handled as spawning a new slave and replicating the data will take time, which i could not answer. And that was end of my interview journey