• Status: Pre-final undergrad at IIT
• Date: 5th September 2020
• Virtual On-campus

Round 1 : Coding Assessment (90 mins)

• There were 3 programming problems, as follows :
  1. Given n groups of singers(as array of size n with arr[i] denoting the ith group size) and m microphones available, we had to output the minimum largest group size sharing a single mic.
  A group could only be divided into two further groups at a time. (The approach was to use binary search and check for the optimality of the group size.)
  Eg: input: arr: [100, 60, 80, 40, 30] , m=9
  output:40 (like we can have groups as follows after division: 40,40,20,40,20,40,40,40,30)
  Time Complexity: O(nlogn)

  2. Based on Graph: This problem had n nodes numbered from 1 to n and m edges, the goal was to return the connected component with the largest sum of priorities
     (an array of priorities was given for each node). A simple dfs based solution possible. Time and space: O(n)

  3. Given a number n(could be negative as well,in the range -10^7 to 10^7), the target was to get the permutation having the smallest magnitude(no leading zeros were allowed).
     Ex: for 901 the output should be 109. [I did it by creating an array of its digits and sorting the permutation] Time Complexity: O(nlogn)

• I solved all the three problems and took around 45 mins after which I submitted my test.[45 mins still remained :)].

• 12 students were shortlisted for the technical interview. The interviews were to be held on AMCAT platform.

Round 2 : Technical Interview 1 (Around 40 mins)

• I greeted the interviewer and he did the same. Immediately, since the interview was scheduled for only 30 mins, he started off with the coding questions.

1. The first problem flashed on the screen and seeing it I had a subtle smile. A sorted array had been given along with the target number to be found, the statement was
   to give the range of indices [l,r] such that all elements in this range are the target. If the target wasn't present, the output was to be an empty array [].
   Eg: Input:[5,11,15,80,80,101]
   Output: [3,4] (0-based)

   • I gave 4 approaches for the problem and the interviewer looked very convinced.

     • A simple array traversal in O(n) time.
     • Applying binary search and then expanding both sides of the first found target,but this could also have gone O(n) in worst case.
     • Applying two binary searches for the first and last occurrences separately. Complexity O(logn+logn).
       After this the interviewer said that what if I had access to library functions.
     • I told him that we could use lower bound and upper bound to solve it.

2. Then we came to the next problem, Given an array of only numbers 0-9, we had to maximize the number of buckets in the array given the condition that all the occurrences
   of a specific digit had to come in the same bucket.

   Eg: Input: [0,0,1,1,2,1,7,8,7,9,9]
   Output: 4 ,[0,0],[1,1,2,1],[7,8,7],[9,9]

   • A simple O(n) solution was possible given we store the first and last index of each occurring number in the array.

3. Another problem was shot next, the statement: Given an n-ary tree, convert it into a binary tree for storage in memory as it wasn't possible to store an n-ary tree.
   So, we had to implement encode() and decode() functions for the same.

   • Initially my approach was a bit haphazard but I kept talking about it whatsoever,he gave me a subtle
     hint and 30 seconds to figure out the solution. I approached it using creation of dummy nodes, as he had already exempted me in space and time complexity at the start
     of this problem (and we were running 10 mins late). Finally he gave me a number of test cases and my solution passed all of them so he sounded very convinced.

   The Interviewer was very attentive and coordinated wonderfully well, giving instructions and hints whenever needed.

• This was the end of the round. 7 people advanced to the next round.

Round 3 : Technical Interview 2 (Around 37-40 mins)

• This round started in a different manner, where the interviewer first asked me about myself, told me to give a brief description of all the projects enlisted on my CV.
  We had a good chat for about 10 mins and then he started off with the coding questions. Asked me whether I liked Graphs or not to which I replied it was my favourite.

