Round 1
Questions:
- Question:
- House Robber III
- A question based on Binary Trees + DP.
- Question:
- Kth Ancestor of a Tree Node
- Find the Kth ancestor of the given node in the binary tree.
Candidate's Approach
-
For the first question, I approached it as follows:
- Brute Force -> Optimized -> DP (Memoization) -> DP (Tabulation).
- I was able to write the correct pseudo code along with the expected time and space complexity.
-
For the second question:
- Initially, I used a brute force approach with a map and DFS.
- I then optimized it using BFS and a vector.
- I was able to write code for both approaches with expected time and space complexity.
Interviewer's Feedback
The interviewer was satisfied with the given solutions and I was qualified for the next round.
Round 2
Questions:
-
Question:
- Bricks Falling When Hit
- The interviewer expected an optimal solution using union find, but I was unable to come up with it.
-
Question:
- A question related to the convex hull algorithm.
- I was not able to come up with the solution.
Candidate's Approach
I was able to come up with a brute force solution for the first question, but the interviewer was not satisfied as the optimal solution required union find, which I could not derive. The second question was challenging, and I could not provide a solution.
Interviewer's Feedback
This round was really hard. Candidates who cleared this were selected for the next round.