Diff Two Enormous Sorted Indexes

Walk both sorted streams together, like the merge step of merge sort. If the current IDs match, the document is unchanged and both streams advance. Otherwise the smaller ID exists in only one list: removed if it came from the old index, added if it came from the new one. One pass over each stream and O(1) memory.

mediumPattern: Two pointers·From Devana's Google question set

Problem

Yesterday's and today's document index are each a list of document IDs sorted ascending. You need the IDs that were added and the IDs that were removed.

Neither list fits in memory, so you can stream through each one only once, holding a constant number of IDs at a time. Write diff_indexes(old_stream, new_stream) as a generator that yields ("added", id) and ("removed", id) events in ID order.

def diff_indexes(old_stream, new_stream):
    """Yield ("added", id) and ("removed", id) in ID order."""

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

Constraints

• Each stream is sorted ascending and contains no repeated IDs.
• Up to 10^10 IDs per stream, so nothing proportional to the input fits in memory.
• One pass over each stream, holding O(1) IDs at a time.
• IDs present in both streams produce no event.

Examples

Input:  old = [1, 2, 5], new = [2, 3, 5]
Output: ("removed", 1), ("added", 3)

Input:  old = [], new = [7, 8]
Output: ("added", 7), ("added", 8)

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

Mention the set difference first, then why it fails: ten billion IDs do not fit in memory. Name the pattern, a merge walk, and give the one-sentence invariant: the smaller current ID cannot appear later in the other stream, because that stream only goes up. That sentence is what interviewers listen for.

Solution

Python

def diff_indexes(old_stream, new_stream):
    old_it, new_it = iter(old_stream), iter(new_stream)
    done = object()                      # marks a finished stream
    a, b = next(old_it, done), next(new_it, done)
    while a is not done or b is not done:
        if b is done or (a is not done and a < b):
            yield ("removed", a)         # the new stream is already past a
            a = next(old_it, done)
        elif a is done or b < a:
            yield ("added", b)           # the old stream is already past b
            b = next(new_it, done)
        else:                            # in both: unchanged
            a, b = next(old_it, done), next(new_it, done)

JavaScript

function* diffIndexes(oldStream, newStream) {
  const oldIt = oldStream[Symbol.iterator]();
  const newIt = newStream[Symbol.iterator]();
  let a = oldIt.next();
  let b = newIt.next();
  while (!a.done || !b.done) {
    if (b.done || (!a.done && a.value < b.value)) {
      yield ["removed", a.value]; // the new stream is already past it
      a = oldIt.next();
    } else if (a.done || b.value < a.value) {
      yield ["added", b.value]; // the old stream is already past it
      b = newIt.next();
    } else {
      a = oldIt.next(); // in both: unchanged
      b = newIt.next();
    }
  }
}

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

• Both versions accept any iterable, so a file reader or a network stream works as well as a list.
• Python uses a private sentinel object rather than None for a finished stream, so no ID can be mistaken for the end.
• As generators, they emit events as they go; the caller can write them out without collecting them.

Follow-up questions

Common mistakes

• Loading either stream into a set or a list.
• Stopping when the shorter stream ends and never draining the other.
• Using a falsy check for the end of a stream, which breaks on an ID of 0.
• Advancing only one stream when the IDs match, which reports the same document as both removed and added.

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

• Reach a Promotion Threshold from a Cart: Sort once, binary search for a single item, then walk two pointers inward for the cheapest pair.
• Compute a Diff Between Two File Versions: A longest common subsequence table over lines, then a walk that turns it into keep, delete and insert.
• Two pointers: the pattern guide, with more practice questions.