Backend engineer coding interview questions

As asked

You are implementing a server-side in-memory cache for a Node.js API that stores expensive database query results. It must evict the least recently used entry when capacity is reached. Implement an LRU cache class with get(key) and put(key, value) in O(1) time. Explain your data structure choices in terms of memory layout and how they behave under high-concurrency API traffic.

Sample answer outline

Use a doubly linked list to track access order (most recent at head, LRU at tail) and a hash map from key to list node for O(1) lookup. put moves the node to the head; get also moves the node to the head. When capacity is exceeded, remove the tail node and its hash map entry. A strong answer mentions that JavaScript's Map preserves insertion order and can be used for a simpler implementation, and handles the edge case where put is called with an existing key (update value, promote to head).

Reference implementation (javascript)

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.map = new Map();
  }

  get(key) {
    if (!this.map.has(key)) return -1;
    const value = this.map.get(key);
    this.map.delete(key);
    this.map.set(key, value);
    return value;
  }

  put(key, value) {
    if (this.map.has(key)) this.map.delete(key);
    this.map.set(key, value);
    if (this.map.size > this.capacity) {
      this.map.delete(this.map.keys().next().value);
    }
  }
}

Expect these follow-ups

• How would you make this thread-safe in a Go or Java implementation?
• How would you modify this to support a TTL per key in addition to LRU eviction?

As asked

Your backend service aggregates maintenance windows from multiple infrastructure providers. Each window is a [startEpoch, endEpoch] pair. Write a function that merges overlapping windows so you can report the true total downtime periods. For example, [[1,3],[2,6],[8,10],[15,18]] should return [[1,6],[8,10],[15,18]].

Sample answer outline

Sort by start time. Iterate through intervals, extending the current interval's end if the next interval's start is within the current end. Push to result when no overlap. Time complexity O(n log n) due to sort. A strong answer mentions the edge case where two intervals share an endpoint ([1,3],[3,5] should merge to [1,5]) and confirms the output is sorted.

Reference implementation (javascript)

function merge(intervals) {
  intervals.sort((a, b) => a[0] - b[0]);
  const result = [];
  for (const interval of intervals) {
    if (!result.length || result[result.length - 1][1] < interval[0]) {
      result.push([...interval]);
    } else {
      result[result.length - 1][1] = Math.max(result[result.length - 1][1], interval[1]);
    }
  }
  return result;
}

Expect these follow-ups

• How would you solve this if the input were a stream of intervals arriving in real time?
• What is the time complexity if the input is already sorted?

As asked

Given a string, find the first character that does not repeat anywhere in the string. If no such character exists, return an empty character or null. Optimize for a single pass through the string.

Sample answer outline

Two-pass approach: first pass builds a frequency hashmap, second pass scans left to right and returns the first character with count 1. A true single-pass approach uses an ordered map or a list of (char, first_index) pairs updated as you scan. A strong candidate mentions character set assumptions (ASCII vs Unicode), handles uppercase vs lowercase, and asks whether the empty string should raise or return a sentinel.

Reference implementation (python)

def first_unique_char(s: str) -> str:
    count = {}
    for ch in s:
        count[ch] = count.get(ch, 0) + 1
    for ch in s:
        if count[ch] == 1:
            return ch
    return ''

Expect these follow-ups

• What if the string is too large to fit in memory and arrives as a stream?
• Extend this to find the first character that appears exactly K times.

As asked

Airbnb's listing availability service caches per-listing calendar data to avoid hitting the database on every search request. Implement an LRU (Least Recently Used) cache that supports get and put in O(1) time. Then explain how you would extend it to be thread-safe in a Node.js or Java service.

Sample answer outline

The canonical solution uses a doubly linked list for O(1) removal combined with a hash map for O(1) lookup. The candidate should walk through get (move node to head), put (insert at head, evict tail if at capacity), and explain pointer bookkeeping. For thread safety they should discuss synchronizing the composite operation, or using a read-write lock.

Reference implementation (python)

class LRUCache:
    def __init__(self, capacity: int):
        self.cap = capacity
        self.cache = {}  # key -> node
        # sentinel head and tail
        self.head, self.tail = Node(0, 0), Node(0, 0)
        self.head.next = self.tail
        self.tail.prev = self.head

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        self._move_to_head(self.cache[key])
        return self.cache[key].val

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            node = self.cache[key]
            node.val = value
            self._move_to_head(node)
        else:
            node = Node(key, value)
            self.cache[key] = node
            self._add_to_head(node)
            if len(self.cache) > self.cap:
                tail = self._remove_tail()
                del self.cache[tail.key]

