Round 1 – Online Coding Round on Amcat Platform

1. Top N competitors similar to this
   https://leetcode.com/discuss/interview-question/542597/

2. A very similar question to this , same concept of BFS will apply
   Given a 2D grid, each cell is either a zombie 1 or a human 0. Zombies can turn adjacent (up/down/left/right) human beings into zombies every hour. Find out how many hours does it take to infect all humans?
   https://leetcode.com/discuss/interview-question/411357/

Example:

Input:
[[0, 1, 1, 0, 1],
[0, 1, 0, 1, 0],
[0, 0, 0, 0, 1],
[0, 1, 0, 0, 0]]

Output: 2

Both top N competitors and the Zombie problems were quite interesting and challenging. Althought the zombie problem was twisted in terms of description, the scope of the problem was exactly the same. Instead of Zombies, it was updating the adjacent servers in least possbile number of days.

After this in each round they were expecting most optimized and productive code as i was 1.5 year experienced.

Round 2 –

Asked for my Work Experience and Projects in beginning and then jumped to questions
This was taken by 2 SDE’s

PEN-PAPER-ROUND

1. Convert BST to Doubly Linked List without deforming tree and without using extra space except used for creating List. So this shouldn’t be done inplace.
   Time and Space Complexity of my solutions -: O(n) & O(1) respectively

2. You are given a subarray which has only 0’s and 1’s , Maximise the subarray containing 1’s and in this you can only flip one 0 , tell the index of that 0
   Similar to this
   find-zeroes-to-be-flipped-so-that-number-of-consecutive-1s-is-maximized
   on GFG
   Time and Space Complexity of my solutions -: O(n) & O(1) respectively

Round 3 (It was a Managerial Round) –

Discussion on one of my Project and then jumped straight to questions , it was more of

WHITE-BOARD-ROUND

1. minimum-swap-required-convert-binary-tree-binary-search-tree on GFG

Firstly asked about my approach and then code

2. Implement LRU Cache
   Detailed discussion on Idea and then code
   https://leetcode.com/problems/lru-cache/

I gave approach similar to what needed in this.
Worst time complexity for get() is O(1) and for put() can go to O(n)

3. Find the next greater element of every element in an Array
   I gave stack based approach with time and space complexity of O(n) each traversing array from left to right , he wanted to work with same approach but optimize it further , so i thought and told him that we can traverse array from right to left , it reduces number of comparisons
   next-greater-element on GFG

Then we had long discussion on Leadership Principles.

Round 4 –
This was taken by a SDE , he was very helpful and cool.

Firstly he told about himself and then asked about me and then he jumped to questions

He asked me difference between Trees and Graphs
and then he gave me this question.

1. We have been given a list of pair , which denotes edges of a tree , there can be a edge which lead to creation of cycle , I have to find pair , which causes cycle. If there are multiple edges which form cycle , then i have to choose last from list.

First I told him , DFS Approach and then I told him Disjoint Set , he was satisfied with second approach and then I implemented it and wrote solution for this problem.
Time Complexity – O(n^2) where n is length of list given in input.

2. Find minimum length subarray whose elements sum up to >= k
   Similar to minimum-length-subarray-sum-greater-given-value on GFG

First I gave him O(n^2) approach and then o(n) windowing technique.
and then I wrote code for second technique.

Round 5(It was taken by different manager)-

As this round started so late , I got tired till then. He was really very cool. He asked about me and how is my experience till now. then he gave me a question and he wanted robust productive code considering each and every testcase carefully. This code should never crash or give wrong output.

1. Replace every element in array with next greater element present to its right in array(greater by position not value)
   so i told him that it is very similar to question asked to me in round 2 , still he wanted to listen my approach and wanted me to code it.

I gave him approach and I coded it , then he found some loopholes in it which can be potential points for crashing and some things which he didn’t like in my code , then I coded it again as he wanted. He was happy with my this attempt.
First code was working fine , the only error in it is no check for null or empty array and some duplicate code.
Time Complexity – O(n)
Space Complexity – O(n)

then again discussion on projects and leadership aspects.

The process ended after this.

Verdict : Selected