Round 1
Questions: The interviewer asked about the Longest Increasing Subsequence.
- Clarifying questions were asked regarding:
- Presence of duplicates or negative numbers
- Whether the sequence needs to be strictly increasing
The candidate mentioned a brute force approach involving sorting and iterating through the sequence to find the longest one. The interviewer prompted for performance details, leading to a discussion on time and space complexity.
Follow-up Question:
- The interviewer asked the candidate to optimize the initial approach.
Candidate's Approach
The candidate proposed a hash set approach:
- Add all elements to a set.
- Iterate through the set and for each number, explore left and right to find the longest sequence.
- Example sequence: (5, 2, 1, 8, 9, 4, 3, 7)
- Starting at 5, the candidate would go left to find 1, then right to find the sequence 1-2-3-4-5.
- To avoid revisiting elements, the candidate suggested using an extra visited set.
- The candidate calculated the time complexity as O(n) and space complexity as O(n) for both sets.
The interviewer suggested an optimization hint:
- Instead of going left every time, check if
num - 1exists to start finding the sequence, which could eliminate the need for the visited set.
The candidate struggled to fully grasp this hint under pressure but incorporated it into the final code, albeit still using the visited set unnecessarily. The candidate successfully wrote working code and ran test inputs provided by the interviewer.
Interviewer's Feedback
No feedback provided.