Expect these follow-ups

• What changes if you need the cache to be distributed across multiple servers?
• How would you add a TTL expiry to each entry without breaking O(1) operations?

As asked

Airbnb uses tree structures internally, for example to represent hierarchical location data (continent, country, city, neighborhood). Implement serialization and deserialization of a binary tree. The serialized form can be any format you choose, as long as the deserialized tree is identical to the original. Discuss your format choice before coding.

Sample answer outline

A clean solution uses BFS with null markers, encoding as a comma-separated string. The candidate should explain why they chose BFS over DFS (often simpler to reconstruct), handle null nodes explicitly, and walk through reconstruction using a queue of values. Edge cases include single-node trees and all-null children.

Reference implementation (python)

from collections import deque

def serialize(root):
    if not root:
        return 'null'
    result, queue = [], deque([root])
    while queue:
        node = queue.popleft()
        if node:
            result.append(str(node.val))
            queue.append(node.left)
            queue.append(node.right)
        else:
            result.append('null')
    return ','.join(result)

def deserialize(data):
    vals = data.split(',')
    if vals[0] == 'null':
        return None
    root = TreeNode(int(vals[0]))
    queue, i = deque([root]), 1
    while queue:
        node = queue.popleft()
        if vals[i] != 'null':
            node.left = TreeNode(int(vals[i]))
            queue.append(node.left)
        i += 1
        if vals[i] != 'null':
            node.right = TreeNode(int(vals[i]))
            queue.append(node.right)
        i += 1
    return root

Expect these follow-ups

• How would you change your approach if the tree had up to 10 million nodes and you needed to minimize serialized size?
• Can you serialize it in a way that lets you deserialize any subtree without reading the whole string?

As asked

Design a parking lot system that handles multiple levels, different vehicle types (motorcycle, car, bus), and can tell you whether a spot is available. Walk me through your class design first, then write the core classes.

Sample answer outline

A strong answer starts with clarifying questions about scale, pricing, and vehicle types before writing code. Core classes should include ParkingLot, Level, ParkingSpot (with a type enum), and Vehicle (with a size property). The candidate should use polymorphism so different vehicle types check availability correctly, and should handle the edge case where a bus takes multiple spots. Interviewers look for clean separation of concerns and good use of OOP principles, not just a working sketch.

Reference implementation (python)

class ParkingSpot:
    def __init__(self, spot_type: str):
        self.spot_type = spot_type  # 'compact', 'large', 'motorcycle'
        self.is_occupied = False
        self.vehicle = None

    def can_fit(self, vehicle: 'Vehicle') -> bool:
        raise NotImplementedError

    def park(self, vehicle: 'Vehicle') -> bool:
        if self.can_fit(vehicle) and not self.is_occupied:
            self.vehicle = vehicle
            self.is_occupied = True
            return True
        return False

Expect these follow-ups

• How would you extend this to support reservations?
• How would you make it thread-safe if multiple entry gates are updating spot availability concurrently?

As asked

Implement a rate limiter class that allows at most N requests per time window T (in seconds) per user. It should support isAllowed(user_id, timestamp) which returns true if the request is allowed and false if it should be throttled. Timestamps are in seconds and may arrive slightly out of order.

Sample answer outline

A strong answer implements a sliding window using a deque or sorted list of recent timestamps per user. For each request, remove timestamps older than (current_time - T) from the window, then check if the window size is below N before adding the current timestamp. Time complexity is O(N) per call in the worst case. The candidate should contrast this with a fixed window counter (simpler but has edge-case burst at window boundaries) and a token bucket (better for bursty traffic, harder to implement exactly).

Reference implementation (python)

from collections import defaultdict, deque

class RateLimiter:
    def __init__(self, n: int, t: int):
        self.n = n
        self.t = t
        self.windows: dict[str, deque] = defaultdict(deque)

    def is_allowed(self, user_id: str, timestamp: int) -> bool:
        window = self.windows[user_id]
        cutoff = timestamp - self.t
        while window and window[0] <= cutoff:
            window.popleft()
        if len(window) < self.n:
            window.append(timestamp)
            return True
        return False

Expect these follow-ups

