InternDoor

Longest rising pick

Mediumdynamic programming · binary search

Reported in interviews at (where)

From a list of whole numbers nums, pick some of them, keeping their order in the list (they need not sit next to each other), so that every pick is strictly bigger than the one before it.

Return the most numbers such a pick can hold. The lists here go up to 100,000 numbers, so the O(n^2) method is too slow: look for O(n log n).

Example 1
Input
nums = [3,10,2,1,20]
Output
3

3, 10, 20 rise; no four numbers do.

Example 2
Input
nums = [5,5,5]
Output
1

Equal numbers do not rise, so only one of them.

Example 3
Input
nums = [2,8,3,4,1,9]
Output
4

2, 3, 4, 9.

Limits

  • 1 <= nums.length <= 100000
  • -10^9 <= nums[i] <= 10^9

Hints

Hint 1

Keep, for every length, the smallest number a rising pick of that length can end with.

Hint 2

That list stays sorted, so each new number finds its place by binary search.

Where this was reported

Our own problem on the task these candidates describe; the wording, examples and tests are InternDoor’s.

Run your code to check it on the examples. Submit runs every hidden test.

Ready for the real one?

Engineering internships and entry-level jobs in India, newest first.