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 Technical Screen rounds at Stripe.

What role is this question designed for?

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

Implement account scheduler with locking and LRU

Company: Stripe

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Design a class `AccountScheduler` that manages the time-based availability of a fixed set of account IDs. ### Initialization You are given: - `accounts`: a list of integers representing all account IDs in the system. - `locked_until`: a dictionary mapping `account_id` → integer timestamp, e.g.: ```text locked_until = { 1: 10, 2: 5, 3: 0, 4: 20 } ``` Interpretation of `locked_until[account_id]`: - The account is **unavailable (locked)** for all times `t` such that `t < locked_until[account_id]`. - The account is **available** for all times `t` such that `t >= locked_until[account_id]`. - If an account does not appear in `locked_until`, treat it as if `locked_until[account_id] = 0` (initially available at `t >= 0`). All time values are integers. You may assume all method calls are processed **sequentially**; you do not need to handle concurrency. Example state and queries: ```text accounts = [1, 2, 3, 4] locked_until = { 1: 10, 2: 5, 3: 0, 4: 20 } is_available(1, 8) -> False # 8 < 10 is_available(2, 8) -> True # 8 >= 5 is_available(3, 1) -> True # 1 >= 0 is_available(4, 21) -> True # 21 >= 20 ``` --- ### Part 1 — Availability queries Implement the class constructor and a method: ```text is_available(account_id, t) -> bool ``` that returns whether `account_id` is available at time `t` according to the `locked_until` rules above. You may store and update internal state in any way you like, but `is_available` must be correct for any sequence of calls. --- ### Part 2 — Explicit acquire operation Extend `AccountScheduler` with a method to acquire/lock a specific account for some duration starting at a given time. Add: ```text acquire(account_id, t, duration) ``` Semantics: - `t` is the current time of the operation. - `duration` is a positive integer. - When `acquire(account_id, t, duration)` is called, you should update internal state so that the account becomes **unavailable** for the time interval `[t, t + duration)`. In terms of the `locked_until` model, this means: ```text locked_until[account_id] = max(locked_until[account_id], t) + duration ``` (i.e., if the account was already locked until some time in the future, the new lock extends from the later of the current lock and `t`). - You may choose whether `acquire` returns `void` or a boolean indicating success/failure; if you support failure, it should fail (e.g., return `False`) when the account is not available at time `t`. Assume all `acquire` and `is_available` calls are supplied with non-decreasing timestamps (`t` never goes backwards). --- ### Part 3 — Auto-select account using LRU policy Now extend the API to support acquiring **any available account** automatically, using an LRU (least recently used) policy. Add an overloaded method: ```text auto_acquire(t, duration) -> Optional[account_id] ``` Semantics: - Consider all accounts that are **available** at time `t` (i.e., `is_available(account_id, t)` is `True`). - Among those, choose the account that was **least recently used**, where "used" is defined as: - The last time the account was successfully acquired (either via `acquire(account_id, t, duration)` or `auto_acquire(t, duration)`). - Accounts that have **never** been acquired are treated as having the oldest possible last-used time (i.e., they should be preferred over accounts that have been used more recently). - If at least one account is available: - Select the least-recently-used available account. - Lock it for `[t, t + duration)` as in Part 2. - Return its `account_id`. - If **no** accounts are available at time `t`, return `None` (or a sentinel value indicating failure). Your task: - Design the internal data structures and implement the three methods: - `is_available(account_id, t)` - `acquire(account_id, t, duration)` - `auto_acquire(t, duration)` - Ensure that all methods are efficient for large numbers of accounts and large numbers of operations. - Assume all calls are sequential and timestamps are non-decreasing.

Quick Answer: This question evaluates understanding of time-based resource scheduling, locking semantics, LRU eviction policies, and stateful data-structure management in the coding & algorithms domain.

Design a class `AccountScheduler` that manages the time-based availability of a fixed set of account IDs. You are initialized with `accounts` (a list of integer account IDs) and `locked_until` (a dict mapping `account_id -> integer timestamp`). An account is **locked/unavailable** for all times `t < locked_until[account_id]`, and **available** for all `t >= locked_until[account_id]`. Accounts missing from `locked_until` default to `0` (available from `t >= 0`). All time values are integers, all calls are sequential (no concurrency), and timestamps are non-decreasing. **Part 1 — Availability queries.** Implement `is_available(account_id, t) -> bool`, returning whether `account_id` is available at time `t`. **Part 2 — Explicit acquire.** Implement `acquire(account_id, t, duration) -> bool`. `duration` is a positive integer; the account becomes unavailable for `[t, t + duration)`, i.e. `locked_until[account_id] = max(locked_until[account_id], t) + duration`. Return `False` (fail) if the account is not available at time `t`, otherwise lock it and return `True`. A successful acquire records this as the account's last-used time. **Part 3 — Auto-select via LRU.** Implement `auto_acquire(t, duration) -> Optional[account_id]`. Among all accounts available at time `t`, pick the **least recently used** one (an account's "use" is its last successful acquire; never-acquired accounts are treated as the oldest, so they are preferred). Lock the chosen account for `[t, t + duration)`, record it as used at time `t`, and return its id. If no account is available, return `None`. **Harness note (how this console drives your class):** Because the console verifies pure functions, you implement a single function `solution(accounts, locked_until, operations)` that builds the scheduler and replays a list of `operations`, returning one result per operation. Each operation is one of: - `["is_available", account_id, t]` -> bool - `["acquire", account_id, t, duration]` -> bool (success/failure) - `["auto_acquire", t, duration]` -> account_id or None Return the list of results in order.

