Solve movie ratings, array, release scheduler
Company: DRW
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Onsite
##### Question
LeetCode 135. Candy – Distribute the minimum number of candies (stars) so that each movie gets at least one star and any movie with a higher rating than an adjacent movie gets more stars than that neighbor. Array Challenge – Optimize an algorithm whose current time-complexity limits performance; design a solution that leverages an appropriate tree data structure to achieve faster operations. Update Release Scheduler – Given two lists of version release dates, sort each list and then compare them to produce the combined chronological release schedule.
https://leetcode.com/problems/candy/description/
Quick Answer: This question tests algorithmic problem-solving across three domains: greedy array optimization, tree-based data structure design, and efficient sequence merging. It evaluates practical coding ability and complexity analysis, commonly used in quantitative and data science interviews to assess how candidates identify inefficiencies and select the right data structure to improve performance.
Solution
# Solution
This screen bundles three independent problems. For each I give the brute-force baseline, the optimal approach, runnable code, complexity, and edge cases. The connective tissue across all three is the same habit: state the naive cost, find the repeated work, and remove it with the right pass or data structure.
---
## Part 1 — Candy / Star Distribution (LeetCode 135)
### Restating the rules
Give each movie at least one star; any movie with a **strictly higher** rating than an **adjacent** movie must get **strictly more** stars than that neighbor. Minimize the total. Equal adjacent ratings impose **no** constraint.
### Why naive is slow
A fixpoint loop that repeatedly scans the array bumping any violated index until nothing changes is $O(n^2)$ worst case (a strictly increasing then decreasing ridge propagates one index per pass).
### Key insight
Each index has two independent constraints — one from its **left** neighbor, one from its **right** neighbor. Decouple them:
1. **Left-to-right pass:** if `ratings[i] > ratings[i-1]`, then `left[i] = left[i-1] + 1`, else `left[i] = 1`.
2. **Right-to-left pass:** if `ratings[i] > ratings[i+1]`, then `right[i] = right[i+1] + 1`, else `right[i] = 1`.
3. **Combine:** the answer at each index must satisfy *both* constraints, so take `max(left[i], right[i])`. Sum it.
Taking the `max` is what guarantees minimality: any smaller value would violate one of the two directional rises.
### Two-pass implementation — $O(n)$ time, $O(n)$ space
```python
def candy(ratings: list[int]) -> int:
n = len(ratings)
if n == 0:
return 0
left = [1] * n
right = [1] * n
# rises from the left
for i in range(1, n):
if ratings[i] > ratings[i - 1]:
left[i] = left[i - 1] + 1
# rises from the right
for i in range(n - 2, -1, -1):
if ratings[i] > ratings[i + 1]:
right[i] = right[i + 1] + 1
# each index needs the larger of the two demands
return sum(max(left[i], right[i]) for i in range(n))
```
Trace `ratings = [1, 0, 2]`: `left = [1, 1, 2]`, `right = [2, 1, 1]`, per-index max `[2, 1, 2]` → total `5`. For `[1, 2, 2]`: `left = [1, 2, 1]`, `right = [1, 1, 1]`, max `[1, 2, 1]` → `4`.
### Optimal-space variant — $O(n)$ time, $O(1)$ extra space (follow-up)
Walk once, counting the length of each ascending `up` run and descending `down` run, with `peak` tracking the last up-run length. A descent of length `d` needs `1 + 2 + ... + d` extra stars; when the descent grows past the peak, the peak itself must be raised by one more.
```python
def candy_o1(ratings: list[int]) -> int:
n = len(ratings)
if n <= 1:
return n
total = 1 # first movie gets 1
up = down = peak = 0
for i in range(1, n):
if ratings[i] > ratings[i - 1]:
up += 1; down = 0; peak = up
total += 1 + up
elif ratings[i] == ratings[i - 1]:
up = down = peak = 0
total += 1
else:
up = 0; down += 1
# the descending tail costs 1..down; if it overtakes the
# peak, the peak must be bumped (the +1 below covers it)
total += 1 + down - (1 if peak >= down else 0)
return total
```
### Complexity and edge cases
- Two-pass: $O(n)$ time, $O(n)$ space. Single-pass: $O(n)$ time, $O(1)$ extra space.
- Edge cases: empty array → `0`; single movie → `1`; all-equal ratings → `n` (every neighbor is equal, so everyone gets exactly 1); strictly monotonic arrays → triangular sums.
---
## Part 2 — Array Challenge: Beat $O(n^2)$ with a Fenwick Tree
### The concrete problem
"Count of smaller numbers after self": given `nums`, return `counts` where `counts[i]` is the number of indices `j > i` with `nums[j] < nums[i]`.
### Why naive is slow
The double loop — for each `i`, scan the suffix and tally smaller elements — is $O(n^2)$. The wasted work is re-scanning overlapping suffixes; the same values are inspected over and over.
### Key insight
Process the array **right to left**. As we move left, every element we have already seen lies to the right of the current one. So the question becomes: *among the values seen so far, how many are strictly smaller than the current value?* That is a **prefix-count over the value domain**, which a **Binary Indexed Tree (Fenwick tree)** answers and updates in $O(\log n)$.
Because values can be large or negative, first **coordinate-compress** them to dense ranks $[1..k]$ (the Fenwick tree is 1-indexed). "Strictly smaller" means we query the prefix sum up to `rank - 1`.
### Implementation — $O(n \log n)$ time, $O(n)$ space
```python
class BIT:
def __init__(self, size: int):
self.tree = [0] * (size + 1) # 1-indexed
def update(self, i: int, delta: int = 1) -> None:
while i < len(self.tree):
self.tree[i] += delta
i += i & (-i)
def query(self, i: int) -> int: # prefix sum of [1..i]
s = 0
while i > 0:
s += self.tree[i]
i -= i & (-i)
return s
def count_smaller(nums: list[int]) -> list[int]:
if not nums:
return []
# coordinate compression -> rank in [1..k]
sorted_vals = sorted(set(nums))
rank = {v: i + 1 for i, v in enumerate(sorted_vals)}
bit = BIT(len(sorted_vals))
counts = [0] * len(nums)
for i in range(len(nums) - 1, -1, -1):
r = rank[nums[i]]
counts[i] = bit.query(r - 1) # strictly smaller already seen
bit.update(r, 1) # record current value
return counts
```
Trace `nums = [5, 2, 6, 1]`. Ranks: `1→1, 2→2, 5→3, 6→4`. Sweeping right→left:
`1`: query rank 0 → 0, add rank 1. `6`: query rank 3 → 1 (only the `1` seen), add rank 4. `2`: query rank 1 → 1, add rank 2. `5`: query rank 2 → 2 (`1` and `2` seen), add rank 3. Result `[2, 1, 1, 0]`. Correct.
### Duplicate-value boundary
"Strictly smaller" ⇒ query `rank - 1` (excludes equal values). If the problem asked for "smaller **or equal**," you would query `rank` instead. Getting this boundary right under duplicates is the most common bug.
### Alternative: merge-sort counting
The same result comes from a modified merge sort: while merging two sorted halves, when an element from the left half is placed *after* `c` elements from the right half have already been emitted, those `c` right-half elements are smaller-and-to-the-right of it, so add `c` to that element's count. Also $O(n \log n)$, and — importantly — its merge step is exactly the routine in Part 3.
### Complexity and edge cases
- Fenwick: $O(n \log n)$ time (each of `n` elements does one $O(\log k)$ query + update), $O(n)$ space.
- Edge cases: empty input → `[]`; all-equal values → all-zero counts (no value is strictly smaller); already-sorted ascending → all zeros; descending → `[n-1, n-2, …, 0]`. Negative and large values are handled by the compression step.
### Variant: count *greater* to the right (follow-up)
Query `total_seen - bit.query(r)` (everything seen minus those `≤` current), or equivalently build the BIT over reversed ranks. For an **online stream**, the same BIT supports inserting one element at a time and querying the running smaller-count in $O(\log k)$ per arrival, provided the value domain (or its compression) is known up front; otherwise use an order-statistics balanced BST.
---
## Part 3 — Update Release Scheduler: Merge Two Sorted Date Lists
### The problem
Given two lists of release dates `a` and `b`, sort each, then merge into one ascending chronological schedule.
### Key insight
Sorting the concatenation is $O((m+n)\log(m+n))$. But once each list is individually sorted, the two can be combined with a **two-pointer linear merge** — the merge step from merge sort — in $O(m + n)$.
ISO `YYYY-MM-DD` strings have the convenient property that lexicographic (string) order equals chronological order, so no parsing is needed for that format. For any other format, parse to a `date`/epoch first and compare on that.
### Implementation — $O(m\log m + n\log n)$ sort, then $O(m+n)$ merge
```python
def merge_release_schedule(a: list[str], b: list[str]) -> list[str]:
a = sorted(a) # ISO YYYY-MM-DD sorts chronologically as text
b = sorted(b)
merged: list[str] = []
i = j = 0
while i < len(a) and j < len(b):
if a[i] <= b[j]: # <= keeps it stable and keeps duplicates
merged.append(a[i]); i += 1
else:
merged.append(b[j]); j += 1
merged.extend(a[i:]) # drain the remainder
merged.extend(b[j:])
return merged
```
Trace `a = ["2024-03-01", "2024-01-15"]`, `b = ["2024-02-10"]`. After sort: `a = ["2024-01-15", "2024-03-01"]`, `b = ["2024-02-10"]`. Merge: `"2024-01-15"` < `"2024-02-10"` → take a; `"2024-03-01"` > `"2024-02-10"` → take b; drain `"2024-03-01"`. Result `["2024-01-15", "2024-02-10", "2024-03-01"]`.
### Handling non-ISO formats
```python
from datetime import datetime
def parse(d: str) -> datetime:
return datetime.strptime(d, "%m/%d/%Y") # e.g. "03/01/2024"
# sort with key=parse, and compare parse(a[i]) <= parse(b[j]) in the merge
```
### Duplicates
The `<=` comparison keeps cross-list duplicate dates (both releases on the same day appear twice), which is usually what a release schedule wants. To de-duplicate, skip appending a date equal to the last one already in `merged`.
### Complexity and edge cases
- Sorting dominates: $O(m\log m + n\log n)$; the merge is $O(m + n)$ with $O(m + n)$ output space.
- Edge cases: one or both lists empty (the drain handles it); all dates identical; already-sorted inputs (sort still $O(n\log n)$ but the merge is clean); mixed formats should be normalized before comparison.
### Merging `k` lists (follow-up)
Replace the two-pointer merge with a **min-heap** of the current heads of all `k` sorted lists: pop the smallest, push the next from the same list. Total cost $O(N \log k)$ where $N$ is the combined length — strictly better than concatenate-and-sort's $O(N \log N)$ when `k ≪ N`.
---
## Cross-cutting summary
| Part | Naive | Optimal | Optimal complexity |
|------|-------|---------|--------------------|
| 1 — Candy | $O(n^2)$ fixpoint | two directional passes + per-index `max` | $O(n)$ time, $O(n)$ (or $O(1)$) space |
| 2 — Count smaller after self | $O(n^2)$ double loop | right-to-left Fenwick over compressed ranks | $O(n \log n)$ time, $O(n)$ space |
| 3 — Merge release dates | $O((m+n)\log(m+n))$ concat-sort | sort each + two-pointer merge | $O(m\log m + n\log n)$ + $O(m+n)$ |
The unifying lesson DRW is probing for: in every part the speedup comes from **separating concerns** — left vs. right constraints, value-domain bookkeeping vs. iteration order, and sort vs. merge. The merge-sort counting variant of Part 2 even reuses Part 3's merge step verbatim, which is the connection the interviewer is likely fishing for.