• How would you implement this rate limiter in a distributed system where requests for the same user hit different servers?
• How does a token bucket differ from a sliding window in terms of burst handling?

As asked

You have a Spark DataFrame with columns start and end representing time intervals. Write a PySpark transformation that merges all overlapping intervals and returns the minimal set of non-overlapping intervals. For example, [(1,3),(2,6),(8,10),(15,18)] becomes [(1,6),(8,10),(15,18)].

Sample answer outline

The candidate should describe the algorithm: sort by start, then use a window function or fold to track the current maximum end and detect whether each interval merges with the previous one. A clean Spark approach uses Window.orderBy('start') and lag to detect gap boundaries, then groups by boundary and takes min(start)/max(end) per group. Alternatively, the candidate can collectAsList on smaller datasets and apply the linear scan algorithm. They should discuss the tradeoffs between a full Spark SQL approach versus collecting to driver.

Reference implementation (python)

from pyspark.sql import functions as F
from pyspark.sql.window import Window

df = spark.createDataFrame([(1,3),(2,6),(8,10),(15,18)], ["start","end"])

w = Window.orderBy("start")
df2 = df.withColumn(
    "prev_max_end",
    F.max("end").over(w.rowsBetween(Window.unboundedPreceding, -1))
).withColumn(
    "new_group",
    F.when(F.col("start") > F.col("prev_max_end"), 1).otherwise(0)
).withColumn("group_id", F.sum("new_group").over(w))

result = df2.groupBy("group_id").agg(
    F.min("start").alias("start"),
    F.max("end").alias("end")
).orderBy("start")

Expect these follow-ups

• How does your approach change if intervals can come from multiple sources and you need to stream merge them?
• What is the time complexity of the distributed version compared to the single-machine version?

As asked

Write a PySpark job that reads a 1TB text file from cloud storage and returns the top 100 most frequent words, excluding common English stop words. Walk me through your implementation and the performance choices you make.

Sample answer outline

The candidate should split lines into words, lowercase and strip punctuation, filter stop words using a broadcast variable, count occurrences, and use top() or orderBy with limit. Key performance choices: broadcasting the stop word set avoids a shuffle join, using flatMap then countByValue is correct but aggregating with reduceByKey is more scalable than groupByKey. They should use Spark's built-in functions (explode, lower, regexp_replace) for efficiency over Python UDFs.

Reference implementation (python)

from pyspark.sql import functions as F

stop_words = spark.sparkContext.broadcast(
    set(["the", "a", "an", "is", "in", "it", "of", "and", "to"])
)

df = spark.read.text("s3://bucket/large-file.txt")

result = (
    df.select(F.explode(F.split(F.lower(F.regexp_replace("value", "[^a-zA-Z ]", "")), " ")).alias("word"))
    .filter(F.col("word") != "")
    .filter(~F.col("word").isin(list(stop_words.value)))
    .groupBy("word")
    .count()
    .orderBy(F.desc("count"))
    .limit(100)
)

Expect these follow-ups

• Why is groupByKey a bad choice here, and what does reduceByKey do differently?
• If the output had to update incrementally as new files arrive, how would you change the approach?

As asked

Implement a thread-safe sliding-window rate limiter in Go. It should allow at most N requests per user per minute, use O(1) memory per user (not storing every request timestamp), and return whether the current request is allowed along with the number of remaining requests in the window.

Sample answer outline

A strong answer implements a token bucket or sliding-window counter using atomic operations or a mutex-protected struct, explains the tradeoff between the exact sliding log (O(N) memory, precise) and the sliding window counter approximation (O(1) memory, slightly imprecise near window boundaries), and handles the concurrent access correctly. The candidate should mention Redis sorted sets as the production approach for distributed rate limiting.

Reference implementation (go)

type RateLimiter struct {
    mu       sync.Mutex
    counters map[string]*windowCounter
    limit    int
    window   time.Duration
}

type windowCounter struct {
    prevCount  int
    currCount  int
    windowStart time.Time
}

func (rl *RateLimiter) Allow(userID string) (bool, int) {
    rl.mu.Lock()
    defer rl.mu.Unlock()
    // TODO: implement sliding window logic
    return false, 0
}

Expect these follow-ups

• How would you make this work across multiple API server instances?
• What happens to accuracy at the window boundary with a counter-based approach versus a log-based approach?

As asked