Constraints

All account IDs are integers; accounts is a fixed set provided at construction.
locked_until maps account_id -> integer timestamp; accounts absent from it default to 0.
All timestamps t are non-negative integers and are supplied in non-decreasing order across calls.
duration is a positive integer.
is_available is true exactly when t >= locked_until[account_id].
acquire fails (returns False) when the account is not available at time t.
auto_acquire returns None when no account is available at time t.
Calls are sequential; no concurrency handling is required.

Examples

Input: ([1, 2, 3, 4], {1: 10, 2: 5, 3: 0, 4: 20}, [["is_available", 1, 8], ["is_available", 2, 8], ["is_available", 3, 1], ["is_available", 4, 21]])

Expected Output: [False, True, True, True]

Explanation: Part 1 basic queries: account 1 is locked until 10 so unavailable at 8; account 2 unlocks at 5 (available at 8); account 3 default-available; account 4 unlocks at 20 (available at 21).

Input: ([1, 2], {}, [["is_available", 1, 0], ["acquire", 1, 0, 5], ["is_available", 1, 3], ["is_available", 1, 5], ["acquire", 2, 0, 3]])

Expected Output: [True, True, False, True, True]

Explanation: Part 2: account 1 starts available; acquiring it at t=0 for 5 locks it until 5, so it is unavailable at 3 but available again at 5 (boundary is inclusive). Account 2 is independently available and acquired.

Input: ([1, 2, 3], {}, [["acquire", 1, 0, 100], ["auto_acquire", 5, 10], ["auto_acquire", 5, 10], ["auto_acquire", 5, 10]])

Expected Output: [True, 2, 3, None]

Explanation: Part 3: account 1 is locked until 100. auto_acquire at t=5 picks among {2,3} (both never used) the smaller id 2, then 3; the third call finds nothing available and returns None.

Input: ([1, 2, 3], {}, [["acquire", 1, 0, 2], ["acquire", 2, 1, 2], ["auto_acquire", 10, 1], ["auto_acquire", 10, 1], ["auto_acquire", 10, 1]])

Expected Output: [True, True, 3, 1, 2]

Explanation: LRU ordering: by t=10 all are available. last_used is {1:0, 2:1}, 3 never used. auto_acquire picks 3 (never used) first, then 1 (oldest use at 0), then 2 (used at 1).

Input: ([7], {7: 50}, [["is_available", 7, 49], ["acquire", 7, 49, 5], ["auto_acquire", 49, 1]])

Expected Output: [False, False, None]

Explanation: Account 7 is locked until 50, so it is unavailable at 49; the acquire at t=49 therefore fails (returns False) and leaves state unchanged, so auto_acquire at 49 finds nothing and returns None.

Input: ([], {}, [["auto_acquire", 0, 5]])

Expected Output: [None]

Explanation: Edge case: with no accounts in the system, auto_acquire has nothing to select and returns None.

Input: ([5], {}, [["acquire", 5, 0, 3], ["acquire", 5, 1, 10], ["is_available", 5, 2], ["is_available", 5, 3], ["auto_acquire", 3, 1]])

Expected Output: [True, False, False, True, 5]

Explanation: First acquire locks account 5 until 3. The second acquire at t=1 fails because 5 is not available then, so it does NOT extend the lock. Account 5 becomes available again at t=3 (boundary inclusive) and auto_acquire at t=3 selects it.

Hints

Keep a single dict locked_until[account_id]; availability at time t is simply t >= locked_until.get(account_id, 0).
For acquire, the new lock end is max(locked_until[account_id], t) + duration so an already-future lock extends correctly rather than being shortened.
Track a separate last_used map updated only on a *successful* acquire (explicit or auto). Never-acquired accounts should compare as older than any used account.
For auto_acquire, scan available accounts and pick the LRU using the tuple key (was_used?, last_used_time, account_id) so never-used wins first, then oldest, then smallest id breaks ties deterministically.