You’re building an offline-first notes feature for a fintech super-app with 10M+ DAUs. Users can edit notes while offline (subway, airplane mode). When connectivity returns, the client must sync local edits with the server without corrupting data—incorrect merges can cause compliance issues (e.g., audit trails) and user trust loss.
Each note is a key-value pair: note_id -> text. Both the device and server produce operations while disconnected. Your job is to implement a deterministic conflict resolver that:
Each operation is a dict with fields:
note_id: strtext: str (the full new text after the edit)device_id: str (who produced it)seq: int (monotonically increasing per device_id)ts: int (client/server timestamp; may be skewed)The server maintains a version vector server_seen[device_id] = max seq applied from that device.
For each note_id, consider all operations from both sides:
seq <= server_seen[device_id] is already on the server and must not be uploaded.(ts ASC, device_id ASC, seq ASC).text.Return:
final_state: dict mapping note_id -> text after merging.to_upload: list of local operations (original dicts) that are not yet on the server, sorted by the same deterministic order.Input
server_state = {"n1": "hello"}server_seen = {"A": 1}server_ops = [{note_id:"n1", text:"hello!", device_id:"A", seq:1, ts:10}]local_ops = [{note_id:"n1", text:"HELLO", device_id:"B", seq:1, ts:9}]Output
final_state = {"n1": "hello!"}to_upload = [{... device_id:"B", seq:1 ...}]Explanation
Local op from B is not seen by server, so it must upload. Merge order applies B@ts=9 then A@ts=10, so final text is "hello!".
Input
server_seen = {"A": 3}local_ops includes {device_id:"A", seq:2, ...} and {device_id:"A", seq:4, ...}Output
to_upload includes only seq:4Explanation
seq:2 is causally included on server (2 <= 3) and must be dropped.
1 <= len(local_ops), len(server_ops) <= 2 * 10^51 <= number of distinct note_id <= 2 * 10^51 <= seq <= 10^90 <= ts <= 10^12device_id and note_id are non-empty stringsserver_state is the state before applying server_ops; you must apply server_ops as part of the merge.server_ops are consistent with server_seen (i.e., server has applied them).