Problem 425861 · medium · Phase 04 Non-Linear Data Structures

Seat Map With Snapshots

design · binary search · versioning · classes

A ticketing system keeps an array of n seat prices and lets staff freeze the current prices as numbered snapshots. Design a class SeatMap:

  • SeatMap(n) creates n slots (indices 0 to n - 1), all holding 0.
  • set(i, val) changes slot i to val in the live array.
  • snap() freezes the live array and returns the snapshot id: 0 for the first call, then 1, 2, ...
  • get(i, snap_id) returns the value slot i had when snapshot snap_id was taken. snap_id is always an id that snap() has already returned.

Examples

ops:  ["SeatMap", "set", "snap", "set", "set", "get", "snap", "get", "get", "get"]
args: [[3], [0, 7], [], [0, 9], [2, 4], [0, 0], [], [0, 1], [2, 0], [1, 1]]
Output: [None, None, 0, None, None, 7, 1, 9, 0, 0]
Explanation: snapshot 0 saw slot 0 = 7; the later changes only show up in snapshot 1.
Slot 2 was still 0 in snapshot 0, and slot 1 was never changed.

Constraints

  • 1 <= n <= 10**4, 0 <= i < n, values are integers
  • Up to 10**4 calls in total
  • Target: set and snap in O(1), get in O(log c) where c is the number of changes to slot i; copying the array on every snap is too slow and too big

Goals

  • Store only the changes to each slot instead of copying the whole array per snapshot
  • Find the value of a slot at an old snapshot with binary search
Starting Python…