Uber Interview Questions - Longest Increasing Subarray

Uber Interview Questions - Longest Increasing Subarray This week, Im going to talk about the longest increasing subarray problem. You can find more posts like this at Uber Interview Questions. Also, this question is similar to Subarray With Given Sum. If you have read our previous post, I hope you can solve this problem easily. In this post, Im going to cover topics like “sliding window”, dynamic programming, time/space complexity and so on. Longest Increasing Subarray Given an array, return the length of the longest increasing subarray. For example, if the input is [1, 3, 2, 3, 4, 8, 7, 9], the output should be 5 because the longest increasing array is [1, 2, 3, 4, 8]. This question has been asked by Uber, Facebook recently (as the time of writing this post). Another reason Id like to discuss this problem is that many techniques used in this question can be re-used in other places. Analysis It should be obvious that the most naive approach is to check all subarrays and return the longest increasing subarray. Although this approach doesnt require extra memory, the time complexity would be O(n^2) where n is the length of the array. This apparently is not what interviewers want, but its usually recommended to mention this approach briefly and also clarify that you know this is not optimal. Lets see how we can make it faster. Think about this: if we want to make it faster than O(n^2), common scenarios are O(nlogn), O(n) and O(1). O(1) seems impossible because we should iterate over the array at least once. So O(n) would be the lower bound. If we want to aim at O(nlogn), usually it means we should do something like sort, binary search, and so on. Since we dont want to change the order of the array, sort is not useful. Binary search also seems irrelevant. As a result, O(n) is our target. Sliding Window If you try to solve this problem manually, you may realize that not all subarrays need to be checked. For example, suppose input is [1, 2, 3, 2, 4, 5, 6], you start with increasing subarray [1, 2, 3]. However, the next one (2) is smaller than the previous number. In fact, you can ignore everything before 2 and just check from the subarray [2, 4, 5, 6]. If you have read our previous post Longest Substring Without Repeating Characters, the sliding window approach should be quite obvious. In fact, its one of the most common techniques to process an array in linear time. So we can have the following algorithm: We keep two pointers start and end to denote the subarray arr[start: end] If the current array is increasing, which means arr[end] arr[end 1], we can increase the current array by add 1 to end Otherwise, we can ignore everything before pointer end. So just set start = end In the end, just return the longest subarray Its worth to note that checking corner cases in the beginning is very necessary. Although the code is quite concise, its easy to make mistakes about boundaries. Extension Lets change the question a little bit. Instead of getting the longest increasing subarray, how to return the length of longest increasing subsequence? For subsequence, numbers are not necessarily contiguous. If the input is [1, 3, 2, 3, 4, 8, 7, 9], the output should be 5 because the longest increasing subsequence is [2, 3, 4, 8, 9]. Id like leave this question as a homework. But here are some hints: Some people might want to do a brute force, however, youll soon notice that you wont be able to list all possibilities. In this case, usually we should rely on a recursive solution. The key to the recursive solution is to come up with the recursion formula. Memorization can significantly improve the speed, though requires more memory. Check Subarray With Given Sum if you still cant figure this out Summary Array questions are quite common in interviews as it doesnt require any prior knowledge and its one of the best ways to test candidates basic coding skills. I dont think this question is hard to think, but writing bug-free code is not trivial, especially with a time constraint. I would say everyone should try to write down the solution even if youve already read this post. By the way, if you want to have more guidance from experienced interviewers, you can check Gainlo that allows you to have mock interview with engineers from Google, Facebook etc..