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 hard difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Nextdoor.

What role is this question designed for?

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

Simulate Transaction Lock Scheduling | Nextdoor Coding Question

Simulate Transaction Lock Scheduling

Company: Nextdoor

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

Implement an in-memory transaction lock simulator. You do **not** need to create real threads; you only need to simulate how transactions acquire locks, become blocked, queue operations, resume, and release locks. Design a class that supports the following methods: ```text begin(id) echo(id, message) acquire(id, lockName) finish(id) ``` Rules: - `begin(id)` creates a new transaction with the given transaction id. - Each transaction executes its operations in the order they are received. - A transaction may hold zero or more named exclusive locks. - `acquire(id, lockName)` attempts to acquire an exclusive lock for transaction `id`. - If the lock is free, grant it immediately. - If the lock is already held by the same transaction, treat the call as a no-op. - If the lock is held by another active transaction, the transaction becomes blocked, and this operation must be queued. - `echo(id, message)` emits `message` only if transaction `id` is not blocked. - If the transaction is currently blocked, queue the `echo` operation so it executes after the transaction becomes unblocked. - `finish(id)` ends the transaction and releases all locks held by it. - If the transaction is currently blocked, queue the `finish` operation so it runs only after all earlier queued operations for that transaction can run. - When locks are released, waiting transactions should be resumed in FIFO order for each lock. - When a transaction resumes, execute its queued operations in order until it either blocks again or finishes. - The simulator should preserve the observable order of `echo` messages according to the above scheduling rules. Return or expose the sequence of messages produced by executed `echo` calls. Example: ```text begin(1) acquire(1, "A") echo(1, "t1 has A") begin(2) acquire(2, "A") // transaction 2 blocks echo(2, "t2 has A") // queued behind the blocked acquire finish(1) // releases A, transaction 2 resumes echo(2, "t2 still running") finish(2) ``` Expected emitted messages: ```text t1 has A t2 has A t2 still running ```

Quick Answer: This question evaluates understanding of concurrency control, lock scheduling, transaction state management, and queuing behavior in the Coding & Algorithms domain, focusing on practical application through an in-memory transaction lock simulator.

You are given a sequence of API-like operations for an in-memory transaction system. Simulate how transactions acquire exclusive locks, become blocked, queue later operations, resume when locks are released, and emit messages from echo operations. For grading, implement a function `solution(operations)` instead of a class. Each element of `operations` is one of: - `('begin', id)` - `('echo', id, message)` - `('acquire', id, lockName)` - `('finish', id)` Behavior: - `begin(id)` creates a new active transaction. - Each transaction must execute its own operations in the order they are received. - A transaction may hold multiple named exclusive locks. - `acquire(id, lockName)`: - if the lock is free, grant it immediately; - if the same transaction already holds it, do nothing; - otherwise, the transaction becomes blocked on that lock, and the acquire remains at the front of that transaction's pending queue. - `echo(id, message)` emits `message` only if the transaction is active. If the transaction is blocked, queue the echo behind earlier pending operations. - `finish(id)` ends the transaction and releases all of its locks. If the transaction is blocked, queue the finish operation. - Each lock has its own FIFO wait queue. When a lock is released, wake the first transaction waiting for that lock, grant it the lock, and allow it to continue running. - When a transaction resumes, keep executing its queued operations in order until it blocks again or finishes. - If `finish` releases multiple locks, process those released locks in the order the transaction originally acquired them. - Newly awakened transactions must run before the simulator processes the next input operation. Return the list of messages produced by executed `echo` calls, in the exact observable order. You may assume the input is well-formed: `begin` ids are unique, and every non-`begin` operation refers to an existing transaction that has not yet finished. No deadlock detection is required.

Constraints

0 <= len(operations) <= 2 * 10^5
Transaction ids in `begin` operations are unique
Every non-`begin` operation refers to an existing transaction that has not already finished
The total number of queued operations and total length of all strings fit in memory

Examples

Input: ([('begin', 1), ('acquire', 1, 'A'), ('echo', 1, 't1 has A'), ('begin', 2), ('acquire', 2, 'A'), ('echo', 2, 't2 has A'), ('finish', 1), ('echo', 2, 't2 still running'), ('finish', 2)],)

Expected Output: ['t1 has A', 't2 has A', 't2 still running']

Explanation: Transaction 2 blocks on A. When transaction 1 finishes, A is released, transaction 2 resumes, its queued acquire succeeds, and its queued echo runs before the later external echo.

Input: ([],)

Expected Output: []

Explanation: No operations means no emitted messages.

Input: ([('begin', 1), ('acquire', 1, 'A'), ('acquire', 1, 'A'), ('echo', 1, 'still active'), ('finish', 1)],)

Expected Output: ['still active']

Explanation: Reacquiring a lock already held by the same transaction is a no-op.

Input: ([('begin', 1), ('acquire', 1, 'A'), ('begin', 2), ('acquire', 2, 'A'), ('finish', 2), ('echo', 1, 'done'), ('finish', 1)],)

Expected Output: ['done']

Explanation: Transaction 2 blocks on A, so its finish is queued behind the blocked acquire. After transaction 1 finishes, transaction 2 resumes, acquires A, and then immediately finishes without emitting anything.

Input: ([('begin', 1), ('acquire', 1, 'B'), ('acquire', 1, 'A'), ('begin', 2), ('acquire', 2, 'A'), ('echo', 2, 'got A'), ('begin', 3), ('acquire', 3, 'B'), ('echo', 3, 'got B'), ('finish', 1), ('finish', 3), ('finish', 2)],)

Expected Output: ['got B', 'got A']

Explanation: Transaction 1 releases multiple locks when it finishes. Because locks are released in acquisition order, B is released before A, so transaction 3 resumes before transaction 2.

Hints

Keep separate state for each transaction: active/blocked/finished, its pending operation queue, the lock it is waiting on, and the locks it currently holds.
For each lock, store its current owner and a FIFO wait queue. When a transaction finishes, wake at most one waiter per released lock, then let awakened transactions run until they block again or finish.

Quick Overview

This question evaluates understanding of concurrency control, lock scheduling, transaction state management, and queuing behavior in the Coding & Algorithms domain, focusing on practical application through an in-memory transaction lock simulator.