Implement an LRU cache that supports get(key) and put(key, value) both in O(1) time. The cache has a fixed capacity; when it is full, evict the least recently used entry before inserting a new one. Use any language you prefer.

Sample answer outline

The canonical solution uses a doubly linked list for O(1) eviction from both ends and a hash map for O(1) key lookup, with sentinel head and tail nodes to simplify boundary conditions. Strong candidates implement the move-to-front logic cleanly, handle the capacity-one edge case, and note that Python's OrderedDict gives this for free if the interviewer allows it.

Reference implementation (python)

class LRUCache:
    def __init__(self, capacity: int):
        pass

    def get(self, key: int) -> int:
        # Return -1 if not found
        pass

    def put(self, key: int, value: int) -> None:
        pass

Expect these follow-ups

• How would you make this cache thread-safe for concurrent access?
• What changes if you need the cache to be persistent across process restarts?

As asked

Given the path to a root directory, write a function that returns groups of files that have identical content. Assume the directory tree can contain millions of files and the total data can be hundreds of gigabytes. How do you do this efficiently, and how do you avoid reading every file fully?

Sample answer outline

A strong approach first groups by file size (eliminating obvious non-duplicates), then hashes only the first 4KB of each same-size group to eliminate more, then fully hashes the remaining candidates. This avoids reading most data. The candidate should mention using SHA-256 or similar, handle hash collisions gracefully, and discuss parallelising the I/O with a thread pool. Very relevant to Dropbox's actual deduplication work.

Reference implementation (python)

import os, hashlib
from collections import defaultdict

def find_duplicates(root: str) -> list[list[str]]:
    # Return list of groups; each group is a list of paths with identical content
    by_size = defaultdict(list)
    for dirpath, _, filenames in os.walk(root):
        for f in filenames:
            path = os.path.join(dirpath, f)
            by_size[os.path.getsize(path)].append(path)
    # ... continue
    pass

Expect these follow-ups

• How would you handle symbolic links and circular directory references?
• If you had to run this incrementally on a live directory that is changing, how would your approach differ?

As asked

Design an algorithm to serialize a binary tree to a string and deserialize that string back to the original tree. Your serialization format must handle any binary tree, not just BSTs. What format do you choose and why?

Sample answer outline

A strong answer uses preorder traversal with explicit null markers (e.g., 'null') so the structure is recoverable from a single pass. The candidate should implement both functions cleanly, handle empty trees, discuss why inorder alone is insufficient for reconstruction, and note that for very deep trees an iterative solution avoids stack overflow.

Reference implementation (python)

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def serialize(root: TreeNode) -> str:
    pass

def deserialize(data: str) -> TreeNode:
    pass

Expect these follow-ups

• How does your format change if the values are arbitrary strings that might contain your delimiter character?
• Could you reconstruct the tree from level-order (BFS) serialization? What are the tradeoffs?

As asked

Given an array of integers and a target sum, return the indices of the two numbers that add up to the target. Assume exactly one solution exists. First give me a brute force approach, then optimize it. After that: if I told you the input array is sorted, how does your solution change? And finally, what if I needed you to find all unique pairs, not just one?

Sample answer outline

A strong candidate moves from O(n^2) brute force to O(n) hash map immediately and explains the space-time tradeoff. For the sorted variant they pivot to two pointers in O(n) time O(1) space. For all unique pairs they handle duplicates by skipping repeated elements at each pointer position. Google wants to see fluency in choosing the right data structure, not just knowing the answer.

Reference implementation (python)

def two_sum(nums: list[int], target: int) -> list[int]:
    seen = {}
    for i, n in enumerate(nums):
        complement = target - n
        if complement in seen:
            return [seen[complement], i]
        seen[n] = i
    return []

Expect these follow-ups

• What if the numbers could overflow a 32-bit integer?
• How would you test this function?

As asked

Lyft's API gateway needs to enforce per-user rate limits across a distributed fleet of backend servers. Implement a rate limiter that enforces a sliding-window limit of N requests per minute per user ID. You can use Redis. Write the core logic and explain your choice of data structure.

Sample answer outline

Strong answers use a Redis sorted set with timestamps as scores, add each request with ZADD, remove entries older than 60 seconds with ZREMRANGEBYSCORE, and count with ZCARD, all in a Lua script for atomicity. They also discuss the trade-off with fixed-window (simpler but bursty) and token bucket (smoother but more state).

Reference implementation (python)

import redis

