Missing Element From Sorted Arrays | Dataford Interview Questions

A dunnhumby retail data pipeline compares two sorted snapshots of integer identifiers. The first snapshot contains every value, while the second contains the same multiset with exactly one occurrence removed. Find the missing value without modifying either array.

Your solution must handle duplicate values, negative values, and a missing value at any position. Because the arrays may be very large, target O(log n) time and O(1) additional space.

Formal Specification

Implement find_missing(first, second):

Input: first, an ascending nondecreasing list of integers with length n; second, an ascending nondecreasing list of integers with length n - 1.
Output: The integer whose one occurrence appears in first but not in second.
The arrays represent multisets, so duplicate values are valid.

Constraints

1 <= len(first) <= 10^7
len(second) = len(first) - 1
Both arrays are sorted in nondecreasing order
Values are integers in [-10^9, 10^9]
Exactly one occurrence is missing from second

Function Signature

def find_missing(first, second):

Your question is Missing Element From Sorted Arrays. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem