Practical Assessments

A colleague reports that this binary search sometimes throws `IndexError` and sometimes never returns at all. The input `nums` is sorted ascending and may be empty. Find every bug without running the code.

A routing service computes single-source shortest paths with the implementation below. Unit tests pass, but on the production graph `dist[3]` comes back as `4` although a path of cost `2` exists: `0 → 2 → 1 → 3` with weights `5, -4, 1`. Edges are given as `(u, v, w)`. The code itself is a textbook Dijkstra. Find the problem.

This function is supposed to return the length of the longest strictly increasing subsequence. It returns `4` for `[10, 9, 2, 5, 3, 7, 101, 18]` (correct) but `5` for `[3, 1, 2, 5, 4, 6]` where the answer is `4` (`1, 2, 4, 6` or `1, 2, 5, 6`). Find the bug.

A grid path finder works on small mazes but on a 1000×1000 open grid it runs for minutes and the queue grows to millions of entries. Distances are still correct on the small tests. Diagnose it.

Two functions from a code review. `count_nodes` should count reachable nodes in an undirected graph given as an adjacency list; `sum_digits` should add the decimal digits of a non-negative integer. Both crash with `RecursionError: maximum recursion depth exceeded` on ordinary inputs. Find the cause of each.

A dashboard shows the `k` highest scores out of `n` (`n` up to 10⁸ streamed from disk, `k = 100`). The current implementation is correct but runs out of memory and is slow. A junior engineer "fixed" the memory issue in `top_k_v2`, which is now wrong. Diagnose both versions.

This function should count contiguous subarrays whose sum equals `k`. It passes all tests with positive numbers but returns `2` for `nums = [1, -1, 1, -1]`, `k = 0` — the correct answer is `4` (`[1,-1]`, `[-1,1]`, `[1,-1]` and `[1,-1,1,-1]`). Explain why and fix it.

This function finds whether any two distinct elements of `nums` add up to `target`. It times out for `n = 10⁵`. Make it fast enough, and discuss the trade-offs of the two standard approaches.

An analytics endpoint answers `q = 10⁵` queries of the form "sum of `values[l..r]`" over an array of `n = 10⁵` daily totals. It is too slow. Then a second requirement lands: values can also be **updated** between queries. Optimize both versions.

This function returns the start indices of every substring of `s` that is an anagram of `p` (lowercase letters, `|s| = 3·10⁴`, `|p|` up to `3·10⁴`). It is correct but too slow when `p` is long. Optimize it to linear time.

You receive millions of numbers as a stream — one at a time, never all in memory — and at any moment you must be able to report the 20 largest seen so far. Choose a data structure and justify it against the alternatives.

A service caches responses keyed by request id. Memory allows at most `capacity` entries. When full, evict the entry that has not been used for the longest time. Both `get` and `put` must be `O(1)`. Choose the data structures and explain why simpler options fail.

A build system has tasks, each listing the tasks that must finish before it can start. Produce a valid execution order, or report that none exists. Later, the team asks for the *maximum parallelism*: which tasks can run at the same time. Choose the model and algorithm.

Design the data structure behind a search box that, after each keystroke, shows the 10 most popular completions of the current prefix. The dictionary has 10⁷ terms with popularity counts; queries arrive at 10⁴ per second; popularity counts change over time. Cover the core structure, top-k retrieval, memory, updates and caching.

Design a component that ingests a stream of numbers and can return the median of everything seen so far at any time. Ingest must be fast; queries are frequent. Then extend it to a *sliding* median over the last `w` values.

A range-sum service precomputes prefix sums over up to `10^5` sensor readings, each up to `10^9`. Small test files pass, but on production data `rangeSum(0, n - 1)` returns a *negative* number, and the binary search that locates the first prefix `>= target` occasionally reads out of bounds. Find every bug.

A cache-eviction routine removes every expired entry from an `unordered_map` and every non-positive value from a `vector`. Under AddressSanitizer both loops report heap-use-after-free; without it the program sometimes skips elements and sometimes segfaults. Find the bug in each loop.

This connected-components counter is textbook DFS, and it returns correct answers. Yet on a graph with `2 · 10^5` vertices and `2 · 10^5` edges it takes 40 seconds and uses gigabytes of memory, while the same algorithm in Python finishes in under a second. Nothing is wrong with the algorithm. Find the bug.

A candidate submits this solution to a variant of two-sum that must also return the *values* at the two positions. It passes but is flagged as "far too slow" on `n = 10^6` — the profiler shows almost all time inside `std::list` and `std::map` internals. The algorithm is the standard one-pass hash approach. Why is it slow, and what did the candidate misunderstand about the STL?

This Dijkstra passes on tiny graphs but on larger ones returns distances that are sometimes too large, and the profiler shows far more heap pops than expected — nearly one per edge relaxation rather than one per settled vertex. The graph has only non-negative weights. Find the bug.

