How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Experian.

What role is this question designed for?

This question is commonly asked for Data Scientist candidates at Experian during technical interviews.

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.

Input: ([7, 7, 7, 7, 7, 7, 7],)

Expected Output: 1

Explanation: All elements equal; strict increase allows only length 1.

Input: ([],)

Expected Output: 0

Explanation: Empty array has no subsequence; length 0.

Input: ([5],)

Expected Output: 1

Explanation: A single element is itself an increasing subsequence of length 1.

Input: ([5, 4, 3, 2, 1],)

Expected Output: 1

Explanation: Strictly decreasing; the best increasing subsequence is a single element.

Input: ([1, 2, 3, 4, 5],)

Expected Output: 5

Explanation: Already strictly increasing; the whole array qualifies.

Input: ([-2, -1, 0, -3, 4, -5, 6],)

Expected Output: 5

Explanation: [-2, -1, 0, 4, 6] is a longest increasing subsequence of length 5.

Input: ([3, 10, 2, 1, 20],)

Expected Output: 3

Explanation: [3, 10, 20] (or [2, 20] etc.) gives a maximum length of 3.

Input: ([2, 2, 2, 1, 3, 4],)

Expected Output: 3

Explanation: [2, 3, 4] is a longest strictly increasing subsequence of length 3.

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.

Quick Overview

This question evaluates algorithm design and data structure skills, covering subsequence analysis, constraint/graph modeling for seating, and external-memory sorting considerations for scalability.