OA -

4 questions were asked. Two were simple brute force, if optimized then all tc would have been passed, one was simple graph BFS (nodes at dist K) but identifying it and implementing it in that time was hard. One was a really hard CF 2000 rated question.

Round 1 (1Hr) -

Pure DSA based round. One question based on Binary Trees + DP was asked (https://leetcode.com/problems/house-robber-iii/description/). My approach was Brute->Optimised->DP(Memoization)->DP(Tabulation). I was able to write the correct pseudo code along with the expected time and space complexity.

The second question was also on binary trees. I had to find the Kth ancestor of the given node in the binary tree (https://leetcode.com/problems/kth-ancestor-of-a-tree-node/description/). I initially approached with a brute force approach using a map and DFS, but was able to optimize it using BFS and vector. I was able to write code for both the approaches with expected time and space complexity.

The interviewer was satisfied with the given solutions and I was qualified for the next round.

Round 2 (1Hr) -

This was the hardest round. The interviewer grilled me on hard graph concepts. This was the first question (https://leetcode.com/problems/bricks-falling-when-hit/description/). I was able to come up with the brute force but the interviewer was not satisfied. We had to use union find to solve it optimally but i was not able to come up with it.

The next question was related to the convex hull algorithm. I was not able to come up with the solution. This round was really hard. Candidates who cleared this were selected for the next round.