# Flipkart Interview | Set 3

Recently I appeared for Flipkart Interview. I would like to share my experience.

Hey geek! It's time to become a success story instead of reading them. Check out our most renowned **DSA Self Paced Course**, now at a student-friendly price and become industry ready. And if you are looking for a more complete interview preparation resource, check out **Complete Interview Preparation Course**** **that will prepare you for the SDE role of your dreams!

Feeling prepared enough for your interview? Test your skills with our **Test Series** that will help you prepare for top companies like **Amazon, Microsoft, TCS, Wipro, Google** and many more!

**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.geeksforgeeks.org/find-a-fixed-point-in-a-given-array/

Practice Link: https://practice.geeksforgeeks.org/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.geeksforgeeks.org/design-a-stack-that-supports-getmin-in-o1-time-and-o1-extra-space/

Practice Link: https://practice.geeksforgeeks.org/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.geeksforgeeks.org/find-element-bitonic-array/

Practice Link: https://practice.geeksforgeeks.org/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.

If you like GeeksforGeeks and would like to contribute, you can also write an article and mail your article to review-team@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.