Realign Drifting Subtitles

Treat the anchors as a piecewise-linear map from observed time to correct time. For each cue time, binary search the sorted anchors for the segment around it and interpolate along that segment; before the first anchor or after the last, extend the nearest segment. A single anchor is a constant shift. O(log m) per time for m anchors.

mediumPattern: Binary search·From Devana's Netflix question set

Problem

After a re-encode, a film's subtitles drift out of sync with the audio. Sometimes the error is a constant offset; sometimes it grows through the film, which is what a frame rate change does. You have the subtitle cues and a few anchors where someone has marked the correct time.

Write realign_subtitles(cues, anchors). Each cue is a dict with start and end in seconds plus other fields that pass through unchanged. Each anchor is (observed, correct). Return the corrected cues.

def realign_subtitles(cues: list[dict], anchors: list[tuple[float, float]]) -> list[dict]:

This is one of Devana's own questions, written in the style of Netflix's interviews. It is not a question leaked from Netflix, and Devana is not affiliated with Netflix.

Constraints

• Anchors have distinct observed times and may arrive unsorted.
• Between two anchors the correction is linear. Before the first or after the last anchor, the nearest segment's line continues.
• A single anchor gives a constant offset. With no anchors, cues come back unchanged.
• Start and end are corrected independently, so a cue's duration stretches when the drift does.
• Up to 10^5 cues and 10^3 anchors; results are rounded to 6 decimal places.

Examples

Input:  cues = [{"start": 600, "end": 602, "text": "a"}]
        anchors = [(600, 599.5), (3600, 3599.5)]
Output: [{"start": 599.5, "end": 601.5, "text": "a"}]

Input:  cues = [{"start": 150, "end": 250}]
        anchors = [(0, 0), (100, 100), (200, 250)]
Output: [{"start": 175, "end": 325}]

Hints

Open one at a time, and try the problem again after each.

Approach: from brute force to optimal

How to say it in the interview

Say "piecewise-linear interpolation" early; it tells the interviewer you have recognized the shape. Then explain how you find the segment, why the end segments extend, and that one anchor is a pure shift. Point out that start and end are corrected separately, which is why durations can change.

Solution

Python

from bisect import bisect_right

def realign_subtitles(cues, anchors):
    points = sorted(anchors)
    if not points:
        return [dict(cue) for cue in cues]
    observed = [x for x, _ in points]

    def correct(t):
        if len(points) == 1:
            return t + points[0][1] - points[0][0]
        # The segment starts at the last anchor at or before t, clamped so
        # times outside the anchors extend the first or last segment.
        i = min(max(bisect_right(observed, t) - 1, 0), len(points) - 2)
        (x0, y0), (x1, y1) = points[i], points[i + 1]
        return y0 + (t - x0) * (y1 - y0) / (x1 - x0)

    fixed = []
    for cue in cues:
        moved = dict(cue)                  # every other field passes through
        moved["start"] = round(correct(cue["start"]), 6)
        moved["end"] = round(correct(cue["end"]), 6)
        fixed.append(moved)
    return fixed

JavaScript

function realignSubtitles(cues, anchors) {
  const points = [...anchors].sort((p, q) => p[0] - q[0]);
  if (points.length === 0) return cues.map((cue) => ({ ...cue }));

  const correct = (t) => {
    if (points.length === 1) return t + points[0][1] - points[0][0];
    // The first anchor after t; the segment starts one before it, clamped.
    let lo = 0, hi = points.length;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (points[mid][0] <= t) lo = mid + 1;
      else hi = mid;
    }
    const i = Math.min(Math.max(lo - 1, 0), points.length - 2);
    const [x0, y0] = points[i];
    const [x1, y1] = points[i + 1];
    return y0 + (t - x0) * (y1 - y0) / (x1 - x0);
  };

  const round6 = (x) => Math.round(x * 1e6) / 1e6;
  return cues.map((cue) => ({ ...cue, start: round6(correct(cue.start)), end: round6(correct(cue.end)) }));
}

Both versions are tested against the same cases, including every example on this page.

• The binary search finds the first anchor after t; one before it is where the segment starts. Clamping handles both ends at once.
• Each cue is copied before it is changed, which leaves the caller's list intact and passes every other field through.
• At an anchor, both neighboring segments give the same answer, so it does not matter which one the search picks.

Follow-up questions

Common mistakes

• Applying the average offset to everything, which leaves the start and end of the film wrong in opposite directions when the drift grows.
• Leaving cues before the first anchor uncorrected, which puts a visible jump at that anchor.
• Moving the end by the start's correction, so durations never stretch.
• Binary searching anchors that were never sorted.

Practice it in a mock interview

Reading a solution and explaining one under questioning are different skills. The button below starts this problem as a voice mock interview with Josh, Devana's AI interviewer, with an editor that runs your code.

Practice this problem in a mock interview

Related problems

• Consistent Hashing for a Cache Tier: Virtual nodes on a sorted ring; each key belongs to the first position at or after its hash.
• Time-Weighted Moving Average over Irregular Ticks: A time-based window with a running area, evicting from the front as ticks age out.
• Binary search: the pattern guide, with more practice questions.