Round 1
Questions: Build an integer which is maximum from a subarray of size K. For example, given the array [4, 9, 0, 2] and k = 2, the answer is 92.
Candidate's Approach
The candidate initially provided a dynamic programming solution with memoization, where they added the i'th index number to the result and decremented k, or chose not to add and incremented the index. They mentioned a time complexity of O(k * n).
Later, the candidate proposed an approach where they selected from the left with at least k-1 elements to the right and then took the maximum after that index, using a heap. The interviewer agreed with this approach but suggested further optimization using a monotonic stack to achieve O(n) time complexity.
Interviewer's Feedback
The interviewer was not satisfied with the initial solution and encouraged the candidate to optimize further. They provided a hint regarding the use of a monotonic stack for better efficiency.