Algorithmic Problem-Solving and Data Structure Selection Questions

Direct answer

Shard the cache by a hash of the key across many independent LRU (least-recently-used, an eviction policy that discards the item that has gone longest without being accessed) instances, each with its own lock, so concurrent threads mostly contend only with other threads hitting the same shard rather than one another. Fairness across tenants on top of that sharding needs an explicit per-tenant admission or capacity policy (blending recency with frequency, or capping each tenant's share of a shard), since plain LRU alone lets one tenant's access pattern evict another tenant's entries with no notion of "whose entry this is."

Structured elaboration

Why a single lock does not scale

A single shared lock around one LRU's map and linked list serializes every get and put across every thread and every tenant: at high throughput, that lock becomes the bottleneck regardless of how fast the underlying O(1) LRU operations are individually, since only one thread can hold the lock at a time.

Sharding for concurrency

Splitting the keyspace into S independent shards, each with its own map, its own recency-ordering structure, and its own lock, means two threads touching different shards never contend at all. A cheap, uniform hash of the key selects the shard. This trades strict global recency ordering (there is no longer one true "least recently used across everything") for a large reduction in lock contention; each shard's local eviction order is still correct within that shard.

flowchart TD
    A[Client request] --> B[hash of key]
    B --> C1[Shard 1: LRU + lock]
    B --> C2[Shard 2: LRU + lock]
    B --> C3[Shard N: LRU + lock]
    C1 --> D1[Per-tenant quota check]
    C2 --> D2[Per-tenant quota check]
    C3 --> D3[Per-tenant quota check]

Fairness across tenants

Sharding solves throughput, not fairness: within a single shard, a noisy tenant issuing far more requests than another will still fill the shared LRU list with its own entries and evict the quieter tenant's entries purely by volume. Three structural fixes, in increasing order of sophistication:

1. Per-tenant sub-capacity within each shard: give every tenant a fixed maximum slot count inside each shard (or a global per-tenant cap enforced across shards), so one tenant's volume cannot starve another's regardless of access pattern.
2. CLOCK-style approximate recency: rather than a strict doubly-linked recency list (which needs a lock on every access just to reorder), a CLOCK algorithm (a circular buffer of entries with a reference bit, advancing a "clock hand" that evicts entries whose bit is unset and clears bits it passes over) approximates LRU with cheaper, more concurrency-friendly bookkeeping, since a read only needs to set a bit rather than acquire a lock to splice a linked list.
3. Frequency-aware admission (SLRU/TinyLFU-style): a segmented or frequency-sketch-based admission policy (for example, an SLRU splitting each shard into a probationary and a protected segment, or a TinyLFU admission filter that only lets a new entry in if it is estimated to be accessed more often than the entry it would evict) protects a tenant's frequently-reused entries from being evicted by another tenant's one-off scan, which pure recency-based LRU cannot distinguish.

Worked example

Consider two tenants sharing one shard with capacity 4: tenant A accesses the same 2 keys repeatedly (a steady, high-frequency pattern), while tenant B does a one-time scan through 100 distinct keys. Under plain LRU with no per-tenant accounting, tenant B's scan evicts tenant A's 2 keys almost immediately, since LRU only tracks recency, not frequency or tenant identity, and every one of B's 100 accesses is more recent than A's last access. Under a per-tenant sub-capacity of 2 slots each within that shard, A's 2 keys never leave A's own reserved slots regardless of how large B's scan is, and B's scan only ever competes for eviction within its own 2 reserved slots.

Trade-offs & pitfalls

Sharding by hash gives up strict global LRU ordering: the item evicted first is the least-recently-used within its shard, not necessarily across the whole cache, which is an approximation, not a bug, as long as shard sizes are reasonably balanced. A concentrated hot key still funnels all its traffic to one shard's lock no matter how many shards exist, so key-level hotspot skew needs its own handling (for example, splitting an extremely hot key across multiple shard slots) rather than being solved by sharding alone. The most common wrong turn on the fairness half of this question is treating "add more shards" as if it also solved fairness: more shards reduce lock contention but do nothing about one tenant's volume crowding out another's entries within whichever shard both tenants happen to land on; fairness needs an explicit tenant-aware policy layered on top of, not instead of, sharding.

Direct answer

A plain stack already gives $O(1)$ push, pop, and top because those operations only ever touch the top element. The trick for $O(1)$ minimum retrieval is to keep a second, parallel stack that tracks what the minimum would be after each push: whenever you push a value onto the main stack, you also push the smaller of that value and the previous minimum onto the min-stack, so its top is always the correct current minimum, and popping both stacks together keeps them in sync without ever rescanning.

Approach

• Maintain two stacks of equal length at all times: stack holds the real values, min_stack holds, at each position, what the minimum was after that push.
• push(x): append x to stack. Append x to min_stack if min_stack is empty or x is less than or equal to its current top; otherwise append the current top again (repeating the still-current minimum).
• pop(): pop from both stacks together; the value from stack is returned, the value from min_stack is discarded.
• get_min(): return min_stack's top directly.

class MinStack:
    def __init__(self):
        self.stack: list[int] = []
        self.min_stack: list[int] = []

    def push(self, x: int) -> None:
        self.stack.append(x)
        if not self.min_stack or x <= self.min_stack[-1]:
            self.min_stack.append(x)
        else:
            self.min_stack.append(self.min_stack[-1])

    def pop(self) -> int:
        if not self.stack:
            raise IndexError("pop from empty stack")
        self.min_stack.pop()
        return self.stack.pop()

    def top(self) -> int:
        return self.stack[-1]

    def get_min(self) -> int:
        return self.min_stack[-1]


if __name__ == "__main__":
    s = MinStack()
    s.push(5)
    s.push(3)
    s.push(7)
    print(s.get_min())  # 3
    s.pop()
    print(s.get_min())  # 3
    s.pop()
    print(s.get_min())  # 5
    print(s.top())       # 5

Running this prints 3, 3, 5, 5: after pushing 5, 3, 7 the minimum is 3; popping 7 (the top) leaves the minimum still 3; popping 3 next leaves only 5, so both the minimum and the top become 5.

Key points

• Using <= (not strict <) when deciding whether to push a new minimum is what makes duplicate minimum values work correctly: if two entries tie for the minimum and you only recorded the first, popping it would incorrectly raise the recorded minimum before the still-present duplicate is gone.
• An alternative "encoded delta" trick stores a single stack, keeping only a running minimum variable, and pushes a value relative to that minimum instead of the raw value, updating the running minimum on push/pop as needed. It roughly halves auxiliary storage but is more error-prone to implement correctly, especially in fixed-width-integer languages (C++, Java) where the encoded delta itself can overflow if the gap between the pushed value and the previous minimum is large.

Complexity

Time: $O(1)$ for every operation (push, pop, top, get_min). Space: $O(n)$ auxiliary for $n$ elements (two stacks, each up to size $n$; a larger constant factor than a single stack, but still linear).

Edge cases

• pop or top on an empty stack should raise or otherwise signal an error rather than reading past the end.
• Duplicate values at the current minimum: handled correctly only if the min-stack push condition uses <=, not <.
• A single-element stack: get_min() must equal top().

Direct answer

Maintain an inclusive range [lo, hi] that is the only place the target could still be. At each step, compare the target to the middle element and shrink the range to whichever half could still contain it. The loop ends when lo > hi, at which point the target is not present, so return a sentinel (commonly -1). This runs in $O(\log n)$ time and $O(1)$ space.

Structured elaboration

The loop invariant. Before every iteration, "if the target is present in the array, its index lies within [lo, hi]" holds. Each iteration either returns immediately (found it) or moves lo past mid, or hi before mid, which strictly shrinks the range while preserving the invariant.

Why it terminates. Every iteration where the target is not found at mid removes at least the midpoint from consideration, so hi - lo at least halves (roughly) each time; the range cannot shrink forever without becoming empty, so the loop reaches lo > hi within $O(\log n)$ steps.

Why it never reads out of bounds. mid is always computed strictly between the current lo and hi, both of which start as, and remain, valid indices into the array (or the empty range lo > hi, which the loop condition catches before computing mid at all).

The overflow bug (reviewing someone else's code). Suppose a colleague wrote mid = (lo + hi) // 2. In Python this is safe because integers have arbitrary precision, but in a fixed-width-integer language such as Java or C++, lo + hi can exceed the maximum representable value for a very large array and silently wrap around, producing a corrupted mid that can throw the search out of bounds or into an infinite loop. Writing mid = lo + (hi - lo) // 2 avoids this because hi - lo never exceeds the array's size, so the sum can never overflow the way lo + hi can.

Worked example

def binary_search(nums: list[int], target: int) -> int:
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2  # avoids the lo + hi overflow above
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1


if __name__ == "__main__":
    nums = [1, 3, 5, 7, 9, 11]
    print(binary_search(nums, 7), binary_search(nums, 4))

Running this prints 3 -1. For target 7: lo=0, hi=5, mid=2 (value 5, too small, lo becomes 3); lo=3, hi=5, mid=4 (value 9, too big, hi becomes 3); lo=3, hi=3, mid=3 (value 7, match, return 3). For target 4: the range keeps shrinking until lo exceeds hi without ever matching, returning -1.

Complexity

Time: $O(\log n)$, since each iteration discards at least half of the remaining [lo, hi] range.
Space: $O(1)$ for this iterative version, since only a fixed number of index variables (lo, hi, mid) are held regardless of the array's size.

Edge cases

• Empty array (len(nums) == 0): lo = 0 and hi = -1 start with lo > hi, so the loop body never runs and the sentinel -1 is returned immediately.
• Target smaller than every element or larger than every element: the range shrinks to empty without ever matching, again returning the sentinel.
• Array with duplicate values: this exact routine returns the index of some matching element, not necessarily the first or last one; that is a distinct, slightly more involved variant.

Trade-offs & pitfalls

A recursive version expresses the same logic but spends $O(\log n)$ call-stack space doing so, where this iterative version uses $O(1)$. The other classic source of infinite loops or off-by-one errors is mixing bound conventions, for example initializing hi = len(nums) (a half-open convention) while writing the rest of the loop as if hi were an inclusive index; pick one convention and keep it consistent throughout.

Direct answer

A binary heap is a complete binary tree (every level full except possibly the last, which fills left to right) stored compactly in an array. A min-heap keeps every parent less than or equal to its children, so the root is always the minimum; a max-heap keeps every parent greater than or equal to its children, so the root is always the maximum. Insert and extract-min/max both cost $O(\log n)$ because each only has to fix a single root-to-leaf path, while peek is $O(1)$ since the answer always sits at the root. Reach for a heap over a balanced binary search tree (BST) or a plain hash table specifically when the operation you actually need is "give me the current min or max, repeatedly, while other items keep arriving": a heap does that with a simpler structure and lower constant factors than a full BST, and a hash table can't do it at all without a full scan.

Structured elaboration

Array representation and core operations (0-indexed; for a node at index $i$, its children sit at $2i+1$ and $2i+2$)

• Insert: append the new value at the next free array slot, then "sift up", swapping it with its parent while the heap property is violated. Time $O(\log n)$ (tree height), space $O(1)$ auxiliary.
• Peek: return the root value directly. Time $O(1)$.
• Extract-min/max: read the root, move the last array element into the root position, shrink the array by one, then "sift down" from the root, swapping with the smaller (or larger) child until the heap property holds. Time $O(\log n)$.
• Build-heap (heapify) from an existing array: run sift-down starting from the last non-leaf node back to the root, not one insert at a time. This costs $O(n)$ total, not $O(n \log n)$: most nodes sit near the bottom of the tree and only need a short sift-down, and the sum of sift-down work across all levels is a convergent series bounded by $O(n)$, tighter than treating it as $n$ separate $O(\log n)$ inserts.

Heap versus balanced BST versus hash table

Use a heap when you repeatedly need the current best item and nothing else about ordering; use a BST when you also need range queries, in-order traversal, or predecessor/successor lookups; use a hash table when you only need arbitrary-key existence or lookup and never need the min, max, or any ordering.

Worked example

A concrete use of a min-heap of bounded size $k$ to track the top-$k$ largest values in a stream: push each new value; once the heap holds $k$ items, only replace the root (the current smallest of the kept set) if the new value is larger.

import heapq


def top_k_largest(nums: list[int], k: int) -> list[int]:
    heap: list[int] = []
    for x in nums:
        if len(heap) < k:
            heapq.heappush(heap, x)
        elif x > heap[0]:
            heapq.heapreplace(heap, x)
    return sorted(heap, reverse=True)


if __name__ == "__main__":
    nums = [7, 2, 9, 4, 1, 8, 3, 10, 5, 6]
    print(top_k_largest(nums, 3))

Running this prints [10, 9, 8]: the heap only ever holds the 3 largest values seen so far, each of the other 7 values is checked against the current smallest kept value (the root) in $O(1)$ and, if larger, replaces it in $O(\log k)$, for a total cost of $O(m \log k)$ across $m$ input values.

Trade-offs & pitfalls

• Inserting $n$ elements one at a time into an empty heap costs $O(n \log n)$ total; heapify builds the same final structure in $O(n)$. Both produce a valid heap, only the construction cost differs, and conflating the two is a common mistake.
• A heap does not support efficient arbitrary-key lookup or a "decrease this specific key's priority" operation without extra bookkeeping (an auxiliary map from key to its current array position); this matters for algorithms like Dijkstra's shortest-path algorithm that rely on decrease-key.
• $k$-ary heaps (each node has $k$ children instead of 2) trade a shallower tree, so insert and decrease-key touch fewer levels, for a more expensive sift-down, since each step now compares against $k$ children instead of 2; they help when insert/decrease-key frequency dominates extraction frequency.
• Duplicate keys are allowed by the heap property; the ordering among equal keys is unspecified and shouldn't be relied upon.

Direct answer

Walk the list once, and at each node redirect its next reference back to the previous node before advancing, using three tracking references: previous, current, and a temporary save of current's original next. This is $O(n)$ time and $O(1)$ space. A recursive version expresses the identical rewiring, handling everything after the current node first and then flipping the one link back, but it pays for that with $O(n)$ call-stack space that the iterative version does not need.

Structured elaboration

The iterative three-pointer dance. Before overwriting curr.next, save it in a temporary variable, or the rest of the list is lost permanently. Then point curr.next back at prev, advance prev to curr, and advance curr to the saved temporary. Repeat until curr is empty.

The recursive version. The base case is an empty list or a single remaining node, which is already "reversed" as-is. Otherwise, recursively reverse everything after the head first; that recursive call returns the new head of the whole reversed list. Then head.next.next = head flips the one link connecting the old head back into the newly-reversed remainder, and head.next = None prevents the old head from accidentally pointing at itself in a two-node cycle.

What language a solution is written in does not change any of this. The reskin into Python, JavaScript, Swift, or Kotlin, or building the linked-list node class from scratch first, is the same pointer-rewiring skill underneath; only the syntax for holding and dereferencing a reference changes, not the three-step relinking logic itself.

Worked example

class Node:
    def __init__(self, val, next=None):
        self.val = val
        self.next = next


def reverse_iterative(head):
    prev = None
    curr = head
    while curr:
        next_tmp = curr.next  # save before overwriting
        curr.next = prev
        prev = curr
        curr = next_tmp
    return prev


def reverse_recursive(head):
    if head is None or head.next is None:
        return head
    new_head = reverse_recursive(head.next)
    head.next.next = head
    head.next = None
    return new_head


def to_list(head):
    out = []
    while head:
        out.append(head.val)
        head = head.next
    return out


def build_list(vals):
    dummy = Node(0)
    tail = dummy
    for v in vals:
        tail.next = Node(v)
        tail = tail.next
    return dummy.next


if __name__ == "__main__":
    print(to_list(reverse_iterative(build_list([1, 2, 3, 4]))))
    print(to_list(reverse_recursive(build_list([1, 2, 3, 4]))))

Running this prints [4, 3, 2, 1] twice, once from each implementation.

Complexity

Time: $O(n)$ for both the iterative and recursive versions, since each one visits every node exactly once.
Space: $O(1)$ extra for the iterative version (three pointer variables regardless of list length); $O(n)$ for the recursive version, from the call stack, since the recursion descends one frame per node before any relinking happens.

Edge cases

• Empty list (head is None): both versions return None immediately without any relinking.
• Single-node list: both versions return that same node unchanged as the new head, since there is nothing to reverse.
• Very long list: the recursive version risks an actual stack overflow, since typical call-stack depth limits are far smaller than what a linked list can otherwise hold in memory.

Trade-offs & pitfalls

The recursive version risks an actual stack overflow on a very long list in production, not just an academic concern, since typical call-stack depth limits are far smaller than what a linked list or array can otherwise hold in memory. The single most common bug in the iterative version is forgetting to save curr.next before overwriting it, which permanently disconnects the rest of the list from anything still reachable.