highway-at-night-picjumbo-com small

Uber Interview Questions – Longest Increasing Subarray

This week, I’m 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, I’m 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 I’d 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 doesn’t 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 it’s usually recommended to mention this approach briefly and also clarify that you know this is not optimal.

Let’s 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 don’t 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, it’s 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

longest increasing subarray

It’s worth to note that checking corner cases in the beginning is very necessary. Although the code is quite concise, it’s easy to make mistakes about boundaries.

Extension

Let’s 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].

I’d like leave this question as a homework. But here are some hints:

  • Some people might want to do a brute force, however, you’ll soon notice that you won’t 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 can’t figure this out

 

Summary

Array questions are quite common in interviews as it doesn’t require any prior knowledge and it’s one of the best ways to test candidate’s basic coding skills.

I don’t 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 you’ve 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..

The post is written by Gainlo - a platform that allows you to have mock interviews with employees from Google, Amazon etc..

I'd like to learn more

Share on Facebook22Tweet about this on TwitterShare on LinkedIn1Share on Reddit0

9 thoughts on “Uber Interview Questions – Longest Increasing Subarray

  1. I’m enjoying your articles and these are really helpful to get an insight to solve interview questions.

    In this article, there is a typo so I fixed it. Please correct it.

    If the input is [1, 3, 2, 3, 4, 8, 7, 9], the output should be 6 because the longest increasing subsequence is [1, 2, 3, 4, 8, 9].

    Thanks in advance.

  2. > 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].

    Why is the answer not 6 with both subsequences [1,2,3,4,8,9] and [1,2,3,4,7,9] being valid?
    Perhaps ‘sub’ in subsequence implies at least one end must be excluded (strictly less than)?

  3. > 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].

    it should be [1, 2, 3, 4, 8, 9]

  4. Thanks for great posts. In the example for the extension, If the input is [1, 3, 2, 3, 4, 8, 7, 9], it was mentioned that the output is 5 and the longest increasing subsequence is [2, 3, 4, 8, 9]. Why we ignored 1? I think longest increasing subsequence is [1,2, 3, 4, 8, 9] and its length is 6.

  5. Thanks for the great blog. Very educational and helpful. That said, the longest increasing subsequence will be {1,2,3,4,7,9}.

  6. Isn’t a subarray like a substring…contiguous and hence the solution to the original problem is [2, 3, 4, 8] and not [1,2,3,4,8].

  7. In your post, you state – 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].
    I look at [1, 3, 2, 3, 4, 8, 7, 9] and see the longest increasing subarray as [2, 3, 4, 8] and length = 4. How is 1 being included in your answer if subarrays are expected to be contiguous elements?

    Am I misunderstanding the definition of subarray here?

    Thanks!

Leave a Reply

Your email address will not be published. Required fields are marked *