1. You are given an array of integers (with arr[i] describing the index of the array to which we can jump from the ith index). We were allowed to either move from current
   index to the next index or to arr[i] as described. The goal was to minimize the number of jumps(edges traversed) to reach the last index.

   • I connected each index with arr[i] and (i+1) with directed edges to model the desired graph. Then, I gave a brute force solution of generating all paths and seeing whether we could reach end or not. He said it was too hectic and wanted me to solve using BFS instead of DFS.
   • I got the hint and told him how the entire procedure worked. Time complexity: O(N) and Space Compelxity: O(N) He said he wanted to check my knowledge of bfs. (Still no code was desired :) )

2. Given a binary matrix (0s and 1s only) in which all the rows are sorted. We were to find the maximum number of zeros(in a row) and its row index.
   Eg:
   Input:
   0 0 0 0 1 1 1 1 1 1
   0 0 1 1 1 1 1 1 1 1
   1 1 1 1 1 1 1 1 1 1
   0 0 0 0 0 0 0 0 1 1
   0 0 0 1 1 1 1 1 1 1
   Output: 8 zeros in 4th row

   • I first gave a brute force approach of traversing all rows and columns. Time Complexity: O(n*m). He asked to optimize it further.

   • I gave an O(n+m) approach. Starting from first row and first column, we would go on incrementing col index until we find a 1. When 1 is found,update the answer and move on to the next row. Remember to take care of the edge cases.

   I was asked to write a pseudocode and I was happy to do so as well.

   Finally the interviewer asked if I had any questions for him to which I asked: What is it like to be a part of Flipkart? What kinds of projects will be assigned to interns? He gave the answer, we had a little chat and the round was over.

• 6 people were able to make it to the Hiring Manager round which was the final round. My interview had been scheduled in the first slot. I was confident that it
  would go well.

Round 4 : Hiring Manager Round (Around 25-27 mins)

This was a Senior Manager taking the interview as opposed to the previous two rounds. He started off by greeting me and asking about the Covid19 scenario in my locality,where I stayed and stuff.
Then he asked me about the semester I was in and the subjects that had till then been taught.

Again he now asked me to tell about myself. I briefly explained my journey in Computer Science domain and where I was headed.

Then he questioned me vividly on my skills and values (typical HR questions). I always connected the questions to an anecdote from my life and went on about how I failed, attempted, gave my best shot, succeeded etc. I had not prepared for even a single question, whatever I said was very natural which made him very impressed and he went on digging deep into those experiences that I told him about.

My JEE story, quizzing as a passion in school, dramatics in college etc. I was so happy to oblige, this was a dream come true HR round for me. He was so humble in the way he spoke and went about asking questions and responded greatly to all my answers. After 21 mins, he said he was done on his part and asked whether I had any questions for him.

I asked the very same question as in previous round and he went on talking about it in great detail, explaining each and every aspect where they are currently facing challenges and scope for research in those domains.

After this,I said I had no further questions and finally we greeted each other and the interview was over. I knew I had done well.

• The results were announced the following day and 5 people were selected for internships, me being one of them.

Some suggestions on my part:

• Do not lose your confidence if you don't crack the interview. Many factors influence it and you should always learn something new out of each experience.
• Dress yourself formally before the interview and make sure to take sound sleep before the D-day.
• Do not feel shy of speaking your heart out in the interviews, even if the approach is not well defined, the interviewer would want to help you if you interact and maintain the purpose of problems with him.
• Make sure you understand the problem very precisely, ask questions, repeat, do not feel ashamed. You could also ask the person to run a testcase for you. Start writing the code only when it has been agreed upon and fully optimized. Do it in one go, and check for any errors and debug them.
• Keep a smiling face throughout, do not try to fake anything. Those people there, are masters of knowing about your attitude towards the role.
• Finally, for the HR round, tell examples from your life where you exhibited qualities that the interviewer wants to know about. He would easily relate to them this way, and yes, try to keep it as natural as possible.

Go rock the stage :) (Because you deserve it!)