Implement pagination and a time-versioned key-value store

Q: Implement pagination and a time-versioned key-value store

This question evaluates proficiency in data structures, algorithms, and API design for stateful systems, focusing on cursor-based pagination stability and time-versioned key-value storage with efficient time-travel reads, and is categorized under coding & algorithms with overlaps into data structures and systems design.

Q: How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

Q: What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Lyft.

Q: What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Lyft during technical interviews.

Question

Implement two coding tasks:
1) Transaction pagination: Given an in-memory collection of transaction records with fields (txn_id: string, user_id: string, amount: int, created_at: int epoch seconds), implement a cursor-based pagination API get_page(user_id, page_size, cursor) -> {items, next_cursor}. Return transactions for the user ordered by created_at descending, breaking ties by txn_id ascending. The cursor must be opaque and ensure stable pages even if new transactions are inserted after earlier pages are fetched (no duplicates or skips). Explain your data structures, cursor encoding/decoding, and the time/space complexity.
2) Time-versioned key-value store: Design and implement a store with set(key, value, t) and get(key, t) that returns the value with the greatest timestamp ≤ t, or null if none exists. Optimize for heavy reads (millions of queries). Choose data structures to achieve O(log n) per operation per key, handle duplicate timestamps deterministically, and discuss memory trade-offs and concurrency safety for readers.

PracHub · Accepted Answer

def solution(transactions, user_id, page_size, cursor): from bisect import bisect_right if page_size <= 0: return {'items': [], 'next_cursor': None} user_txns = [txn for txn in transactions if txn[1] == user_id] user_txns.sort(key=lambda txn: (-txn[3], txn[0])) start = 0 if cursor is not None: created_at_str, last_txn_id = cursor.split('|', 1) cursor_key = (-int(created_at_str), last_txn_id) keys = [(-txn[3], txn[0]) for txn in user_txns] start = bisect_right(keys, cursor_key) page = user_txns[start:start + page_size] if not page or start + page_size >= len(user_txns): next_cursor = None else: last = page[-1] next_cursor = f'{last[3]}|{last[0]}' return {'items': page, 'next_cursor': next_cursor} def solution(operations): MASK = (1 << 64) - 1 def fnv1a(text): h = 1469598103934665603 for ch in text: h ^= ord(ch) h = (h * 1099511628211) & MASK return h def mix64(x): x = (x + 0x9E3779B97F4A7C15) & MASK x = ((x ^ (x >> 30)) * 0xBF58476D1CE4E5B9) & MASK x = ((x ^ (x >> 27)) * 0x94D049BB133111EB) & MASK x ^= x >> 31 return x & MASK class Node: __slots__ = ('ts', 'value', 'prio', 'left', 'right') def __init__(self, ts, value, prio): self.ts = ts self.value = value self.prio = prio self.left = None self.right = None def rotate_right(y): x = y.left y.left = x.right x.right = y return x def rotate_left(x): y = x.right x.right = y.left y.left = x return y def insert(node, ts, value, prio): if node is None: return Node(ts, value, prio) if ts == node.ts: node.value = value return node if ts < node.ts: node.left = insert(node.left, ts, value, prio) if node.left.prio < node.prio: node = rotate_right(node) else: node.right = insert(node.right, ts, value, prio) if node.right.prio < node.prio: node = rotate_left(node) return node def floor_get(node, ts): ans = None cur = node while cur is not None: if ts < cur.ts: cur = cur.left else: ans = cur.value cur = cur.right return ans roots = {} seeds = {} out = [] for op in operations: if op[0] == 'set': _, key, value, ts = op if key not in seeds: seeds[key] = fnv1a(key) prio = mix64(ts ^ seeds[key]) roots[key] = insert(roots.get(key), ts, value, prio) else: _, key, ts = op out.append(floor_get(roots.get(key), ts)) return out

Quick Overview

Solution

Hints

Part 2: Time-Versioned Key-Value Store

Constraints

Examples

Solution

Hints

Quick Overview