Round 1. (Most of the questions were from LeetCode's 150 must-do coding questions)

1. Rotate array k to the left.

   • I solved this question first with the brute-force approach using two for loops, each time shifting an element to the left for k times.
   • The interviewer asked to optimize this since the time complexity was O(n^2).
   • I discussed the approach with extra space where elements can be copied to the new array accordingly.
   • He asked if I could come up with a solution without extra space.
   • I solved this by first reversing the whole array and then reversing the array again from 0 to k-1 and from k to n-1.
   • The interviewer was satisfied.

2. Insert, delete, and getRandom in O(1).

   • I had already solved this on LeetCode, so I knew the answer and explained it well to the interviewer.
   • He seemed satisfied.

3. Copy linked list with a random pointer

   • I tried to solve this with a map, but he asked to solve it without extra space.
   • This is where I could not come up with an optimized solution.

4. Delete given node from the linked list (Head of the linked list is not given)

   • I solved this first with O(n), but he was expecting O(1).
   • After some time, I was able to solve it in O(1).

The interviewer was a kind and helpful person. He seemed satisfied with the answers.
Verdict - Selected.

Round 2 (same day after 1 hour)

1. Mirror image of a binary tree

   • I solved this using recursion. It took around 15-20 minutes.
   • I explained the code, but there was a mistake he pointed out.
   • After discussion, I corrected that and moved to the next question.

2. Detect cycle in a linked list

   • This one was an easy question, so I quickly solved it with a slow and fast pointer.

3. Find the node that has a cycle in a linked list

   • This was a follow-up question, and I was clueless.
   • He helped me with the hints, and I was able to solve this as well.

In this round, a lot of discussions were there, and these 3 questions took all the time. It was a really good interview, and I learned new things as well.
Verdict - Selected.

Round 3 (next day)

1. Snake and ladder

   • He told me to write a pseudo code and explain.
   • I wrote pseudo code and explained all the data structures and logic which I used to solve this problem.
   • He was satisfied, but it took me around 20-30 minutes to solve this.

2. Find the shortest unique prefix for every word in an array

   • I solved this using tries. Actually, I had solved this problem, so it was easy for me.

3. Few general questions about the current project and my current company role and responsibility.

I was a little confused about the result since the second and third rounds were not up to the mark.
In all three rounds, starting question 'tell me about yourself' was there.

After two days, I got a call from the recruiter HR that I'm selected. I was very excited.
They offered me after 15 days.

Offered CTC - 25 LPA (fixed)
YOE - 3.9
Location - Hyderabad