Study

Data structures 18

How to hold data so the operations you need are cheap.

Hash maps and setsTurn a key into an array index so lookup, insert and delete take constant time on average. The default tool for "have I seen this?".Counting and frequency tablesTally how often each value occurs in one pass, then answer "how many", "which most", "is there enough" questions in O(1) each.Arrays and in-place manipulationContiguous memory gives O(1) indexing and fast scans; in-place tricks with read/write pointers and swaps rearrange data without extra space.String manipulationStrings are immutable arrays of characters in all three languages; know the builder pattern, char-code arithmetic and split semantics to avoid quiet O(n²) bugs.StacksLast in, first out. A stack remembers what's still open so the most recent unfinished thing is always one O(1) step away.Monotonic stack / queueA stack or deque kept in sorted order answers "next greater", "previous smaller" and "max of this window" for every element in O(n) total.Queues and dequesFirst in, first out. Queues drive BFS, schedulers and time windows; a ring buffer gives O(1) enqueue and dequeue in fixed memory.Heaps and priority queuesA complete binary tree stored in an array that always hands you the smallest (or largest) item in O(1) and repairs itself in O(log n).Linked listsNodes joined by pointers. Insert or remove in O(1) once you hold a node; sentinels and careful splicing make the pointer surgery bug-free.Binary treesNodes with at most two children; nearly every tree question is a traversal plus a decision about what each node returns to its parent.Binary search trees / ordered mapsA binary tree kept in sorted order, so lookup, insert, delete, min/max and "nearest key" queries all cost O(height), which balance keeps at O(log n).TriesA tree of characters where every path from the root spells a prefix, so prefix lookups cost O(length of the key), not O(number of keys).Union-find (disjoint set union)Track which items are in the same group as groups merge, answering "connected?" in near-constant time with two tiny tricks.Graph representationAdjacency lists, adjacency matrices and edge lists store the same graph with very different costs; choosing well is the first step of every graph problem.Segment trees and Fenwick treesTrees of precomputed range summaries that answer range queries and absorb point updates in O(log n) each, where a plain prefix-sum array would pay O(n) per update.Sorted containers and bisectKeep values in order and find positions by binary search; know exactly what bisect_left and bisect_right return and which sorted structure each language gives you.Grids and matricesA 2-D array indexed by (row, column). Master the traversal orders, direction vectors, bounds checks and in-place transforms that every grid problem reuses.Bit manipulationTreat an integer as a row of switches. AND, OR, XOR and shifts give O(1) set operations, parity tricks and compact state, if you respect each language's integer width.

Algorithms & patterns 28

Reusable shapes of solutions: windows, searches, DP, graphs.

Complexity analysisCount how work and memory grow with input size, so you can pick an algorithm from the constraints and defend it out loud.Sorting and custom comparatorsHow comparison sorts work, why stability matters, and how to sort by several keys correctly in Python, TypeScript and C#.Two pointersWalk two indices through an array, from both ends or in the same direction, to replace an O(n²) pair search with one O(n) pass.Sliding windowScan a contiguous range once by growing the right edge and shrinking the left, turning O(n·k) or O(n²) scans into O(n).Prefix sums and difference arraysPrecompute running totals once so any range sum is one subtraction, and batch range updates as two writes each.Binary searchHalve the candidates on every step by asking a yes/no question whose answers flip exactly once, on arrays or on the answer itself.RecursionSolve a problem by solving smaller copies of itself; understand the call stack it builds, what that costs, and when to replace it.BacktrackingBuild a solution one decision at a time, abandon a partial choice as soon as it can't work, and undo it to try the next; the standard way to enumerate or search combinatorial spaces.Breadth-first searchExplore a graph in rings of increasing distance using a FIFO queue; the standard way to get fewest-step shortest paths in unweighted graphs and grids.Depth-first searchFollow one path as deep as it goes, then back up and try the next; the engine behind reachability, flood fill, cycle detection and topological order.Topological sort and cycle detectionLine up the nodes of a directed graph so every edge points forward, or prove it can't be done because of a cycle.Shortest paths (Dijkstra, Bellman-Ford, 0-1 BFS)Find the cheapest route through a weighted graph, and pick the right algorithm for the weights you have: non-negative, negative, or just 0 and 1.Minimum spanning treesConnect every node of a weighted graph as cheaply as possible; Kruskal and Prim both do it greedily, thanks to one property about cuts.IntervalsSort by start, then a single left-to-right pass decides overlap, merging and conflicts. O(n log n), and the endpoint convention matters.Sweep lineTurn intervals into sorted start and end events, then walk them once with a running count. Tie-breaking at equal coordinates decides correctness.Greedy algorithmsCommit to the locally best choice and never look back. Fast and simple, but only correct when you can prove the choice is safe.Dynamic programming: 1DDefine the answer for a prefix, write how it depends on smaller prefixes, and fill a 1-D table left to right. Exponential recursion becomes O(n).Dynamic programming: 2DWhen a state needs two indices (two prefixes, a cell in a grid, a range), fill a table in dependency order and walk back to recover the answer.Dynamic programming: advanced shapesFour recurring DP state shapes beyond prefixes. Recognise the shape, and the state, fill order and complexity follow.MemoizationCache the result of a pure recursive function by its arguments so each subproblem is solved once. Top-down dynamic programming.Divide and conquerSplit a problem into smaller copies of itself, solve them recursively, and combine the answers; the master theorem tells you what it costs.Math and number handlingOverflow, integer division and modulo, gcd, modular arithmetic and floating point, and how Python, TypeScript and C# differ on each.Randomized algorithms and samplingShuffling, reservoir sampling and O(1) random picks, plus how randomness protects quicksort and hashing from worst-case inputs.String algorithmsLinear-time pattern matching with the prefix function (KMP) and the Z-function, plus where hashing, tries and suffix structures fit.Step-by-step simulationModel a system's rules exactly and advance it through time, tick by tick or event by event, with deterministic, testable updates.Search over states: position plus extra stateWhen where you are isn't enough to decide what happens next, make the search node a tuple of position and extra state, and BFS or Dijkstra over that.Rolling hash (Rabin-Karp)Hash a string as a number in base B modulo M, and update a window's hash in O(1) as it slides. Fast substring comparison, with collisions to manage.Knapsack and subset selectionChoose items under a budget with a table over (item, capacity). 0/1 vs unbounded differ by one index, or by the loop direction in 1-D.