def is_allowed(r: redis.Redis, user_id: str, limit: int, window_secs: int) -> bool:
    key = f"rl:{user_id}"
    now_ms = int(time.time() * 1000)
    window_start = now_ms - window_secs * 1000
    pipe = r.pipeline()
    pipe.zremrangebyscore(key, 0, window_start)
    pipe.zadd(key, {str(now_ms): now_ms})
    pipe.zcard(key)
    pipe.expire(key, window_secs + 1)
    results = pipe.execute()
    count = results[2]
    return count <= limit

Expect these follow-ups

• What happens to your rate limiter if the Redis node goes down?
• How would you rate-limit by IP instead of user ID for unauthenticated endpoints?

As asked

OpenAI's inference stack needs to cache KV (key-value) states and decoded outputs to serve repeated or similar prompts efficiently. As a warm-up, implement a general LRU cache that supports two operations: get(key) returns the value if the key exists, otherwise -1; put(key, value) inserts or updates the key, evicting the least-recently-used key when the cache is at capacity. Both operations must run in O(1) time.

Sample answer outline

The candidate should reach for a doubly-linked list paired with a hash map. They should explain why a doubly-linked list allows O(1) removal (you need the prev pointer) and why the hash map stores node references, not just keys. A strong answer handles edge cases: capacity of 1, overwriting an existing key without duplicating the node, and moving the accessed node to the head correctly.

Reference implementation (python)

class LRUCache:
    def __init__(self, capacity: int):
        self.cap = capacity
        self.cache = {}  # key -> node
        # sentinel head and tail
        self.head = Node(0, 0)
        self.tail = Node(0, 0)
        self.head.next = self.tail
        self.tail.prev = self.head

    def get(self, key: int) -> int:
        ...

    def put(self, key: int, value: int) -> None:
        ...

Expect these follow-ups

• How would you make this thread-safe for concurrent access?
• What changes if you need to support a TTL on each entry in addition to LRU eviction?

As asked

Write a function that returns true if a request from a given user ID should be allowed, given a limit of N requests per M seconds. Use an in-memory sliding window approach. Assume this runs in a single process.

Sample answer outline

Maintain a map from user ID to a slice or circular buffer of timestamps. On each call, remove timestamps older than M seconds from the front, then check if the count exceeds N. If not, append the current timestamp and return true. A strong answer uses a mutex for concurrent safety, discusses time.Now() as the clock source (mockable in tests), and notes that this does not work across multiple processes without a shared store like Redis.

Reference implementation (go)

import (
  "sync"
  "time"
)

type RateLimiter struct {
  mu       sync.Mutex
  requests map[string][]time.Time
  limit    int
  window   time.Duration
}

func (r *RateLimiter) Allow(userID string) bool {
  r.mu.Lock()
  defer r.mu.Unlock()
  now := time.Now()
  cutoff := now.Add(-r.window)
  times := r.requests[userID]
  // TODO: filter times >= cutoff, check len vs limit
  _ = times; _ = cutoff
  return false
}

Expect these follow-ups

• How would you adapt this to use Redis sorted sets for a distributed implementation?
• What is the memory complexity of this approach with 100,000 unique users?

As asked

Your analytics backend receives a stream of API endpoint hit counts and needs to report the k most called endpoints for a dashboard. Given an array of endpoint IDs and a number k, return the k most frequent IDs. Your solution must run faster than O(n log n). For example, [1,1,1,2,2,3] with k=2 returns [1,2].

Sample answer outline

Count frequencies with a hash map in O(n). Use a min-heap of size k to maintain the top-k elements; replace the minimum if a new element has higher frequency. Total time O(n log k). Alternatively, use bucket sort where index equals frequency, collecting from the highest bucket down. A strong answer identifies the bucket approach as O(n) and explains the trade-off: heap is better when k is small and n is large; bucket sort requires extra O(n) space.

Reference implementation (javascript)

function topKFrequent(nums, k) {
  const freq = new Map();
  for (const n of nums) freq.set(n, (freq.get(n) || 0) + 1);
  const buckets = Array.from({ length: nums.length + 1 }, () => []);
  for (const [num, count] of freq) buckets[count].push(num);
  const result = [];
  for (let i = buckets.length - 1; i >= 0 && result.length < k; i--) {
    result.push(...buckets[i]);
  }
  return result.slice(0, k);
}

Expect these follow-ups

