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 SoFi.

What role is this question designed for?

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

Design a key-value store with getLast

Quick Overview

Design a key-value store with getLast evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Company: SoFi

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

Design and implement an in-memory key–value store with this API: add(key, value), get(key), remove(key), and getLast(). The operation getLast() must return the most recently added entry that still exists in the store. Calling get(key) must not change which element is considered "last." Specify behavior for edge cases: adding an existing key (overwrite vs. reject), removing the current last element (the next most recent becomes last), and calling getLast() on an empty store (return sentinel or throw). Target O( 1) average time for all operations; justify your data structures, provide pseudocode for each method, and analyze time and space complexity. Discuss how you would test correctness for concurrent adds/removes and outline any locking strategy if concurrency is required.

Quick Answer: Design a key-value store with getLast evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Implement an in-memory key-value store that supports four operations, each O(1) average time: - `add(key, value)` - insert `key` with `value`. If `key` already exists, overwrite its value AND treat it as the most recently added entry (refreshes recency). - `get(key)` - return the value for `key`, or a null/None sentinel if absent. Calling `get` must NOT change which entry is considered "last". - `remove(key)` - delete `key` from the store (no-op if absent). If you remove the current last entry, the next most recently added entry that still exists becomes the new last. - `getLast()` - return the most recently added entry that still exists, as a `[key, value]` pair, or null/None if the store is empty. Write a function `processOperations(operations)` that replays a list of operations and returns the list of outputs produced by the query operations (`get` and `getLast`), in order. Each operation is a list whose first element is the op name: - `["add", key, value]` - `["get", key]` -> appends the value (or null) to the result list - `["remove", key]` - `["getLast"]` -> appends `[key, value]` (or null) to the result list Keys are strings and values are integers. Example: Input: `[["add","a",1],["add","b",2],["getLast"],["get","a"],["getLast"]]` Output: `[["b",2], 1, ["b",2]]` (`getLast` is `b` after the two adds; `get("a")` returns 1 without changing the last; `getLast` is still `b`.)

Constraints

Keys are strings; values are integers.
add on an existing key overwrites the value and refreshes its recency (becomes last).
get returns null/None for a missing key and never changes which entry is last.
remove is a no-op on a missing key; removing the last entry promotes the next most recent live entry to last.
getLast on an empty store returns null/None.
All operations must be O(1) average time.

Examples

Input: [["add", "a", 1], ["add", "b", 2], ["getLast"], ["get", "a"], ["getLast"]]

Expected Output: [["b", 2], 1, ["b", 2]]

Explanation: After adding a then b, last is b. get(a) returns 1 but does not change last, so the second getLast is still b.

Input: [["add", "a", 1], ["add", "b", 2], ["remove", "b"], ["getLast"]]

Expected Output: [["a", 1]]

Explanation: Removing the current last (b) promotes the next most recent live entry, a, to last.

Input: [["getLast"], ["get", "x"]]

Expected Output: [null, null]

Explanation: Empty store: getLast returns null and get of a missing key returns null.

Input: [["add", "k", 10], ["add", "k", 20], ["get", "k"], ["getLast"]]

Expected Output: [20, ["k", 20]]

Explanation: Re-adding an existing key overwrites the value to 20 and refreshes recency; k is last with value 20.

Input: [["add", "a", 1], ["add", "b", 2], ["add", "c", 3], ["remove", "c"], ["remove", "a"], ["getLast"], ["add", "d", 4], ["getLast"], ["remove", "d"], ["getLast"]]

Expected Output: [["b", 2], ["d", 4], ["b", 2]]

Explanation: After removing c then a, the live order is [b]; adding d makes it last; removing d falls back to b.

Input: [["add", "a", 1], ["remove", "a"], ["getLast"]]

Expected Output: [null]

Explanation: Removing the only entry empties the store, so getLast returns null.

Hints

A hash map alone gives O(1) add/get/remove but cannot answer getLast efficiently after the most-recent entry is removed.
Pair the hash map with a doubly linked list ordered by insertion recency; the tail is always 'last'. Store node pointers in the map so any key can be detached in O(1).
On add of an existing key, detach its node first, then re-append at the tail so recency is refreshed. On remove, detach and let the previous node become the new tail automatically.
get must read the value without touching the linked list, so recency is preserved.

Quick Overview