Object & API design 11

Classes with invariants, caches, versioning, undo: the stateful-system rounds.

Class design and invariantsChoose a class's fields from the operations it must support, write down what must always be true, and guard it so the next level's changes stay cheap.API design and evolutionShape method signatures, return values and errors so callers can't misuse them, and change them later without breaking anyone.State machinesModel a lifecycle as states, events and a transition table so illegal moves are impossible to make by accident and easy to reject on purpose.Iterators, generators and resumable stateProduce values one at a time on demand. Generators in Python, TypeScript and C#, lazy pipelines, and iterators whose position you can save and restore.Caching and eviction (LRU, LFU)Keep the most useful results in bounded memory. How LRU, LFU and FIFO choose what to throw away, and the structures that make each O(1).TTL and expiryMake data disappear on schedule. Lazy versus active expiry, a heap of deadlines, half-open time intervals, and clocks you inject instead of reading.Versioning, history and point-in-time queriesKeep every version instead of overwriting, then answer "what was the value at time t?" with a sorted version list and one binary search.Snapshots, backup and restoreFreeze a store's state so you can read or restore it later. Full copies, copy-on-write sharing and version stamps, and what each costs.Undo / redo and command patternTwo stacks and a rule about forking history. Store edits as invertible commands or as saved copies (mementos), and know what each costs.Secondary indexes and query designAnswer "find by X" without scanning everything. Keep extra maps in sync with the primary data, and pick SQL index columns in the right order.Designing for the next requirementWrite level 1 so level 2, 3 and 4 are small edits, without building a framework nobody asked for. A worked example across three levels.

Real-world engineering 12

Parsing, money, ledgers, idempotency: the messy parts of real code.

Parsing and tokenizingTurn raw text into structured data in two clean passes, a tokenizer then a recursive-descent parser, with errors that say exactly where input went wrong.Expression evaluationTurn infix text like 3 + 4 * 2 into a value by respecting precedence and associativity, via shunting-yard to postfix or a syntax tree.Input validation and error handlingCheck untrusted input once at the boundary, report errors the caller can act on, and choose deliberately between exceptions and result values.Money: integer cents, rounding, currenciesRepresent money as integers in a currency's minor unit, round once with a named rule, and split amounts so no cent is created or lost.Ledgers and double entryRecord every movement of money as balanced, append-only entries and derive balances from them, so the books can always be checked and explained.Idempotency and deduplicationMake retried requests and redelivered messages safe, so a flaky network can never charge a customer twice or apply an event twice.Reconciliation and matchingProve two record sets agree by matching them on normalized keys, then a tolerance, and reporting every leftover as a break to investigate.Timestamps, windows and timeUse half-open intervals, epoch instants, explicit time zones and an injected clock so time-based logic has no off-by-one, DST or flaky-test bugs.Permissions and access controlDecide who may do what to which resource, using roles, lists or attributes, with default deny, deny overrides and expiring grants.Paths and hierarchical namespacesSplit, normalize and resolve slash-separated paths with a stack, and store hierarchies as a tree of maps with O(depth) lookups.Aggregation, grouping and reportingBucket rows by a key, fold each bucket into a summary, then rank and cut with explicit tie-breaks, in code and in SQL.Order books and trading mechanicsHow a limit order book ranks bids and asks by price then time, how incoming orders match and partially fill, and the vocabulary trading interviews assume.

Systems & concurrency 11

Schedulers, rate limits, streaming, sharding and races.

