Katkat
Back

Design credit balance with vector-clock expirations

OpenAISoftware Engineer · Technical Screen
HardSoftware EngineerTechnical ScreenSystem Design

Last updated

This question evaluates understanding of distributed-systems concepts such as vector clocks, partial orders, concurrency control and idempotency, plus practical competencies in data structures and algorithms for efficient per-user state management and correctness under concurrent operations.

Design and implement a credit balance service that processes a stream of operations for each user. Operations: (

  1. add(userId, creditId, amount, expiryVc) adds credits with an expiry time represented by a vector clock; (
  2. use(userId, amount, atVc) spends credits at logical time 'atVc'. Rules: spending must consume from the credits that expire soonest; any credit whose expiryVc is <= atVc is unavailable; expired credits cannot be used. Assume every operation is tagged only with a vector clock; wall-clock time is not used. Specify APIs, core data structures, and algorithms to support efficient inserts and spends across many active credits. Explain how you compare vector-clock expiries with 'atVc' and impose a deterministic ordering when vector clocks are partially ordered (e.g., tie-break policies). Describe safeguards against double-spend and against using expired credits, and how to handle identical expiries. Provide complexity analysis and walk through test cases, including tricky edge cases (concurrent expiries, expiry exactly at 'atVc', zero/negative amounts, insufficient balance).