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 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 Grid Spread and Transactional Store

Quick Overview

This question evaluates skills in grid-based propagation modeling and stateful transactional system design, testing concepts such as graph traversal and timed spread dynamics for the grid task and nested transaction semantics, isolation, and state management for the in-memory key-value store.

Company: Lyft

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Onsite

You have two coding tasks. ### Task A: Compute Contamination Spread Time Given an `m x n` grid: - `0` means an empty cell. - `1` means a fresh item. - `2` means a contaminated item. Every minute, each contaminated item contaminates its fresh 4-directional neighbors: up, down, left, and right. Return the minimum number of minutes needed until no fresh items remain. If some fresh item can never be contaminated, return `-1`. Handle edge cases such as an empty grid, no fresh items, isolated fresh items, and multiple initial contaminated items. ### Task B: Implement an In-Memory Transactional Key-Value Store Implement an in-memory key-value store supporting basic operations and transactions. Required API: - `get(key)`: Return the current value for `key`, or `null`/`None` if the key does not exist. - `set(key, value)`: Set `key` to `value` in the current transaction if one exists; otherwise set it in the main store. - `delete(key)`: Delete `key` in the current transaction if one exists; otherwise delete it from the main store. - `begin()`: Start a new transaction. Transactions may be nested. - `rollback()`: Revert all changes made in the most recent active transaction. Return whether the rollback succeeded. - `commit()`: Commit the most recent active transaction. If it is nested, merge its changes into the parent transaction; otherwise apply them to the main store. Return whether the commit succeeded. Important edge cases: - `rollback()` or `commit()` with no active transaction. - Reading a key changed in the current transaction. - Reading a key changed in an outer transaction. - Deleting a key inside a transaction and then rolling back. - Setting a key after deleting it in the same transaction. - Nested transactions with independent rollback and commit behavior.

Quick Answer: This question evaluates skills in grid-based propagation modeling and stateful transactional system design, testing concepts such as graph traversal and timed spread dynamics for the grid task and nested transaction semantics, isolation, and state management for the in-memory key-value store.

Part 1: Compute Contamination Spread Time

You are given a 2D grid where `0` represents an empty cell, `1` represents a fresh item, and `2` represents a contaminated item. Every minute, each contaminated item spreads contamination to its fresh neighbors in the four cardinal directions: up, down, left, and right. Return the minimum number of minutes required until no fresh items remain. If at least one fresh item can never be contaminated, return `-1`. If the grid is empty or there are no fresh items to begin with, return `0`.

Constraints

`0 <= m, n <= 200`, where `m` is the number of rows and `n` is the number of columns
Each `grid[r][c]` is one of `0`, `1`, or `2`
Contamination spreads only in 4 directions

Examples

Input: [[2, 1, 1], [1, 1, 0], [0, 1, 1]]

Expected Output: 4

Explanation: The contamination spreads outward level by level and reaches the last fresh item after 4 minutes.

Input: [[2, 1, 1], [0, 1, 1], [1, 0, 1]]

Expected Output: -1

Explanation: The fresh item at the bottom-left is isolated by empty cells, so not all fresh items can be contaminated.

Input: [[0, 2, 0]]

Expected Output: 0

Explanation: There are no fresh items, so no time is needed.

Input: []

Expected Output: 0

Explanation: An empty grid has nothing to process.

Input: [[2, 1, 1], [1, 1, 1], [0, 2, 1]]

Expected Output: 2

Explanation: There are two initial contamination sources, so the spread finishes faster.

Hints

Think of all initially contaminated cells as starting points at the same time.
A breadth-first search by levels naturally models the minute-by-minute spread.

Part 2: Implement an In-Memory Transactional Key-Value Store

Process a sequence of commands for an in-memory key-value store with nested transactions. The store must support `get`, `set`, `delete`, `begin`, `rollback`, and `commit`. A `set` or `delete` affects the current transaction if one exists; otherwise it affects the main store. `rollback` reverts only the most recent active transaction. `commit` applies the most recent transaction: if it is nested, merge its changes into the parent transaction; otherwise apply them to the main store. Return the results of all `get`, `rollback`, and `commit` operations in the order they occur. `set`, `delete`, and `begin` do not produce output.

Constraints

`1 <= len(operations) <= 10^4`
Transaction nesting depth can be as large as the number of operations
Keys are strings and values are integers in the provided tests
Deleting a missing key should not raise an error

Examples

Input: [('set', 'a', 10), ('get', 'a'), ('delete', 'a'), ('get', 'a')]

Expected Output: [10, None]

Explanation: Basic operations outside a transaction work directly on the main store.

Input: [('rollback',), ('commit',)]

Expected Output: [False, False]

Explanation: Both commands fail because there is no active transaction.

Input: [('set', 'x', 1), ('begin',), ('delete', 'x'), ('get', 'x'), ('rollback',), ('get', 'x')]

Expected Output: [None, True, 1]

Explanation: Inside the transaction, `x` appears deleted. After rollback, the original value is visible again.

Input: [('begin',), ('set', 'a', 1), ('begin',), ('get', 'a'), ('rollback',), ('get', 'a'), ('commit',), ('get', 'a')]

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

Explanation: The inner transaction can read a value changed in the outer transaction. Rolling back the inner one does not affect the outer change.

Input: [('set', 'x', 5), ('begin',), ('delete', 'x'), ('set', 'x', 7), ('begin',), ('set', 'x', 9), ('rollback',), ('get', 'x'), ('commit',), ('get', 'x')]

Expected Output: [True, 7, True, 7]

Explanation: A key deleted and then set again in the same transaction should hold the new value. Rolling back the inner transaction restores the outer transaction's state.

Hints

Use a stack to represent nested transactions.
For reads, search from the most recent transaction backward before checking the main store.

Quick Overview