Rate limitingCap how many requests a client may make per unit of time, choosing between exact logs, cheap counters and token buckets.Scheduling and task queuesDecide which waiting job runs next (FIFO, priority, round robin, EDF), and make queued work survive crashes with leases, retries and backoff.Event-driven simulation and timersKeep future events in a priority queue ordered by time, then repeatedly pop the earliest one. It powers timers, schedulers and deterministic simulations.Concurrency semanticsRaces, critical sections, deadlocks and the ordering guarantees of threads, asyncio, the JS event loop and .NET tasks, made visible step by step.Streaming and online algorithmsAnswer questions about data you see once, in order, with memory that stays fixed no matter how long the stream runs.Resource allocation and quotasHand out a finite resource (memory, cores, slots, budget) fairly and without waste, and refuse cleanly when it runs out.Dependency resolutionTurn "X needs Y" rules into a safe order, spot cycles, find what can run in parallel, and pick versions that satisfy every constraint.Load balancing and consistent hashingSpread requests and keys across servers so none is overloaded, and add or remove servers while moving as little data as possible.Distributed systems reasoningSplit data across machines (sharding), copy it for safety (replication), and reason about quorums, clocks, ids and repair when no single machine knows everything.Crawling and graph exploration over servicesExplore a graph you can only see one fetch at a time, with a frontier, a seen set, canonical keys, bounded concurrency and per-host politeness.Memory efficiencyKnow what each element really costs in your language, then pack, bound or stream your data so it fits with room to spare.

Engineering craft 4

Edge cases, testing, debugging, adapting when requirements change.

Edge cases and boundary conditionsA systematic checklist of the inputs that break code (empty, one, duplicates, negatives, overflow, unicode, boundaries, ties) and how to cover them fast.Testing and verificationHow to prove your code works during an interview, from a hand trace to table-driven tests, property checks and a brute-force oracle.DebuggingA repeatable method for finding bugs under pressure: reproduce, minimize, hypothesize, bisect, verify, with hand-tracing and loop invariants as the main tools.Adapting to changing requirementsHow multi-level coding rounds work, how to design level 1 so levels 2-4 are additions, and when to refactor instead of patching.

Design deep dives 20

Classic systems designed end to end: requirements, estimates, architecture, the hard parts and how they fail.

Rate limiterDesign an API rate limiter end to end, from the per-key algorithm to many gateways sharing one count without becoming the outage.Distributed cacheTake an LRU/TTL cache from one process to a memcached or Redis cluster, and keep it fast, fresh and from taking the database down.Event-driven order pipelineDesign an order pipeline on a partitioned event log, from per-key ordering and the outbox to sagas, dead letters, lag and replay.Distributed job queueDesign a background job queue with leases, heartbeats, retries with jittered backoff, dead letters, tenant fairness, delayed and cron jobs.Key-value storeDesign a Dynamo/Cassandra-style distributed key-value store, from the log-structured storage engine on one disk to quorums, repair and conflicts.URL shortenerDesign a link shortener end to end, from collision-free short keys to a cached redirect path that serves a million clicks a second.Web crawlerDesign a crawler that fetches billions of pages politely, never fetches the same thing twice, and doesn't fall into infinite traps.Payment systemDesign a Stripe-style payments API that never charges twice, survives processor timeouts, and keeps a ledger that always balances.Notification systemDesign multi-channel notifications (push, email, SMS, in-app) with preferences, priorities, rate caps, dedupe, provider failover, quiet hours and digests.News feedDesign a home timeline end to end, from fan-out on write versus read to celebrity accounts, ranking and stable pagination.Chat systemDesign 1:1 and group chat end to end, from WebSocket gateways and per-conversation ordering to receipts, offline sync and multiple devices.TypeaheadDesign search autocomplete end to end, from an offline pipeline over query logs to an in-memory prefix index answering every keystroke in milliseconds.Unique ID generatorGenerate unique, roughly time-ordered ids across thousands of machines without a round trip per id, and survive clocks that misbehave.Metrics pipelineDesign a Prometheus or Datadog style monitoring system, from scraping counters to compressed time series, rollups, percentiles and alerts.LeaderboardDesign a global game leaderboard for 100M players with live top-K, exact rank, around-me views, time windows and sharding.File syncDesign Dropbox or Google Drive style file sync, from chunking and content hashes to the sync protocol, change notifications and conflicted copies.Webhook deliveryDesign Stripe-style outbound webhooks: fan-out, signed payloads, retries over days, endpoint health, and isolating slow customer servers.LLM inference servingDesign an LLM API like Anthropic's, from token-based rate limits and queues to continuous batching, KV cache paging and streaming.Ticket bookingDesign a Ticketmaster-style booking system that sells each seat exactly once while millions of fans race for the same few rows.Proximity serviceDesign "find nearby" for places and for moving drivers, with geohash, quadtrees and S2/H3 cells, read-heavy indexes and write-heavy location stores.