Algorithmic Problem Solving Questions

Evaluates ability to decompose computational problems, design correct and efficient algorithms, reason about complexity, and consider edge cases and correctness. Expectation includes translating problem statements into data structures and algorithmic steps, justifying choices of approach, analyzing time and space complexity, optimizing for constraints, and producing test cases and proofs of correctness or invariants. This topic covers common algorithmic techniques such as sorting, searching, recursion, dynamic programming, greedy algorithms, graph traversal, and trade offs between readability, performance, and maintainability.

EasyTechnical

82 practiced

Given an integer array nums and a sliding window size k, implement a function in Python that returns an array of the maximum values in each sliding window of size k. Requirement: O(n) time total and O(k) space. Example: nums = [1,3,-1,-3,5,3,6,7], k = 3 -> result = [3,3,5,5,6,7].

Sample Answer

To solve this in O(n) time and O(k) space, use a monotonic deque that stores indices of elements in decreasing order of their values. For each new element, pop from the back while current value >= deque's last value, append current index, and remove the front if it's out of the window. The front index always points to the max for the current window.

python

from collections import deque

def max_sliding_window(nums, k):
    """
    Return list of max values for each sliding window of size k.
    Time: O(n), Space: O(k)
    """
    if k <= 0 or not nums:
        return []
    n = len(nums)
    if k > n:
        return [max(nums)]

    dq = deque()  # will store indices, values decreasing
    res = []

    for i, val in enumerate(nums):
        # remove indices out of window
        while dq and dq[0] <= i - k:
            dq.popleft()

        # maintain decreasing values: remove smaller elements from back
        while dq and nums[dq[-1]] <= val:
            dq.pop()

        dq.append(i)

        # window is full starting at i = k-1
        if i >= k - 1:
            res.append(nums[dq[0]])

    return res

Key points:- Deque keeps indices; front is max.- Each element is pushed/popped at most once → O(n) time.- Space: deque holds at most k indices → O(k).

Edge cases:- k == 1 returns original array.- k > len(nums) handled by returning global max.- empty nums or non-positive k returns [].

Alternative:- A max-heap with lazy deletion works but yields O(n log k) time. Deque is optimal here.

EasyTechnical

93 practiced

Design and implement a class in Python that maintains the median of an online stream of integers. Provide methods add(num) to add a number and median() to return the current median. Requirement: each add should be O(log n) time and overall space O(n). Explain how two heaps are used and handle even/odd counts.

Sample Answer

Approach: use two heaps (max-heap for lower half, min-heap for upper half) so that adding is O(log n) and median is O(1). Maintain sizes so they differ by at most 1. For odd count, the root of the larger heap is median; for even, median is average of both roots.

python

import heapq

class OnlineMedian:
    def __init__(self):
        # max_heap stores negated values to simulate max-heap
        self.max_heap = []  # lower half
        self.min_heap = []  # upper half

    def add(self, num: int) -> None:
        # push into appropriate heap
        if not self.max_heap or num <= -self.max_heap[0]:
            heapq.heappush(self.max_heap, -num)
        else:
            heapq.heappush(self.min_heap, num)

        # rebalance so size difference <= 1
        if len(self.max_heap) > len(self.min_heap) + 1:
            heapq.heappush(self.min_heap, -heapq.heappop(self.max_heap))
        elif len(self.min_heap) > len(self.max_heap) + 1:
            heapq.heappush(self.max_heap, -heapq.heappop(self.min_heap))

    def median(self) -> float:
        if not self.max_heap and not self.min_heap:
            raise ValueError("no elements")
        if len(self.max_heap) > len(self.min_heap):
            return -self.max_heap[0]
        if len(self.min_heap) > len(self.max_heap):
            return self.min_heap[0]
        return (-self.max_heap[0] + self.min_heap[0]) / 2.0

Key points:- max_heap holds the smaller half (as negatives); min_heap holds the larger half.- Rebalance after each add to keep O(log n) push/pop.Complexity: add O(log n), median O(1), space O(n).Edge cases: empty stream, duplicates, negative numbers. This pattern is useful in SRE for streaming metrics aggregation (latencies, percentiles) with bounded memory and predictable performance.

HardTechnical

73 practiced

