Flipkart Interview Experience | 2years Experience | SDE1
(Offsite Hiring Drive)
Machine Round (90mins coding + 30mins review)
Design and implement a Multiple Level Cache Management System with N levels, say:
L1 -> L2 -> L3 … -> LN. Each layer will store Key-Value pairs of data. Both KEY and VALUE are of type String. L1 is the top most layer with most priority. LN is the last layer with least priority. You can choose any replacement policy for the cache. You are given following details about the system:
1. The number of levels of cache.
2. The capacity of each layer, i.e. number of elements that can be stored.
3. Read time of each layer.
4. Write time of each layer.
This Cache system should be able to perform following operations:
1. READ KEY Operation
Read will start from L1 level. If KEY is found at this layer then this value will be returned. If KEY is not found at this layer then try to read from next layer. Keep doing this until the value of KEY is found at any level or the last level has been reached. If the value of KEY is found at any level, then this VALUE should also be written into all previous levels of cache which have higher priority than this level. Total Read time is the sum of Read time of all levels where READ operation was attempted and Write time of all levels where WRITE operation was attempted. You have to print the VALUE of KEY and total time taken to read it.
2. WRITE KEY Operation
Write will start from L1 level. Write the value of KEY at this level and all levels below it. If at any level value of KEY is same as given VALUE then don’t write again and return. Total Write time is the sum of WRITE time of all levels where WRITE operation was attempted and Read time of levels where READ operation was attempted. You have to print total time taken to write this KEY-VALUE information.
3. STAT Operation ( Bonus point / Optional )
Stat operations prints three information:
a) What is the current usage of each level of cache, i.e. Filled / Total size
b) What is the average read time of this Multi-Level Cache System for last 10 READ operation?
c) What is the average write time of this Multi-Level Cache System for last 10 WRITE operation?
Implementing Bonus part is optional but candidates who implement this part would be rated higher.
The duration of the complete exercise is roughly 2 hours. Of this, 90 mins are available to you for designing and implementing your solution. At the end of this time, your evaluator sits with you 1-on-1 and sees a demo of your code, and evaluates it on certain criteria.
Below are few points you need to keep in mind during your design and implementation.
1. Since we want to have a demo, it has to be running code. Appears fairly implicit, but it’s actually very important and unique criterion to Flipkart.
2. What it means for you is: you may know of excellent data-structures or the most optimal and fitting algorithm to the given problem statement, but you need to ask yourself whether you can implement it within the duration of 90 mins? If the answer is not close to yes, you may need to reconsider and maybe choose a sub-optimal but simpler-to-implement data-structures/algorithm. Of course, you would always have the chance to explain this choice later in your evaluation.
3. If you can get it implemented and running in the given time, a more optimal and fitting solution will obviously have more credit.
4. Your code needs to display maturity in various senses: modularity, extensibility, Separation of Concerns(SoC), good and consistent naming-conventions, validation and exception handling, comprehensive of test-cases covering corner cases, and other coding best practices that you may be aware of and follow. So, put related functionality in classes or methods, don’t have unrelated things muddled together in a class, make interfaces or base classes wherever you see generic behavior that can be abstracted out, etc.
Essentially, just 3 things: running code, optimality and maturity.
I solved this problem using LRU Policy. I solved Bonus part partially. Here’s input/output from my code: ( I have also printed all elements of cache for better understanding )
3
2 5 10
1 3 9
5 10 15
WRITE abc apple
WRITE def ball
READ abc
WRITE ghi cat
WRITE jkl dog
WRITE mno elephant
WRITE pqr fish
READ jkl
WRITE abc apple
STATS
Sample Output:
Write time: 43
abc: apple,
abc: apple,
abc: apple,
Write time: 43
def: ball, abc: apple,
def: ball, abc: apple,
def: ball, abc: apple,
Value at abc is apple
Read time: 1
abc: apple, def: ball,
def: ball, abc: apple,
def: ball, abc: apple,
Write time: 43
ghi: cat, abc: apple,
ghi: cat, def: ball, abc: apple,
ghi: cat, def: ball, abc: apple,
Write time: 43
jkl: dog, ghi: cat,
jkl: dog, ghi: cat, def: ball, abc: apple,
jkl: dog, ghi: cat, def: ball, abc: apple,
Write time: 43
mno: elephant, jkl: dog,
mno: elephant, jkl: dog, ghi: cat, def: ball, abc: apple,
mno: elephant, jkl: dog, ghi: cat, def: ball, abc: apple,
Write time: 43
pqr: fish, mno: elephant,
pqr: fish, mno: elephant, jkl: dog, ghi: cat, def: ball,
pqr: fish, mno: elephant, jkl: dog, ghi: cat, def: ball, abc: apple,
Value at jkl is dog
Read time: 9
jkl: dog, pqr: fish,
jkl: dog, pqr: fish, mno: elephant, ghi: cat, def: ball,
pqr: fish, mno: elephant, jkl: dog, ghi: cat, def: ball, abc: apple,
Write time: 28
abc: apple, jkl: dog,
abc: apple, jkl: dog, pqr: fish, mno: elephant, ghi: cat,
abc: apple, pqr: fish, mno: elephant, jkl: dog, ghi: cat, def: ball,
Usage: 2 / 2, 5 / 5, 6 / 10,
abc: apple, jkl: dog,
abc: apple, jkl: dog, pqr: fish, mno: elephant, ghi: cat,
abc: apple, pqr: fish, mno: elephant, jkl: dog, ghi: cat, def: ball,
Questions asked during code review:
Q1. Why LRU?
Q2. What was the reason behind creating every class?
Q3. How easily can you change/modify Caching policy?
Problem Solving / Data structure Round (1 hour)
Q1. Given a set of positive integers, write a function to order the integers in such a way that the concatenation of the numbers forms the largest possible integer and return this integer.
Q2. You are standing at 0 on a number line. At i’th turn you can move exactly i steps towards left or right. What is the minimum number of steps required to reach a given number n?
Q3. Given a 2D square matrix of zero and one. Find the largest square submatrix inside the given matrix which has one on all its boundary.
eg:
1 0 1 1 1 1
1 0 1 0 1 1
1 0 1 0 0 1
0 1 1 1 1 1
1 1 0 1 1 1
0 0 1 1 0 1
Output: 4 (highlighted in bold, I solved it using N^3 DP)
Q4. Sort a stack using only recursion. You can’t use any loops.
Q5. Given an array find a subset with a given sum.
All questions involved writing pseudo code, time-complexity, space-complexity, edge-cases
HR Round(30 mins)
Q1.Tell me something about yourself.
Q2. Discussed projects of current company in detail.
Q3. What was most challenging I did at my company?
Q4. Who is your role model, why?
Q5. Have you helped juniors at your company?
Q6. How do you keep updated with new technologies?
Q7. Why are you changing job?
Q8. Why Flipkart?
Result: Selected! Thanks crazyforcode! for your content.
