Solve movie ratings, array, release scheduler

Question

This is a three-part coding screen used for a Data Scientist role at DRW. You will work through three independent array/sequence problems, each progressively exercising a different algorithmic skill: greedy local reasoning, choosing the right data structure to beat a slow baseline, and merging ordered sequences. Treat each part as self-contained; an interviewer typically expects working code plus a clear statement of time and space complexity for each.

Constraints & Assumptions

• All three parts are standard whiteboard / online-judge style problems; no external libraries beyond the language standard library.
• Inputs fit in memory. Aim for the best asymptotic complexity, then discuss constants only if asked.
• Where the problem statement is loose (Part 2 in particular), you are expected to pin down the exact operations you are optimizing before writing code.

Clarifying Questions to Ask

• What are the input size bounds for each part (do we need an $O(n)$/$O(n \log n)$ solution, or is $O(n^2)$ acceptable)?
• Are values guaranteed to be integers, and can ratings/dates be equal (ties)? How should ties be handled?
• For Part 3, can the two release-date lists contain duplicates across lists, and should the merged schedule keep duplicates or de-duplicate?
• Is in-place mutation of the inputs allowed, or must the inputs be preserved?

---

Part 1 — Candy / Star Distribution (LeetCode 135)

There are n movies in a row, each with an integer rating. You must hand out "stars" to the movies under these rules:

1. Every movie gets at least one star.
2. A movie with a strictly higher rating than an adjacent movie must receive strictly more stars than that neighbor.

Return the minimum total number of stars you must distribute.

Reference: https://leetcode.com/problems/candy/description/

Example: ratings = [1, 0, 2] → answer 5 (stars [2, 1, 2]). ratings = [1, 2, 2] → answer 4 (stars [1, 2, 1]; equal neighbors have no ordering constraint).

Hint: Where to start

The two adjacency rules are independent in direction. Consider satisfying the left-to-right constraint and the right-to-left constraint separately, then reconciling them.

Hint: Data structure / approach

A greedy two-pass sweep works in $O(n)$ time and $O(n)$ space: one pass left→right, one pass right→left, then combine. Think about what to do at each index when combining the two passes.

Hint: Combining the passes

For each index, the final stars must satisfy both the rise-from-the-left and the rise-from-the-right. Which of the two per-index values do you keep?

What This Part Should Cover

• Recognizing that the left and right neighbor constraints can be decoupled into two directional passes.
• Correct $O(n)$ greedy (or an equivalent single-pass up/down/plateau counting) rather than a quadratic fixpoint loop.
• Handling equal adjacent ratings (no constraint) and the minimization requirement (start everyone at 1).

---

Part 2 — Array Challenge: Beat a Slow Baseline with a Tree

You are given an algorithm whose current time complexity is the bottleneck — the naive approach repeats an expensive scan and runs in $O(n^2)$ (or worse). Redesign it so the core operation becomes a logarithmic-time query/update by choosing an appropriate tree-based data structure.

Concretely: design and implement a solution to the "count smaller elements after self" problem (a canonical instance of this optimization). Given an integer array nums, return an array counts where counts[i] is the number of elements to the right of nums[i] that are strictly smaller than nums[i]. The naive double loop is $O(n^2)$; your solution must do better by leveraging a tree.

Example: nums = [5, 2, 6, 1] → counts = [2, 1, 1, 0].

Hint: Where to start

The naive solution re-scans the suffix for every element. To answer "how many smaller values have I already seen?" quickly, process the array from the right and maintain an order-aware running multiset.

Hint: Data structure

A Binary Indexed Tree (Fenwick tree) or a segment tree over the value domain (coordinate-compress first if values are large/sparse) gives $O(\log n)$ per query+update, i.e. $O(n \log n)$ overall. A balanced-BST / merge-sort-based count is also acceptable.

Hint: Mechanics

Coordinate-compress nums to ranks $[1..k]$. Sweep right→left: for each value, query the prefix sum of counts strictly below its rank, then update (increment) that rank by 1.

Clarifying Questions for this Part

• Is "smaller" strict, and are there duplicate values (which decides whether the Fenwick query is a strict prefix rank-1 or inclusive)?
• Are the integer values bounded (allowing a direct-indexed BIT) or arbitrary (requiring coordinate compression)?

What This Part Should Cover

• Identifying why the baseline is $O(n^2)$ and which repeated work the tree eliminates.
• Correct use of a Fenwick/segment tree (or merge-sort counting) for $O(n \log n)$, including coordinate compression when values are unbounded.
• Getting the strict-vs-inclusive boundary right under duplicate values, and stating the final time/space complexity.

---

Part 3 — Update Release Scheduler: Merge Two Sorted Date Lists

You are given two lists of version release dates, a and b. Produce the combined chronological release schedule: sort each list, then merge them into a single ascending sequence of dates.

A correct but naive approach concatenates and sorts in $O((m+n)\log(m+n))$. A stronger answer recognizes that once each list is sorted, the two can be merged in linear time.

Example: a = ["2024-03-01", "2024-01-15"], b = ["2024-02-10"] → ["2024-01-15", "2024-02-10", "2024-03-01"].

Hint: Where to start

Treat dates as comparable keys (ISO YYYY-MM-DD strings sort lexicographically the same as chronologically; otherwise parse to a date/epoch). After each list is sorted, the merge is the same routine used inside merge sort.

Hint: Merge step

Use two pointers, one per sorted list, repeatedly appending the smaller front element — $O(m + n)$ for the merge after the $O(m\log m + n\log n)$ sorts.

What This Part Should Cover

• Sorting each list correctly (and why ISO date strings compare correctly without parsing, or parsing when the format isn't sortable as text).
• The two-pointer linear merge of two sorted sequences rather than a re-sort of the concatenation.
• A clear decision on duplicate dates across lists (keep both vs. de-duplicate) and stable, total ordering.

---

What a Strong Answer Covers

Across all three parts, a strong candidate demonstrates the same disciplined pattern: state the brute-force baseline and its complexity, identify the wasted/repeated work, then pick the data structure or sweep that removes it — and quantify the improvement.

• Per part: a correct, runnable solution with explicit time/space complexity (Part 1 $O(n)$, Part 2 $O(n \log n)$, Part 3 $O(m\log m + n\log n)$ sort + $O(m+n)$ merge).
• Decoupling directional constraints (Part 1) and decoupling sort from merge (Part 3) — recognizing that two simpler passes beat one tangled pass.
• Justifying the tree choice in Part 2 (Fenwick vs. segment tree vs. merge-sort counting) and the compression step.
• Edge cases throughout: single-element / empty inputs, all-equal values, duplicates, and the strict-vs-non-strict comparison boundaries.

Follow-up Questions

• Part 1: Can you achieve $O(1)$ extra space (no auxiliary arrays) using a single up/down/plateau scan? Sketch how the peak/valley accounting works.
• Part 2: How would you adapt the structure to instead count elements greater than nums[i] to the right, or to support an online stream where elements arrive one at a time?
• Part 2 vs. Part 3: Both Parts 2 and 3 are "inversion / merge" flavored. Explain how the merge-sort counting variant of Part 2 reuses the exact merge step from Part 3.
• Part 3: If you must merge k sorted release lists instead of two, what changes, and what is the resulting complexity?

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

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.

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

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

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

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.