Find First Diverging Execution Log | Dataford Interview Questions

Your question is Find First Diverging Execution Log. Start with the requirements on the right.

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

During debugging in One Drop services, a useful first step is finding where an observed execution trace stops matching the expected control flow. Given two execution logs as arrays of strings, return the earliest event index where they diverge after normalizing nested function scopes.

Each log entry is one of:

"CALL:name" — enter a function scope
"RETURN:name" — exit a function scope
"SET:key=value" — record a state update in the current scope

Two logs are considered equivalent up to an index if, after processing entries in order, they produce the same stack of active function calls and the same latest values for keys visible in the current scope chain. Return the smallest index i where the states differ immediately after processing expected[i] and observed[i]. If the logs have different lengths but match through the shorter one, return the shorter length. If they never diverge, return -1.

Formal Specification

Implement find_first_divergence(expected, observed) where:

expected: list of strings
observed: list of strings
Returns: integer divergence index

Constraints

0 <= len(expected), len(observed) <= 10^4
Each log entry has length between 1 and 100
Function names and keys are non-empty alphanumeric strings
Each individual log is well-formed, except mismatched returns may still appear and should be treated as divergence

Function Signature

def find_first_divergence(expected, observed):