• How would you solve the streaming variant where new elements arrive continuously and you need the current top-k at any moment?
• How does the min-heap approach change if k is close to n?

As asked

Your backend stores sorted partition IDs for a sharded database, but a deployment bug rotated the sorted array at an unknown pivot. Write a function to locate a given partition ID in O(log n) time so recovery tooling can find the correct shard quickly. For example, searching for 0 in [4,5,6,7,0,1,2] returns index 4. Return -1 if the ID is not present.

Sample answer outline

Use standard binary search but determine which half is sorted by comparing nums[mid] to nums[left]. In the sorted half, check if target is within the range; if yes, search there; otherwise search the other half. A strong answer handles duplicates (a harder variant) by incrementing left when nums[left] == nums[mid], and notes that duplicates degrade worst case to O(n).

Reference implementation (javascript)

function search(nums, target) {
  let left = 0, right = nums.length - 1;
  while (left <= right) {
    const mid = (left + right) >> 1;
    if (nums[mid] === target) return mid;
    if (nums[left] <= nums[mid]) {
      if (target >= nums[left] && target < nums[mid]) right = mid - 1;
      else left = mid + 1;
    } else {
      if (target > nums[mid] && target <= nums[right]) left = mid + 1;
      else right = mid - 1;
    }
  }
  return -1;
}

Expect these follow-ups

• How does this change if the array may contain duplicates?
• How would you find the rotation pivot index instead of a specific target?

As asked

Your backend URL router needs to split a URL path string into valid route segments using a dictionary of known route tokens. Given a path string and a set of valid tokens, determine if the path can be fully segmented into valid tokens with no characters left over. For example, path 'userprofile' with tokens ['user','profile'] returns true.

Sample answer outline

Use a boolean DP array of length n+1 where dp[i] means the substring s[0..i) can be segmented. For each position i, check all positions j < i where dp[j] is true and s[j..i) is in the dictionary. Time O(n^2 * m) where m is dictionary lookup time. Using a Set for the dictionary makes lookups O(1). A strong answer also mentions the trie optimization when the dictionary is very large.

Reference implementation (javascript)

function wordBreak(s, wordDict) {
  const words = new Set(wordDict);
  const dp = new Array(s.length + 1).fill(false);
  dp[0] = true;
  for (let i = 1; i <= s.length; i++) {
    for (let j = 0; j < i; j++) {
      if (dp[j] && words.has(s.slice(j, i))) {
        dp[i] = true;
        break;
      }
    }
  }
  return dp[s.length];
}

Expect these follow-ups

• How would you modify this to return all possible segmentations instead of just true/false?
• What is the time complexity if the dictionary contains words up to length L?

As asked

Write a Go function that takes a slice of URLs, fetches each one concurrently with a max concurrency of 5, and returns all the response bodies. Use goroutines and channels. Handle errors per URL without aborting the whole pipeline.

Sample answer outline

Use a semaphore channel of capacity 5 to limit concurrency. Spawn one goroutine per URL, acquire the semaphore before fetching, release after. Collect results via a results channel. Use sync.WaitGroup to know when all goroutines finish, then close the results channel. A strong answer passes a context with timeout, handles the case where a fetch error should be included in results (not silently dropped), and avoids goroutine leaks by always releasing the semaphore in a defer.

Reference implementation (go)

func fetchAll(ctx context.Context, urls []string) []Result {
  sem := make(chan struct{}, 5)
  results := make(chan Result, len(urls))
  var wg sync.WaitGroup
  for _, url := range urls {
    wg.Add(1)
    go func(u string) {
      defer wg.Done()
      sem <- struct{}{}
      defer func() { <-sem }()
      // TODO: perform http.Get(u), send Result to results
    }(url)
  }
  go func() { wg.Wait(); close(results) }()
  var out []Result
  for r := range results { out = append(out, r) }
  return out
}

Expect these follow-ups

• How would you add a timeout so that any single fetch cannot take more than 3 seconds?
• How would you cancel all remaining fetches if the first error occurs?

As asked

Your backend needs to persist in-memory decision trees to a document store and reconstruct them on service restart. Design an algorithm to serialize a binary tree to a string and deserialize that string back to the original structure, suitable for storage in Postgres or Redis. The tree can contain any integer values including duplicates.

Sample answer outline

