Design Algorithm for Longest Increasing Subsequence Length
Company: Experian
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
##### Scenario
Programming assessment and infrastructure panel
##### Question
Design an algorithm to return the length of the Longest Increasing Subsequence of an array.
Seat students so that no two listed friends sit next to each other; provide algorithm and complexity.
How would you sort a file containing 50 numbers? How would your approach change for a 1-million-number file stored on disk?
##### Hints
Use O(n log n) patience sorting + binary search; graph/constraint satisfaction; external merge-sort for large files.
Quick Answer: This question evaluates algorithm design and data structure skills, covering subsequence analysis, constraint/graph modeling for seating, and external-memory sorting considerations for scalability.
Given an integer array `nums`, return the length of the longest strictly increasing subsequence.
A subsequence is a sequence derived from the array by deleting zero or more elements without changing the order of the remaining elements. The subsequence must be strictly increasing (each chosen element strictly greater than the previous one) but the chosen elements need not be contiguous.
Example 1:
Input: nums = [10, 9, 2, 5, 3, 7, 101, 18]
Output: 4
Explanation: One longest increasing subsequence is [2, 3, 7, 18] (or [2, 3, 7, 101]), which has length 4.
Example 2:
Input: nums = [0, 1, 0, 3, 2, 3]
Output: 4
Explanation: A longest increasing subsequence is [0, 1, 2, 3].
Example 3:
Input: nums = [7, 7, 7, 7, 7, 7, 7]
Output: 1
Explanation: Equal elements are not strictly increasing, so the best length is 1.
Aim for an O(n log n) solution.
Constraints
- 0 <= len(nums) <= 2500
- -10^4 <= nums[i] <= 10^4
- The subsequence must be strictly increasing (duplicates do not extend it).
Examples
Input: ([10, 9, 2, 5, 3, 7, 101, 18],)
Expected Output: 4
Explanation: [2, 3, 7, 18] is one longest strictly increasing subsequence of length 4.
Input: ([0, 1, 0, 3, 2, 3],)
Expected Output: 4
Explanation: [0, 1, 2, 3] is a longest increasing subsequence.
Hints
- A patience-sorting approach maintains a list `tails`, where tails[k] is the smallest possible tail value of any increasing subsequence of length k+1.
- For each element x, binary-search for the leftmost position in `tails` whose value is >= x; replace it (or append x if x is larger than all tails). The answer is len(tails).
- Use bisect_left (not bisect_right) so that equal values overwrite rather than extend, enforcing STRICT increase.