A k-th smallest helper and a "meeting rooms" interval merge both sort their input first. Tests with single-digit numbers pass, but `kthSmallest([10, 2, 5, 33, 4], 1)` returns `10` and the interval merge produces overlapping output when start times exceed 9. Find the bug.

A word-frequency service uses a plain object as a hash map. Two bug reports: (1) counting the word `"constructor"` returns a function-like garbage value instead of a number; (2) a coordinate-visited set keyed by `[row, col]` treats every cell as already visited after the first one. Find both bugs.

This shortest-path BFS on a grid is correct and runs instantly on a `100 × 100` grid, but on a `2000 × 2000` open grid it takes minutes. The reviewer says "the algorithm is O(V + E), so it must be the machine". Prove them wrong.

A data-cleaning step removes duplicates from a stream of parsed values and then finds the index of a target. Users report that `0`, `""`, `false` and `null` collapse into one value, that `NaN` is never found even when present, and that `indexOf(NaN)` returns `-1`. Find every equality bug.

A Rabin–Karp matcher and a bitmask DP both work in C++ and were ported line by line to JavaScript. The JS version reports false matches on long strings, the DP "visits" states it never set, and a factorial helper returns the wrong value for `n = 21`. Find the three numeric bugs.

A hand-rolled binary heap backs a Dijkstra implementation. The project compiles clean with `strict: true`, and the unit tests — which push plain numbers — all pass. In production the heap holds `{ dist, node }` entries, and suddenly `pop()` returns them in an arbitrary wrong order, so Dijkstra settles vertices with non-final distances. Not a single red squiggle anywhere. Find the bug and explain why the compiler let it through.

A BFS over string-keyed graphs compiles clean under `strict: true`. At runtime, building the adjacency map throws `TypeError: Cannot read properties of undefined (reading 'push')` on the very first edge. A teammate "fixed" it by pre-seeding the map, and now every distance except the source comes out as `NaN`. Both failures trace back to the same character. Find it.

A `topK` utility takes an options object. One caller consistently gets the three *smallest* scores instead of the three largest — but only in one file. The options object is identical character-for-character to a working call elsewhere, except that it is built in a `const` first and passed by name. Everything compiles under `strict: true`. Explain what TypeScript checked, what it deliberately did not, and fix the API so the mistake cannot recur.

A leaderboard library exposes `sortBy(items, key)` and `maxBy(items, key)`, generic over any object type. Sorting players by `score` works perfectly and is covered by tests. Sorting by `name` returns the players in their original insertion order — no error, no warning — and `maxBy(players, 'name')` always returns whichever player happens to be first. The code compiles clean under `strict: true`. Find the bug, and explain why the compiler *did* try to prevent it.

A crawler loads its settings from a JSON file: a maximum crawl depth and a per-page-type score weight table. The loader compiles clean under `strict: true` and every type reads correctly in the IDE. In production the crawler dies two ways: `scorePage` throws `TypeError: Cannot read properties of undefined (reading 'article')` deep in the scoring pass, and on another config file the crawl recurses until `RangeError: Maximum call stack size exceeded`. Neither stack trace mentions the config loader. Find the real bug and say why both crashes surface so far from it.

A staircase-paths counter with memoization returns correct answers — the first time. Called again with a *different* set of allowed step sizes, it returns the answer from the previous configuration. A tree helper has the same disease: `collect_leaves(tree)` returns `[2, 3]` on the first call and `[2, 3, 2, 3]` on the second, with the same tree. Each function works in isolation and fails only across calls. Find the bug.

An island counter builds a `visited` grid with `[[False] * cols] * rows` and runs a standard DFS flood fill. On the sample grid it reports 2 islands instead of 3. Stranger: printing `visited` after marking a single cell shows the mark appearing in *every row at once*. The DFS itself is correct. Find the bug.

A task scheduler is supposed to run tasks highest-priority first. Instead it runs them lowest-first, and the moment two tasks share a priority it crashes with `TypeError: '<' not supported between instances of 'Task' and 'Task'`. The heap operations themselves are used correctly. Find both bugs.

A connected-components counter passes every unit test — small random graphs, stars, cliques. On the first production input, a road network containing one long chain of `100,000` nodes, it dies with `RecursionError: maximum recursion depth exceeded`. The same algorithm in C++ handles the input fine. A teammate proposes `sys.setrecursionlimit(10**9)` as the fix. Evaluate that proposal, find the real issue, and fix it properly.

A shortest-path BFS over a grid returns correct distances and sails through the `100 × 100` test suite. On a `1000 × 1000` open grid it takes minutes, and a profiler attributes nearly all the time to a single innocuous-looking line: `queue.pop(0)`. The algorithm is textbook BFS. Explain the slowdown, quantify it, and fix it with the right standard-library tool.