DSA — Practical

DSA — Practical (canonical templates)

Sliding window (max sum subarray of size K)

def max_sum_k(a, k):
    s = sum(a[:k]); best = s
    for i in range(k, len(a)):
        s += a[i] - a[i-k]
        best = max(best, s)
    return best

Two pointers (3-sum)

def three_sum(nums):
    nums.sort()
    res = []
    for i, x in enumerate(nums):
        if i and nums[i] == nums[i-1]: continue
        l, r = i+1, len(nums)-1
        while l < r:
            s = x + nums[l] + nums[r]
            if s == 0:
                res.append([x, nums[l], nums[r]])
                l += 1; r -= 1
                while l < r and nums[l] == nums[l-1]: l += 1
                while l < r and nums[r] == nums[r+1]: r -= 1
            elif s < 0: l += 1
            else: r -= 1
    return res

Longest substring without repeating chars

def longest_unique(s):
    seen = {}; left = 0; best = 0
    for r, c in enumerate(s):
        if c in seen and seen[c] >= left:
            left = seen[c] + 1
        seen[c] = r
        best = max(best, r - left + 1)
    return best

Binary search (lower_bound)

def lower_bound(a, target):
    lo, hi = 0, len(a)
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] < target: lo = mid + 1
        else: hi = mid
    return lo

BFS shortest path on grid

from collections import deque
def shortest(grid, start, end):
    R, C = len(grid), len(grid[0])
    q = deque([(start, 0)])
    seen = {start}
    while q:
        (r, c), d = q.popleft()
        if (r, c) == end: return d
        for dr, dc in [(1,0),(-1,0),(0,1),(0,-1)]:
            nr, nc = r+dr, c+dc
            if 0 <= nr < R and 0 <= nc < C and grid[nr][nc] != '#' and (nr,nc) not in seen:
                seen.add((nr,nc))
                q.append(((nr,nc), d+1))
    return -1

DFS / topological sort

def topo(n, edges):
    adj = [[] for _ in range(n)]
    indeg = [0]*n
    for u, v in edges:
        adj[u].append(v); indeg[v] += 1
    q = deque(i for i in range(n) if indeg[i] == 0)
    order = []
    while q:
        u = q.popleft(); order.append(u)
        for v in adj[u]:
            indeg[v] -= 1
            if indeg[v] == 0: q.append(v)
    return order if len(order) == n else None    # cycle

Dijkstra