Prove Raft's election safety property: at most one leader can be elected in a given term. Outline the invariants required and explain how term numbers and voting restrictions enforce safety. Then propose a change to reduce election churn during network partitions and discuss why your change preserves safety.

Sample Answer

Situation / goal: Prove Raft’s election-safety: at most one leader per term. I'll state the invariants Raft relies on, show why they imply safety, and then propose a change to reduce election churn (pre-vote / leader stickiness) and argue safety is preserved.

Invariants (must hold on all persistent state transitions):1. Monotonic term: persistent currentTerm never decreases; any RPC or election with higher term updates it.2. At-most-one-vote-per-term: each server persists votedFor for currentTerm and grants at most one vote in that term.3. Log-up-to-date-vote: a server votes for a candidate only if the candidate’s (term, lastIndex) is at least as up-to-date as its own log.4. Leader-announcement: a leader for term T only exists after it received votes from a majority in term T.

Proof sketch (why at most one leader per term):- Suppose for contradiction there were two leaders L1 and L2 both claiming term T. Each must have gathered votes from a majority: M1 and M2. Any two majorities intersect at some server S.- S could not have voted for both L1 and L2 in term T because of invariant 2 (at-most-one-vote-per-term). Therefore one of L1 or L2 could not have legitimately obtained a majority. Contradiction. Hence at most one leader per term.- Term monotonicity prevents "split-brain" via stale leaders: if any node sees a higher term, it steps down, so concurrent leaders across different terms are also prevented from persisting conflicting authority.

Why term numbers and voting restrictions enforce safety:- Term numbers serialize epochs; votes are tied to terms and persisted, so you cannot retroactively grant a vote to two candidates in same term.- The log-up-to-date predicate prevents electing a leader that might be missing committed entries, ensuring leaders elected in higher terms have logs at least as up-to-date as voters — this supports safety of committed entries.

Proposal to reduce election churn: Pre-vote (or leader stickiness)- Pre-vote: before incrementing currentTerm and starting a formal election, a candidate asks peers “would you grant me a vote?” without bumping term. Only if it gets a quorum of pre-votes does it increment term and start a real election.- Effect: during transient partitions or when a node is slightly behind, pre-votes prevent noisy elections that will fail because nodes refuse for log staleness or will cause term bumps that force leaders to step down unnecessarily.

Why this preserves election safety:- Pre-vote does not grant leadership nor persist votes; it only gauges viability. The actual election still follows Raft’s rules: when a candidate starts a real election it increments term, peers persist votedFor for that term and enforce at-most-one-vote-per-term and log-up-to-date checks. Thus the invariants used in the proof remain intact for real elections, so the majority-intersection argument still prevents two leaders in the same (real) term.- Term monotonicity remains: pre-vote uses no term increment, so it cannot violate monotonicity; real-term bumps still follow existing update rules.

Operational note (SRE perspective):- Implement pre-vote and tuned randomized election timeouts to reduce false leader churn. Monitor election rate, term bumps, and leader tenure; set alerts if election rate exceeds expected thresholds. Pre-vote reduces unnecessary leader changes while keeping Raft’s formal safety guarantees.

MediumTechnical

64 practiced

Describe and implement the algorithm for consistent hashing to shard keys across nodes. Explain how to use virtual nodes to improve balance, and provide pseudocode for key-to-node mapping, node join, and node leave. Analyze the expected fraction of keys that must move on membership changes.

Sample Answer

Consistent hashing maps both nodes and keys onto a circular hash ring (0..2^32-1). Each key is assigned to the first node clockwise from its hash. When nodes join/leave, only adjacent key ranges move, so rebalancing affects ~1/N of keys rather than all.

Use virtual nodes: place multiple hashes per physical node (vnodes). That reduces imbalance by averaging many small ranges per node.

Algorithm idea:- Hash(node_id + replica_index) -> vnode position on ring- Maintain sorted map of vnode_position -> physical_node- To map key: h = hash(key); find first vnode_position >= h (wrap to smallest); return its physical_node.

Pseudocode (Python-like):

python

import bisect
from hashlib import md5

