Round 1: Problem Solving/Data Structures
Questions:
-
Increasing Triplet Subsequence:
- I initially proposed an O(n^3) solution and then optimized it to O(n). I discussed the approach with the interviewer, who then asked me to code it on Google Docs. After completing the code, we dry ran it on a few test cases. The interviewer then pointed out that my implementation was incorrect because it didn't maintain
a,b,cexplicitly. I tried to explain that the problem only required a boolean return value, but he disagreed. With 15 minutes left, he moved on to the next question without letting me finish discussing the first one.
- I initially proposed an O(n^3) solution and then optimized it to O(n). I discussed the approach with the interviewer, who then asked me to code it on Google Docs. After completing the code, we dry ran it on a few test cases. The interviewer then pointed out that my implementation was incorrect because it didn't maintain
-
Maximum Number of Vowels in a Substring of Given Length:
- I solved this question optimally using a sliding window approach on the first attempt. The interviewer asked for the time and space complexity. I explained that it was O(n), but he insisted it should be O(n^2) because of the use of two loops. Despite my efforts to clarify that the worst-case scenario involves iterating over the entire array twice, he didn’t understand and abruptly ended the interview.
Candidate's Approach
- For the first question, I proposed an O(n^3) solution and optimized it to O(n) through discussion.
- For the second question, I effectively used a sliding window approach to achieve an optimal solution.
Interviewer's Feedback
- The interviewer pointed out issues with my implementation of the first question and insisted on a different interpretation of the time complexity for the second question, leading to an abrupt end of the interview.