import heapq
def dijkstra(adj, src):
    INF = float('inf')
    dist = [INF]*len(adj); dist[src] = 0
    pq = [(0, src)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]: continue
        for v, w in adj[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
    return dist

DP — coin change (min coins)

def coin_change(coins, amount):
    INF = amount + 1
    dp = [0] + [INF]*amount
    for a in range(1, amount+1):
        for c in coins:
            if a >= c:
                dp[a] = min(dp[a], dp[a-c]+1)
    return dp[amount] if dp[amount] != INF else -1

DP — LIS O(n log n)

from bisect import bisect_left
def lis(a):
    tails = []
    for x in a:
        i = bisect_left(tails, x)
        if i == len(tails): tails.append(x)
        else: tails[i] = x
    return len(tails)

DP — edit distance

def edit(a, b):
    m, n = len(a), len(b)
    dp = [[0]*(n+1) for _ in range(m+1)]
    for i in range(m+1): dp[i][0] = i
    for j in range(n+1): dp[0][j] = j
    for i in range(1, m+1):
        for j in range(1, n+1):
            if a[i-1] == b[j-1]: dp[i][j] = dp[i-1][j-1]
            else: dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
    return dp[m][n]

LRU cache (OrderedDict)

from collections import OrderedDict
class LRU:
    def __init__(self, cap): self.c = OrderedDict(); self.cap = cap
    def get(self, k):
        if k not in self.c: return -1
        self.c.move_to_end(k)
        return self.c[k]
    def put(self, k, v):
        if k in self.c: self.c.move_to_end(k)
        self.c[k] = v
        if len(self.c) > self.cap: self.c.popitem(last=False)

Trie

class Trie:
    def __init__(self):
        self.children = {}
        self.end = False
    def insert(self, w):
        node = self
        for c in w:
            node = node.children.setdefault(c, Trie())
        node.end = True
    def search(self, w):
        node = self
        for c in w:
            if c not in node.children: return False
            node = node.children[c]
        return node.end
    def starts_with(self, p):
        node = self
        for c in p:
            if c not in node.children: return False
            node = node.children[c]
        return True

Backtracking template

def backtrack(state, choices, result):
    if is_solution(state):
        result.append(snapshot(state))
        return
    for c in choices:
        if not valid(state, c): continue
        apply(state, c)
        backtrack(state, choices, result)
        undo(state, c)

Top K (heap)

import heapq
def top_k(nums, k):
    return heapq.nlargest(k, nums)

# top K frequent
def top_k_freq(nums, k):
    cnt = Counter(nums)
    return [w for w, _ in cnt.most_common(k)]

Quickselect (Kth largest, expected O(n))

import random
def kth_largest(nums, k):
    target = len(nums) - k
    lo, hi = 0, len(nums)-1
    while True:
        p = partition(nums, lo, hi)
        if p == target: return nums[p]
        if p < target: lo = p+1
        else: hi = p-1

def partition(a, lo, hi):
    pivot = a[random.randint(lo, hi)]
    i = lo
    for j in range(lo, hi+1):
        if a[j] < pivot:
            a[i], a[j] = a[j], a[i]; i += 1
    return i  # boundary; for full implementation, see standard refs

Number of islands (DFS)

def num_islands(grid):
    R, C = len(grid), len(grid[0])
    def dfs(r, c):
        if r<0 or r>=R or c<0 or c>=C or grid[r][c] != '1': return
        grid[r][c] = '0'
        for dr,dc in ((1,0),(-1,0),(0,1),(0,-1)): dfs(r+dr, c+dc)
    n = 0
    for r in range(R):
        for c in range(C):
            if grid[r][c] == '1':
                n += 1; dfs(r, c)
    return n

Merge intervals

def merge(intervals):
    intervals.sort()
    out = [intervals[0]]
    for s, e in intervals[1:]:
        if s <= out[-1][1]:
            out[-1][1] = max(out[-1][1], e)
        else:
            out.append([s, e])
    return out

System-design coding problems (non-algorithmic but commonly asked)

These are the “implement X from scratch” problems senior interviewers reach for when they want to see how you wire data structures into real components — closer to engineering than to puzzles. The interviewer cares about correctness, thread/async safety, and that you can name the trade-offs out loud while coding.

LRU cache — from scratch (Map + doubly linked list)

JS Map already preserves insertion order, so the trick version uses delete + set to move a key to the end (Stripe/Cloudflare engineers reach for this in 3 lines). The interviewer usually wants the explicit doubly-linked-list version though — it shows you understand the underlying structure and generalises to LFU, TTL eviction, write-through cache, etc.

class DLLNode<K, V> {
  prev: DLLNode<K, V> | null = null;
  next: DLLNode<K, V> | null = null;
  constructor(public key: K, public value: V) {}
}

export class LRUCache<K, V> {
  private readonly map = new Map<K, DLLNode<K, V>>();
  private readonly head: DLLNode<K, V>;             // sentinel — MRU side
  private readonly tail: DLLNode<K, V>;             // sentinel — LRU side

  constructor(private readonly capacity: number) {
    if (capacity <= 0) throw new RangeError('capacity must be > 0');
    this.head = new DLLNode<K, V>(null as never, null as never);
    this.tail = new DLLNode<K, V>(null as never, null as never);
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }

  get size(): number { return this.map.size; }

  get(key: K): V | undefined {
    const node = this.map.get(key);
    if (!node) return undefined;
    this.unlink(node);
    this.addFront(node);
    return node.value;
  }

  put(key: K, value: V): void {
    const existing = this.map.get(key);
    if (existing) {
      existing.value = value;
      this.unlink(existing);
      this.addFront(existing);
      return;
    }
    if (this.map.size >= this.capacity) {
      const lru = this.tail.prev!;
      this.unlink(lru);
      this.map.delete(lru.key);
    }
    const node = new DLLNode(key, value);
    this.addFront(node);
    this.map.set(key, node);
  }

  private unlink(node: DLLNode<K, V>): void {
    node.prev!.next = node.next;
    node.next!.prev = node.prev;
  }

  private addFront(node: DLLNode<K, V>): void {
    node.prev = this.head;
    node.next = this.head.next;
    this.head.next!.prev = node;
    this.head.next = node;
  }
}

Map shortcut version (mention it after the explicit one to show you also know the JS-idiomatic answer):

export class LRUMap<K, V> {
  private readonly m = new Map<K, V>();
  constructor(private readonly cap: number) {}
  get(k: K): V | undefined {
    if (!this.m.has(k)) return undefined;
    const v = this.m.get(k)!;
    this.m.delete(k); this.m.set(k, v);             // move to end = most recent
    return v;
  }
  set(k: K, v: V): void {
    if (this.m.has(k)) this.m.delete(k);
    else if (this.m.size >= this.cap) this.m.delete(this.m.keys().next().value);
    this.m.set(k, v);
  }
}

Talking points while coding: sentinel head/tail removes the null-checks at the ends (Sedgewick’s standard trick); both get and put are O(1) — Map gives O(1) hash lookup, DLL gives O(1) splice; for LFU mention the Shim & Park O(1) algorithm (two linked lists indexed by frequency); for TTL/expiry mention a min-heap on expiry timestamps or a lazy “check on read” pattern. Node single-threaded event loop = no locking needed; if asked about worker-thread access mention SharedArrayBuffer + Atomics or just “use Redis.”

Token-bucket rate limiter (lazy refill on read)

Asked anywhere request limits are a product feature — Stripe, GitHub, CDNs, internal API gateways. Wrong answer: a setInterval topping up every second. Right answer: compute tokens lazily from elapsed time on each call.

export class TokenBucket {
  private tokens: number;
  private lastRefillNs: bigint;

  constructor(
    private readonly capacity: number,
    private readonly refillPerSec: number,
  ) {
    this.tokens = capacity;
    this.lastRefillNs = process.hrtime.bigint();
  }

  /** Returns true if `cost` tokens were available and consumed. */
  allow(cost = 1): boolean {
    this.refill();
    if (this.tokens >= cost) {
      this.tokens -= cost;
      return true;
    }
    return false;
  }

  /** ms until `cost` tokens will be available (0 if already). */
  retryAfterMs(cost = 1): number {
    this.refill();
    if (this.tokens >= cost) return 0;
    return Math.ceil(((cost - this.tokens) / this.refillPerSec) * 1000);
  }

  private refill(): void {
    const now = process.hrtime.bigint();
    const elapsedSec = Number(now - this.lastRefillNs) / 1e9;
    this.tokens = Math.min(this.capacity, this.tokens + elapsedSec * this.refillPerSec);
    this.lastRefillNs = now;
  }
}

Distributed version (atomic Lua on Redis — same algorithm, replicated state):

// KEYS[1] = bucket key, ARGV = capacity, refillPerSec, nowMs, cost
const LUA = `
  local key = KEYS[1]
  local cap = tonumber(ARGV[1])
  local rate = tonumber(ARGV[2])
  local now = tonumber(ARGV[3])
  local cost = tonumber(ARGV[4])
  local data = redis.call('HMGET', key, 'tokens', 'ts')
  local tokens = tonumber(data[1]) or cap
  local ts = tonumber(data[2]) or now
  tokens = math.min(cap, tokens + (now - ts) / 1000 * rate)
  if tokens < cost then
    redis.call('HMSET', key, 'tokens', tokens, 'ts', now)
    redis.call('PEXPIRE', key, math.ceil(cap / rate * 1000))
    return 0
  end
  redis.call('HMSET', key, 'tokens', tokens - cost, 'ts', now)
  redis.call('PEXPIRE', key, math.ceil(cap / rate * 1000))
  return 1
`;
const allowed = await redis.eval(LUA, 1, `rl:${userId}`, 100, 10, Date.now(), 1);

Talking points: process.hrtime.bigint() (or performance.now()) instead of Date.now() because wall clock can jump (NTP, leap seconds, manual time changes); lazy refill removes the need for a per-bucket timer; cost parameter handles “this endpoint is expensive — charge 5 tokens”; in a distributed system mention the single-key Redis Lua version above (atomic, no race); for smooth output rate use leaky bucket instead — token bucket allows bursts up to capacity, leaky bucket enforces constant drain rate.

Bounded async queue (producer/consumer primitive)

Node has no real “blocking” — await yields to the event loop instead. The shape is the same: enqueue resolves only when there’s space; dequeue resolves only when there’s an item. Uses a deferred-promise queue rather than condition variables.

type Deferred<T> = { resolve: (v: T) => void; reject: (e: unknown) => void };

export class BoundedAsyncQueue<T> {
  private readonly buf: T[] = [];
  private readonly waitingProducers: Array<{ item: T; d: Deferred<void> }> = [];
  private readonly waitingConsumers: Array<Deferred<T>> = [];
  private closed = false;

  constructor(private readonly capacity: number) {
    if (capacity <= 0) throw new RangeError('capacity must be > 0');
  }

  enqueue(item: T): Promise<void> {
    if (this.closed) return Promise.reject(new Error('queue closed'));
    // hand directly to a waiting consumer — skip the buffer entirely
    const consumer = this.waitingConsumers.shift();
    if (consumer) { consumer.resolve(item); return Promise.resolve(); }
    if (this.buf.length < this.capacity) {
      this.buf.push(item);
      return Promise.resolve();
    }
    // full — park the producer until a slot opens
    return new Promise<void>((resolve, reject) => {
      this.waitingProducers.push({ item, d: { resolve, reject } });
    });
  }

  dequeue(): Promise<T> {
    if (this.buf.length > 0) {
      const item = this.buf.shift()!;
      // a producer was parked — admit them into the freed slot
      const parked = this.waitingProducers.shift();
      if (parked) { this.buf.push(parked.item); parked.d.resolve(); }
      return Promise.resolve(item);
    }
    if (this.closed) return Promise.reject(new Error('queue closed'));
    return new Promise<T>((resolve, reject) => {
      this.waitingConsumers.push({ resolve, reject });
    });
  }

  close(): void {
    this.closed = true;
    for (const p of this.waitingProducers) p.d.reject(new Error('queue closed'));
    for (const c of this.waitingConsumers) c.reject(new Error('queue closed'));
    this.waitingProducers.length = 0;
    this.waitingConsumers.length = 0;
  }

  get size(): number { return this.buf.length; }
}

Talking points: Node is single-threaded so no locks — but you do have the same logical races. Two separate waiter lists (producers vs consumers) avoid the spurious-wake / lost-wake bugs that plague single-CV implementations in threaded languages; direct hand-off (consumer waiting → producer skips buffer) reduces memory churn and matches Go channel semantics; close() must reject pending waiters or callers hang forever; for backpressure-aware streams mention Node’s built-in Readable/Writable with highWaterMark — the same idea built into stdlib.

Async event emitter / pub-sub (with once, ordering, error policy)

The exact “implement Node’s EventEmitter for me” question. Sounds trivial — until they add “make emit await all async listeners” or “what happens if a listener throws.”

type Handler<Args extends unknown[]> = (...args: Args) => void | Promise<void>;

interface EmitOptions {
  parallel?: boolean;        // default false — sequential
  bail?: boolean;            // default false — collect errors, don't stop
}

export class AsyncEmitter<EventMap extends Record<string, unknown[]>> {
  private readonly listeners = new Map<keyof EventMap, Array<{ h: Handler<any>; once: boolean }>>();

  on<E extends keyof EventMap>(event: E, handler: Handler<EventMap[E]>): () => void {
    const arr = this.listeners.get(event) ?? [];
    arr.push({ h: handler, once: false });
    this.listeners.set(event, arr);
    return () => this.off(event, handler);
  }

  once<E extends keyof EventMap>(event: E, handler: Handler<EventMap[E]>): void {
    const arr = this.listeners.get(event) ?? [];
    arr.push({ h: handler, once: true });
    this.listeners.set(event, arr);
  }

  off<E extends keyof EventMap>(event: E, handler: Handler<EventMap[E]>): void {
    const arr = this.listeners.get(event);
    if (!arr) return;
    this.listeners.set(event, arr.filter((l) => l.h !== handler));
  }

  async emit<E extends keyof EventMap>(
    event: E,
    args: EventMap[E],
    { parallel = false, bail = false }: EmitOptions = {},
  ): Promise<Array<unknown>> {
    const arr = this.listeners.get(event) ?? [];
    // snapshot + drop once-only BEFORE awaiting so handlers can on/off mid-emit safely
    this.listeners.set(event, arr.filter((l) => !l.once));
    const snapshot = arr.slice();

    if (parallel) {
      const settled = await Promise.allSettled(snapshot.map((l) => l.h(...args)));
      const errors = settled
        .filter((s): s is PromiseRejectedResult => s.status === 'rejected')
        .map((s) => s.reason);
      if (bail && errors.length) throw errors[0];
      return settled.map((s) => (s.status === 'fulfilled' ? s.value : s.reason));
    }

    const results: unknown[] = [];
    for (const l of snapshot) {
      try { results.push(await l.h(...args)); }
      catch (e) { if (bail) throw e; results.push(e); }
    }
    return results;
  }
}

// Typed usage — TS enforces event payload shapes
type Events = {
  'order.created': [orderId: string, total: number];
  'order.shipped': [orderId: string];
};
const bus = new AsyncEmitter<Events>();
bus.on('order.created', async (id, total) => { /* id: string, total: number */ });
await bus.emit('order.created', ['o-1', 199]);

Talking points: typed event map (Record<string, unknown[]>) gives compile-time payload safety — Node’s stdlib EventEmitter is untyped and a frequent runtime-error source; snapshot the listener array before the first await so a handler can on/off mid-emit without breaking the iteration (the canonical mid-level bug); Promise.allSettled instead of Promise.all for parallel dispatch — one rejected handler should not lose results from the others; bail policy mirrors EventEmitter’s default (sync throw stops the loop); for production scale mention backpressure (a slow listener stalls fast producers — fix with a per-listener bounded queue) and memory leaks (the well-known process.setMaxListeners warning that catches it).

---

Why these four. They cover the four primitives senior backend interviews keep returning to: caching with eviction (LRU), flow control (rate limiter), concurrency coordination (blocking queue), and event-driven dispatch (emitter). If you can write all four cleanly in 25 minutes each with the trade-offs spoken aloud, almost every “implement X” round is a known shape.

Test plan template

For a coding round, after writing solution, verbally test:

• Empty input.
• Single element.
• All same elements.
• Already sorted / reverse sorted.
• Very large (mention: O() guarantees this).
• Negatives (if applicable).
• Off-by-one boundaries.

Practice resources

• LeetCode 75 / NeetCode 150 / Blind 75.
• Cracking the Coding Interview.
• Elements of Programming Interviews.
• AlgoExpert / Educative DP courses.
• LeetCode Discuss for diverse approaches.