Interview Experience (Flipkart)
There were 3 rounds of interview. 2 DS/Algo rounds and a hiring manager round. The first round was of 30 mins and 2 questions were asked. And second round was of about 45 mins and again 2 questions were asked. I was supposed to code the solution and discuss multiple approaches to the problem and explaining their time and space complexities.
Round 1:
This round was taken by one of our alumni. The interviewer was friendly and made me comfortable.
Question1: https://leetcode.com/problems/container-with-most-water/
It’s a common question but I missed it initially. I tried doing something with stack but later I realized it’s 2 pointer approach and wrote the code. The interviewer was satisfied with the solution.
Question 2: You are given three sorted arrays A, B, C. You have to count the number of tuples (a,b,c) satisfying a>b>c. a is taken from A, b is taken from B, and c is taken from C.
I initially gave a solution of O(n^2(log n)^2) but he told me to optimize it. He gave me hint to use extra space. Then I gave an O(N log N) solution with O(n) space. He asked me to write it’s code. Then he asked me to optimize it further. Finally, I gave an O(n) solution with O(n) space.
The interviewer was happy with my response and asked me not to mess up my further rounds. :D
Round 2:
This interview was scheduled abruptly. HR called me later that evening and told me 2nd round would happen after 10 mins. Initially, there were some issues with connection and platform so this interview happened on google meet and I coded solutions on google docs. The interviewer asked two questions. He gave me no hints throughout the interview.
Question 1: Given the NxN matrix. Each cell contains a symbol which is the direction to which you can move from that position. Like if ‘->’ then you can move the left adjacent cell, ‘<-‘ then move to the right adjacent cell, and so on for moving upwards and downwards.
Now you would be given a start and an endpoint. You have to find if there is a path from start to end.
So, initially, I have an approach using dfs of O(n^2) time and space. He asked me to optimize the space specifically. I asked if there is going to be cycles or not. So, he replied yes there would be.
I was stuck here for a while. Then he told me to first code the dfs solution. I coded it properly on google docs.
I later realized that there is only one option for us to move from the current cell to the next cell. So, I suggested a two-pointer solution. Take two pointers fast and slow. Move fast pointer with twice as speed as a slow pointer. If one of the pointers reaches the end cell then return true. If the fast and slow pointer meets before then there is loop and no path to the end cell.
So this was of O(n^2) time and O(1) space. The interviewer was satisfied with this.
Question 2: https://leetcode.com/problems/shortest-unsorted-continuous-subarray/
Again a standard question. I didn’t remember the solution that time. So I initially gave O(nlog n) approach with O(n) space then later an O(n) solution with O(n) space. He asked to dry run my approach over a given test case. He was satisfied with it and didn’t ask me to code the solution.
Round 3:
This was the hiring manager round. Basic questions were asked about the projects mentioned in the resume.
Basic questions like:
How you store the password in the database?
Which encryption did you use?
Which database did you use?
Design the schema of the database.
Some question regarding sockets, client-server, and peer to peer architecture.
What are the difficulties you faced while working on this project?
And why Flipkart?
The experience was altogether nice. I feel the first question in the second interview was the critical one. I am happy that I was able to give the O(1) space solution without any hints.
I feel that one should not miss getting the standard questions right. Because they turn out to be a real deal-breaker in many cases. It was also a matter of great luck that I got selected as I was shortlisted among very talented people for the interview.
But that’s what they say, “Hard work puts you where good luck can find you”. 😊
Satvik Pandey
CSE 2k21
Comments
Post a Comment