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 Facebook23Tweet about this on TwitterShare on LinkedIn1Share on Reddit0

22 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]

    1. "Leave it as-is. Many sites have duplicate co&etnt.nquot; :-/What about duplicate page made for synonims, it should not be considered as a cheat for spiders as it improve user experience.It is hard to follow google guidelines. Some people are blacklisted, some people not. Some people are sandboxed, others not.

  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}.

    1. Thanks for your post on the travel industry. I will also like to include that if you are a senior thinking about traveling, its absolutely vital that you buy travel insurance for older persons. When traveling, senior citizens are at high risk of getting a heltht-relaaed emergency. Obtaining right insurance cover package for one’s age group can look after your health and provide you with peace of mind.

    2. I too confused initially.
      If the sub-arrays are contiguous elements, then it O(n^2). If sub-arrays are non-contiguous then it is O(2^n).
      Here the solution is for contiguous elements sub-array.

  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!

    1. As TMN pointed it out in the previous comment, I think the solution given here return [2, 3, 4, 8] with length = 4. I think the post is describing the solution for the extension problem – longest increasing subsequence-.

  8. In the longest increasing subarray case, your example is wrong.

    For the list [1, 3, 2, 3, 4, 8, 7, 9] the longest increasing subarray should be [2,3,4,8] as a subarray is contiguous similar to a substring. Please correct it.

    Because the python code finds longest subarray which also gives [2,3,4,8] in this case.

  9. Hi Team,

    Your solution works for sub-array with continuous elements but not for the problem to find longest increasing sub-array with non-continues elements.

    For input: 1 3 2 3 4 8 7 9
    Continous elements sub array – 2 3 4 8 (4) (As per your solution)
    Non Continous elements sub array – 1 2 3 4 7 9 (6)

    Correct me, if I am wrong
    Many Thanks,
    Manohar

  10. Wrong content in post totally confused me
    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].
    is wrong
    Answer is 4 and the array is [2,3,4, 8]

    Question is subarray and not subsequence so answer is 4

  11. I think here the assumption is that the subarray has to be of contiguous elements, else the algorithm does not work for non-contiguous elements.
    If we run through the solution provided, the max_len returned here is 4.

    Thanks !

  12. The function doesn’t seem right, I think it will only give the max length of contiguous subarrays, whereas non-contiguous ones are mentioned in the provided example, [1, 3, 2, 3, 4, 8, 7, 9] giving 5 for [1, 2, 3, 4, 8].

    Another example:
    longest_increasing_subarray([5,1,6,2,7,3,8,4,5])

    Should give length 5, for [1,2,3,4,5], but only gives 2, for [4,5]

  13. Also, there is little difference between following two,
    1. Longest Increasing sub array
    2. Longest Increasing contiguous sub array

    The first one doesn’t have to be contiguous, where as the second one is contiguous. I think, you algorithm will work for the second one. Please correct me if I am wrong.

Leave a Reply

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