Quick Overview

This question evaluates the ability to design a timestamped key-value data structure, testing competencies in time-based indexing, ordered retrieval, and data structure selection for efficient timestamp queries.

Design timestamped key-value map

Company: Character.AI

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

##### Question Design a class that supports insert(key, value, timestamp) and get(key, timestamp) where get returns the value whose timestamp is the smallest timestamp ≥ the given timestamp, assuming inserts arrive in increasing timestamp order. Follow-up: How would you change the design if inserts arrive out of order (timestamps not strictly increasing)?

Overview: This question evaluates the ability to design a timestamped key-value data structure, testing competencies in time-based indexing, ordered retrieval, and data structure selection for efficient timestamp queries.

Implement a function to process operations on a timestamped key-value map. It supports two operations: (1) insert(key, value, timestamp): store the value for key at the given timestamp; (2) get(key, timestamp): return the value for key whose timestamp is the smallest timestamp greater than or equal to the given timestamp. If no such timestamp exists for the key, return null. Assume that all insert operations arrive in nondecreasing timestamp order across all keys. The function should return a list of results for all get operations in the order they appear.

Constraints

  • 1 <= len(operations) <= 200000
  • Each operation is either ["insert", key:str, value:str, timestamp:int] or ["get", key:str, timestamp:int]
  • All insert operations appear in nondecreasing timestamp order (timestamps may be equal)
  • 0 <= timestamp <= 1e9
  • 1 <= len(key), len(value) <= 50
  • The function returns results for get operations only; insert operations produce no direct output

Hints

  1. Map each key to a sorted list of timestamps and a parallel list of values.
  2. Because inserts are in nondecreasing timestamp order, you can append to each key's lists to keep them sorted.
  3. Use binary search (bisect_left) on the timestamps list to find the first index with timestamp >= query.
  4. If inserts were out of order, maintain each key's timestamps in sorted order via bisect.insort or use a balanced BST.

Loading coding console...

Show the approach

Approach

Maintain, for each key, a pair of parallel arrays: timestamps (sorted) and values. Because all inserts arrive in nondecreasing timestamp order, appending keeps the timestamps sorted. For a get(key, t) query, perform a binary search with bisect_left to find the smallest index i such that timestamps[i] >= t; if it exists, return values[i]; otherwise return None. If inserts arrive out of order, you would insert timestamps and values at the appropriate positions using bisect.insort (O(log m) per insert plus O(m) shifts in arrays) or use a balanced tree/skip list to keep inserts and queries both O(log m), where m is the number of entries for that key.

Time complexity:
Insert: O(1) amortized per operation (append); Get: O(log m) per query where m is the number of entries for the key
Space complexity:
O(N) where N is the total number of inserted entries