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.

What difficulty level is this coding question?

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

What role is this question designed for?

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

Implement pagination and a time-versioned key-value store

Quick Overview

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.

Company: Lyft

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

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.

Quick Answer: 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.

Part 1: Transaction Pagination with Stable Cursor

You are given an unsorted in-memory list of transaction records. Each record is a 4-tuple: (txn_id, user_id, amount, created_at). Implement cursor-based pagination as a function solution(transactions, user_id, page_size, cursor) that returns a dictionary with keys 'items' and 'next_cursor'. Return only the transactions for the requested user, ordered by created_at descending. If two transactions have the same created_at, break ties by txn_id ascending. The cursor must act like an opaque keyset cursor: the next call should continue strictly after the last item from the previous page, so inserts between calls do not cause duplicates or offset-based skips.

Constraints

0 <= len(transactions) <= 200000
1 <= page_size <= 1000
Each txn_id is unique
created_at is an integer epoch timestamp
cursor is either None or a valid cursor previously produced by the function

Examples

Input: ([('t1', 'u1', 50, 100), ('t3', 'u1', 20, 120), ('t2', 'u1', 70, 120), ('t4', 'u2', 10, 130)], 'u1', 2, None)

Expected Output: {'items': [('t2', 'u1', 70, 120), ('t3', 'u1', 20, 120)], 'next_cursor': '120|t3'}

Explanation: Transactions for u1 are ordered by created_at descending. t2 comes before t3 because they tie on timestamp and txn_id is the tie-breaker.

Input: ([('t1', 'u1', 50, 100), ('t3', 'u1', 20, 120), ('t2', 'u1', 70, 120), ('t4', 'u2', 10, 130), ('t0', 'u1', 99, 200)], 'u1', 2, '120|t3')

Expected Output: {'items': [('t1', 'u1', 50, 100)], 'next_cursor': None}

Explanation: A newer transaction t0 was inserted before the next call, but the cursor resumes after t3, so there is no duplicate and the remaining older item is returned.

Hints

Offset pagination is fragile when new rows appear. Think about resuming from the last seen record instead.
Your ordering key is composite: created_at descending, then txn_id ascending. The cursor must carry enough information to resume after exactly one record.

Part 2: Time-Versioned Key-Value Store

Implement a time-versioned key-value store. You will receive a sequence of operations of two forms: ('set', key, value, t) and ('get', key, t). A get must return the value associated with the greatest timestamp less than or equal to t for that key, or None if no such version exists. Timestamps may arrive out of order. If the same key is set multiple times at the same timestamp, the latest set should deterministically replace the previous value. Return the results of all get operations in order. Aim for O(log v) lookup/update per key, where v is the number of versions for that key.

Constraints

0 <= len(operations) <= 200000
Keys and values are strings
Timestamps are integers and are not guaranteed to be sorted
If the same key is written at the same timestamp more than once, the most recent write wins

Examples

Input: ([('set', 'a', 'x', 5), ('set', 'a', 'y', 10), ('get', 'a', 4), ('get', 'a', 5), ('get', 'a', 7), ('get', 'a', 10), ('get', 'a', 100)],)

Expected Output: [None, 'x', 'x', 'y', 'y']

Explanation: Basic predecessor queries on one key.

Input: ([('set', 'k', 'late', 10), ('set', 'k', 'early', 3), ('set', 'k', 'replace', 10), ('get', 'k', 2), ('get', 'k', 3), ('get', 'k', 9), ('get', 'k', 10)],)

Expected Output: [None, 'early', 'early', 'replace']

Explanation: Out-of-order inserts are allowed, and the second write at timestamp 10 replaces the earlier value.

Hints

For each key, keep versions ordered by timestamp and answer get with a predecessor/floor search.
If duplicate timestamps are allowed, do not create two versions with the same timestamp for one key; overwrite the old value.

Quick Overview