The interview consisted of one technical round, focused on DSA fundamentals + problem-solving depth.

Question 1: Deep Copy of Linked List (with Random Pointer)

The interviewer explored the concept in depth.

My Approach:

→ First explained brute force using HashMap (O(n) space)
→ Then optimized to O(1) space using node interleaving

Follow-ups:

1. What do key & value represent?
   → The original node acts as the key and its copied node as the value.

2. Can we do deep copy without extra space?
   → Yes, using the interweaving technique with O(1) auxiliary space.

3. Why separate linked lists?
   → To ensure changes in the copied list don’t affect the original.

4. Dry Run- hashmap solution.

5. Optimisation & Time Complexity/ Space Complexity

6. Edge cases.

Question 2: Next Higher Rated Movie

Given a list of movies with ratings, find the next movie on the right with a higher rating.

My Approach:

Used Monotonic Stack (Next Greater Element pattern).

Follow-ups:

1. Why traverse from right?
2. When would brute force fail?
3. Can we do it without stack?

It was a concept-heavy and discussion-oriented interview. I suggest two things:

1. You should always have an answer for:
   a. Why you're using this DS? what advantage that gives in this PS?
   b. Why you're doing this step?
   c. Can you optimize this?
   d. Run me through a test case.
   e. What's the TC/ SC?

2. Think aloud clearly.

Upvote if you liked!
All the best to everyone preparing. 💪