class ConsistentHashRing:
    def __init__(self, vnode_count=100):
        self.vnode_count = vnode_count
        self.positions = []          # sorted list of vnode hashes (ints)
        self.position_to_node = {}   # map hash -> node_id

    def _hash(self, s):
        return int(md5(s.encode()).hexdigest(), 16)

    def add_node(self, node_id):
        for i in range(self.vnode_count):
            pos = self._hash(f"{node_id}:{i}") % (2**32)
            if pos in self.position_to_node:
                # rare collision; skip or linear probe
                continue
            bisect.insort(self.positions, pos)
            self.position_to_node[pos] = node_id

    def remove_node(self, node_id):
        to_remove = [p for p,n in self.position_to_node.items() if n==node_id]
        for p in to_remove:
            idx = bisect.bisect_left(self.positions, p)
            if idx < len(self.positions) and self.positions[idx]==p:
                self.positions.pop(idx)
            del self.position_to_node[p]

    def get_node(self, key):
        if not self.positions:
            return None
        h = self._hash(key) % (2**32)
        idx = bisect.bisect_right(self.positions, h)
        if idx == len(self.positions):
            idx = 0
        return self.position_to_node[self.positions[idx]]

Expected movement on membership change:- If there are N physical nodes and no vnodes, adding/removing one node moves ~1/N of keys (on average) because it takes one contiguous arc.- With V virtual nodes per physical node (total M = N*V vnodes), the expected fraction moved when a physical node joins/leaves ≈ V/M = 1/N, but variance is much lower — each vnode owns many small arcs so distribution approaches uniform; maximum imbalance drops roughly as O(1/√V).- Therefore expected key movement per membership change is ~1/N of keys; using vnodes reduces statistical deviation and hot spots.

Operational notes:- Choose vnode_count so N*V >> 1 (e.g., V=100-1000) for smooth balance.- Persist ring metadata, use consistent hashing for replication by taking next R distinct nodes clockwise.- Handle concurrency: perform join/leave via coordinated updates (gossip/consensus) and migrate keys for affected key ranges only.

EasyTechnical

91 practiced

You need to uniformly sample approximately 1% of a very high volume log stream for long-term archival, but you cannot store the full stream. Describe and implement reservoir sampling for sample size k in Python, and prove why the algorithm maintains a uniform sample.

Sample Answer

Approach: Use reservoir sampling to maintain a uniform random sample of size k over a stream you cannot store. Keep first k items, then for the i-th (1-based) item with i>k, accept it with probability k/i and if accepted, replace a random existing item in the reservoir.

python

import random

class ReservoirSampler:
    def __init__(self, k):
        assert k > 0
        self.k = k
        self.reservoir = []
        self.count = 0  # total items seen

    def process(self, item):
        self.count += 1
        i = self.count
        if i <= self.k:
            self.reservoir.append(item)
        else:
            # accept new item with probability k/i
            if random.random() < self.k / i:
                # replace a uniformly chosen existing element
                idx = random.randrange(self.k)
                self.reservoir[idx] = item

    def sample(self):
        return list(self.reservoir)

Why this is uniform (proof sketch):- Base: after first k items, each is in reservoir with probability 1.- Inductive step: assume after processing i items (i >= k) each item seen so far has probability k/i to be in reservoir. For item j ≤ i, when processing item i+1: - It survives if it was already in the reservoir (probability k/i) and not replaced by the new item (probability 1 - 1/(i+1) * (i+1)/k *? simpler:) alternative: show direct: new item chosen with prob k/(i+1). If new item chosen, it replaces a uniformly random slot, so any existing item is kicked with prob (k/(i+1))*(1/k)=1/(i+1). So an existing item remains with prob (k/i)*(1 - 1/(i+1)) = (k/i)*(i/(i+1)) = k/(i+1). New item has prob k/(i+1) by construction. Thus all i+1 items have equal probability k/(i+1).- So invariant holds; final reservoir is uniform.

Complexity:- Time: O(1) per item.- Space: O(k).

Edge cases & SRE notes:- If stream length < k, reservoir contains all items. Use a deterministic RNG seed for reproducible samples in tests. For very high throughput, implement in streaming worker, periodically snapshot reservoir to archive, and ensure thread-safety if sampling in parallel (shard streams and merge samples appropriately).

Unlock Full Question Bank

Get access to hundreds of Algorithmic Problem Solving interview questions and detailed answers.

Join thousands of developers preparing for their dream job.