Round 1 - Online Assessment (OA)
Both questions were based on the "pick not pick" variation of Dynamic Programming (DP), one from 1D DP and the other from 2D DP.
Round 2 - DSA Round
The first question was a variation of the Rat in a Maze problem, involving 2D DP. The second question was Find the Largest Plus Sign. I provided the approach and explained how we could solve it, but since the code was too long, I had already spent 30 minutes (10 minutes on a normal database question and 20 minutes on this one). So, I asked for the second question.
Q2: Find the Missing Positive Number Without Extra Space (O(n) Approach Required)
I initially gave the brute force solution, which used extra space, but the interviewer wasn’t satisfied. Then, I suggested sorting the array and applying binary search, but that had a time complexity of O(n log n), which wasn’t acceptable. Finally, I implemented the cyclic sort approach, passed all test cases, and completed the solution.
At the end of the interview, the interviewer wished me "All the best for the future," which made me feel that I wasn't 100% perfect and led to receiving a rejection. Despite solving 1/2 questions completely and approaching the first one, If this level of questioning is being asked for an internship, I am traumatized. I still got rejection, waiting for the feedback.