This question evaluates proficiency in dynamic programming, range-query data structures (Fenwick/segment tree), sorting and two-pointer techniques, and algorithmic complexity analysis within the Coding & Algorithms domain for Python-based implementation.
Implement in Python three tasks.
1) Movie Ratings (DP): Given an integer array ratings of length n, return both
(a) the length of the longest strictly increasing subsequence (LIS) and
(b) one valid LIS as a list of 1-based indices. Explain your DP formulation (state, transition) and provide code. Constraints: 1 ≤ n ≤ 200000; ratings[i] can be any 32-bit signed integer. Target complexity: O(n log n) time, O
(n) memory.
2) Array Challenge (optimize with a tree structure): You are given n and an initial array a[1..n], followed by q operations of two types:
(i) "add i x" — add integer x to a[i]; (ii) "sum l r" — output the sum of a[l..r], inclusive. Constraints: 1 ≤ n, q ≤ 200000. A naive O
(n) per query will time out; implement an O(log n) per-operation solution using a Fenwick tree or segment tree.
3) Update Release Scheduler (sort and compare two lists): You receive two unsorted lists of integers: releases[0..n-1] (timestamps when builds become available) and windows[0..m-1] (deployment windows). Produce an array schedule[0..m-1] where schedule[j] is the timestamp of the latest release ≤ windows[j] that has not been assigned to any earlier window; if no release is available, set schedule[j] = -1. If multiple releases qualify for a window, choose the one with the greatest timestamp. Approach should sort both lists and scan with two pointers. Target complexity: O((n + m) log(n + m)) time, O(
1) extra space aside from outputs.
Overview: This question evaluates proficiency in dynamic programming, range-query data structures (Fenwick/segment tree), sorting and two-pointer techniques, and algorithmic complexity analysis within the Coding & Algorithms domain for Python-based implementation.
You are given 120 minutes to implement three independent algorithmic tasks in Python. Each task specifies the required input/output behavior, the constraints, and a target time/memory complexity. For every task you should: explain your approach (state, transition, or invariant where relevant), write clean Python, and argue that your complexity meets the target.
Constraints & Assumptions
Python 3. Standard library only (
bisect
,
heapq
, etc.). No third-party packages.
Tasks are independent; they share no state.
Per-task scale limits and target complexities are stated inside each Part below.
Inputs are well-formed (valid indices/ranges); you do not need to validate I/O format unless a Part says otherwise.
"Latest" / "greatest" always refer to the numerically largest value.
Clarifying Questions to Ask Guidance
For the LIS task, is "increasing"
strict
(
<
) or non-strict (
≤
)? (It is strict here.) And must I return the actual indices, or only the length?
For the range-query task, are array values and the added deltas integers that can be negative, and can sums exceed 32-bit range (do I need 64-bit accumulation)?
For the scheduler task, are indices/timestamps 0-based? What is returned when no release qualifies, and can two releases share the same timestamp?
Is each release consumable (assigned to at most one window), and does "earlier window" mean earlier in the
input order
of
windows
, not sorted order?
Are duplicate values allowed in any of the input arrays?
Part 1 — Movie Ratings (Longest Increasing Subsequence)
Given an integer array ratings of length n, return both:
(a) the length of the
longest strictly increasing subsequence
(LIS), and
(b)
one
valid LIS expressed as a list of
1-based indices
into
ratings
(the indices must be strictly ascending and the corresponding values strictly increasing).
Explain your DP formulation (state and transition) and provide code.
Constraints: 1≤n≤200,000; each ratings[i] is any 32-bit signed integer. Target: O(nlogn) time, O(n) memory.
Part 2 — Array Challenge (Point Update + Range Sum)
You are given n and an initial array a[1..n], followed by q operations of two kinds:
add i x
— add integer
x
to
a[i]
.
sum l r
— output
∑k=lra[k]
(inclusive).
Constraints: 1≤n,q≤200,000. A naive O(n)-per-query scan times out. Implement an O(logn)-per-operation solution.
What This Part Should Cover Guidance
A correct Fenwick (or segment) tree with
O(logn)add
and prefix-sum, and the
prefix(r) - prefix(l-1)
decomposition for range sum.
1-based indexing discipline and an
O(n)
or
O(nlogn)
build.
Awareness that values/deltas may be negative and sums may exceed 32-bit, requiring wide accumulation.
Part 3 — Update Release Scheduler
You receive two unsorted integer lists: releases[0..n-1] (timestamps at which builds become available) and windows[0..m-1] (deployment windows). Produce schedule[0..m-1] where schedule[j] is the timestamp of the greatest release ≤ windows[j] that has not been assigned to any earlier window (earlier = smaller index j in the original windows order). Each release may be assigned to at most one window. If no unassigned release ≤ windows[j] exists, set schedule[j] = -1. Output is in the original windows order.
Clarifying Questions for this Part Guidance
Does "earlier window" mean earlier input index, or earlier
sorted
position? (Input index — this changes the algorithm.)
If two available releases tie at the same timestamp
≤ w
, does it matter which one is consumed? (No — they're interchangeable, but one is still consumed.)
What This Part Should Cover Guidance
Recognizing this as
predecessor-with-deletion
over a multiset of releases, processed in input-window order.
A correct
O((n+m)logn)
structure (Fenwick-over-ranks, or a balanced/sorted multiset) for predecessor + delete.
Explicit handling of the
-1
(no qualifying release) case and consumed-once semantics; correctly distinguishing this from the simpler global two-pointer matching.
What a Strong Answer Covers Guidance
Across all three parts, a strong submission demonstrates: matching each target complexity (with a one-line justification), not just producing correct output; clean, idiomatic Python using bisect/Fenwick rather than ad-hoc O(n) scans; and disciplined handling of indexing conventions (0- vs 1-based), negative values, duplicates, and empty inputs. The candidate should be able to state the invariant or state/transition that makes each algorithm correct, and reason about where naive approaches blow up at n,q,m≈2×105.
Follow-up Questions Guidance
Part 1: If ties counted as increasing (non-strict LIS), what single change makes the code correct, and how would you additionally return the
count
of distinct LIS?
Part 2: How would you extend the Fenwick tree to support
range-add, range-sum
in
O(logn)
(two BITs)?
Part 3: Suppose each window could consume
up to k
releases (the
k
greatest available
≤ w
). How does your structure change, and what is the new complexity?
General: For Part 3, under what added assumption (e.g. windows already sorted, or "earliest available" instead of "greatest ≤ w") does a pure two-pointer sweep become correct and drop the log factor?