BFS or pre-order DFS both work. Pre-order DFS: serialize by writing node value then left subtree then right subtree; write 'null' for missing children. Deserialize by splitting on delimiter and using a queue or index pointer to reconstruct. A strong answer notes that in-order alone is insufficient for reconstruction, discusses delimiter choice (avoid values that appear in data), and analyzes time complexity O(n) for both operations.

Reference implementation (javascript)

function serialize(root) {
  if (!root) return 'null';
  return `${root.val},${serialize(root.left)},${serialize(root.right)}`;
}

function deserialize(data) {
  const vals = data.split(',');
  let i = 0;
  function build() {
    if (vals[i] === 'null') { i++; return null; }
    const node = new TreeNode(+vals[i++]);
    node.left = build();
    node.right = build();
    return node;
  }
  return build();
}

Expect these follow-ups

• How would you handle a tree with very large integer values efficiently?
• How does your approach change for an n-ary tree?

As asked

Implement a tiled matrix multiplication in C or Python that improves cache utilization over the naive triple-loop version. Explain why tiling helps and what tile size you would choose.

Sample answer outline

A strong answer implements the three-loop GEMM with a blocking factor B, loading B x B tiles into local arrays before the inner product. The key insight is reuse: each element of A is read B times instead of N times, and same for B. Tile size is chosen so two tiles fit in L1 cache (typically 64 to 128 KB), so for float32 with 4 bytes each: sqrt(64KB/4/2) is roughly 90, so a tile of 64 or 128 is common. On AMD GPUs the equivalent is LDS tiling in a HIP kernel, where tile size matches the wavefront width.

Reference implementation (python)

def tiled_matmul(A, B, tile=64):
    N = len(A)
    C = [[0.0]*N for _ in range(N)]
    for ii in range(0, N, tile):
        for jj in range(0, N, tile):
            for kk in range(0, N, tile):
                for i in range(ii, min(ii+tile, N)):
                    for k in range(kk, min(kk+tile, N)):
                        a_ik = A[i][k]
                        for j in range(jj, min(jj+tile, N)):
                            C[i][j] += a_ik * B[k][j]
    return C

Expect these follow-ups

• How does the memory layout (row-major vs column-major) affect your tiling strategy?
• How would you add vectorization hints or use SIMD intrinsics to speed up the inner loop on a CPU?

As asked

Given a stream of Server-Sent Events from the Claude API where each event looks like `data: {"type": "content_block_delta", "delta": {"type": "text_delta", "text": "hello"}}`, write a function that accumulates the full text and returns the total character count once a `message_stop` event is received. Handle malformed events gracefully.

Sample answer outline

The function should iterate over SSE lines, skip comment and empty lines, parse the JSON payload after the `data: ` prefix, check the event type, and accumulate text from content_block_delta events. On message_stop it returns the accumulated string and its length. Malformed JSON should be caught and logged without crashing the accumulator.

Reference implementation (python)

def parse_sse_stream(lines: list[str]) -> tuple[str, int]:
    # lines is a sequence of raw SSE lines
    accumulated = []
    for line in lines:
        if not line.startswith('data: '):
            continue
        payload = line[len('data: '):]
        # TODO: parse payload, accumulate text, stop on message_stop
    return ''.join(accumulated), sum(len(s) for s in accumulated)

Expect these follow-ups

• How would you modify this to handle streaming tool use blocks in addition to text blocks?
• How would you test this without hitting the real API?

As asked

Write a class that enforces a sliding window rate limit of N requests per M seconds per user. The class should be thread-safe and must not use external libraries. The check method should return True if the request is allowed and False if it should be rejected.

Sample answer outline

A strong solution uses a collections.deque per user keyed in a dict, storing timestamps of allowed requests. On each call, it pops timestamps older than M seconds from the left, checks if the deque length is less than N, appends the current timestamp if allowed, and returns the result. Thread safety requires a threading.Lock around reads and writes. A good candidate notes that this is an in-process solution and does not scale horizontally.

Reference implementation (python)

import threading
from collections import deque
import time

class SlidingWindowRateLimiter:
    def __init__(self, max_requests: int, window_seconds: float):
        self.max_requests = max_requests
        self.window_seconds = window_seconds
        self._user_windows: dict[str, deque] = {}
        self._lock = threading.Lock()

    def is_allowed(self, user_id: str) -> bool:
        now = time.monotonic()
        # TODO: implement sliding window check
        pass

Expect these follow-ups

• How would you scale this to multiple server processes sharing state?
• What is the memory complexity of this approach if there are 100k active users?