Flipkart Interview | Set 3
Recently I appeared for Flipkart Interview. I would like to share my experience.
Round-1: Telephonic (45 mins)
- Given an array of n distinct integers sorted in ascending order. Find an index i s.t ar[i] = i. Return -1 if no such index exists. Note that integers in array can be negative.
Article Link: https://www.w3wiki.net/find-a-fixed-point-in-a-given-array/
Practice Link: https://www.w3wiki.net/problems/value-equal-to-index-value1330/1
- Design a stack which holds an integer value such that getMinimum() function should return the minimum element in the stack.
FOLLOW UP: Implement popMin() function which would pop minimum element from the original stack. O(1) implementation was required. (Hint: Use LinkedList to implement stack and store address of minimum element node in min-stack)
Article Link: https://www.w3wiki.net/design-a-stack-that-supports-getmin-in-o1-time-and-o1-extra-space/
Practice Link: https://www.w3wiki.net/problems/special-stack/1
- Print an organisational hierarchy.
Naveen manages Satish
Satish manages Anushree
Satish manages Sandeep
Gurinder manages NaveenGurinder->Naveen
Naveen->Satish
Satish->Anushree,Sandeep
Anushree->
Sandeep->
Round-2: Telephonic (30 mins)
- Given an array which is first strictly increasing and then strictly decreasing. Find an element in this array. Discussions on various approaches and their complexities.
Article Link: https://www.w3wiki.net/find-element-bitonic-array/
Practice Link: https://www.w3wiki.net/problems/maximum-value-in-a-bitonic-array3001/1
Round-3: In-House Coding(1 Hour 45 mins)
Write a running code in any language to implement the famous tic-tac-toe game.
First, there was a discussion on various approaches and basic functions which would be required to implement the same. Then I was asked to code.
I was given 1 hour 15 mins to code this. I had to design this game as per following:
- Game has 3 modes: Human Vs Human, Human Vs Computer and Computer Vs Computer.
- Initially start with a 3X3 grid, but it can be generalised to NXN grid. So don’t hardcode any variable.
- Minimise Code Redundancy and try to make it as modular as possible.
- Try to use abstraction and expose a lesser number of functions(APIs) to the outside world.
- Try to cover maximum number of edge cases, like when to abort the game, draw condition, win condition, overwriting the existing value in grid etc)
Round-4: Data Structure and Problem Solving(1 Hour)
- Given a sorted and rotated array. Find an element in this array. (Famous Problem)
- This was an interesting problem. Given a set of intervals like 5-10, 15-20, 25-40, 30-45, 50-100. Find the ith smallest number in these intervals.
Assume there are no duplicate numbers.e.g: 1st smallest number = 5 6th smallest number = 10 7th smallest number = 15 and so on.
I told him that we would first sort the interval on basis of starting numbers. Then merge overlapping intervals to get a set of non-overlapping intervals like 5-10, 15-20, 25-45, 50-100. Now we can find the ith smallest number after finding the appropriate interval.
FOLLOW UP: He then modified this question to accommodate duplicate numbers also.
Suppose we have intervals like 5-10, 8-12. Then total numbers in these two intervals would be: {5,6,7,8,8,9,9,10,10,11,12} So, 1st smallest number: 5 4th smallest number: 8 5th smallest number: 8 (here is the change since now we have duplicate elements also) and so on.
- Given a dictionary of 50,000 words. Given a phrase without spaces, add spaces to make it a proper sentence.
e.g: input: thequickbrownfoxjumpoverlazydog output: the quick brown fox jump over lazy dog
FOLLOW UP Questions:
- Worst case complexity of finding a word in HASHMAP given we have ‘B’ buckets and total of 50,000 words. ( Ans: O(50,000/B) )
- Complexity of finding a word in TRIE. (Ans: O(Word Length) )
- Advantages of TRIE over HASHMAP and some similar discussion.
Round-5: Hiring Manager Round(45 mins)
He asked me lots of questions regarding my current company projects.
Questions:
- My role in current project.
- Most Challenging work in your company.
- What technologies you learnt last year? and several similar questions.
Round-6: HR Round (10 mins)
- Common HR questions like why Flipkart, Why should we hire you etc.
All Practice Problems for Flipkart !