Interview words without the professor voice.

A way to represent a graph where each node stores a list of its neighbors. More space-efficient than a matrix for sparse graphs (most real graphs). The go-to representation for coding interviews.

Example: Node 0 → [1, 2], Node 1 → [0, 3], Node 2 → [0]. That's a graph with 4 nodes and 4 edges.

Try a choice, go deeper, and if it leads to a dead end, UNDO the choice and try the next option. Like solving a maze by walking forward until you hit a wall, then going back to the last fork and trying a different path.

Example: Generate all valid parentheses: add '(' or ')' at each step, backtrack if it becomes invalid.

The simplest version of a recursive problem that you can answer directly without recursing further. Every recursion MUST have one, or it runs forever. The base case is where the recursion stops and actual answers start flowing back up.

Example: Factorial: base case is factorial(0) = 1. Without it, factorial(5) would call factorial(4) → factorial(3) → ... forever.

The round where the interviewer asks about past work to predict future behavior. 'Tell me about a time you disagreed with a teammate.' 'Tell me about a failure.' Behind every question is a specific signal the company is grading — ownership, leadership, conflict resolution, clarity under pressure. The wrong move is a rehearsed speech. The right move is a specific, first-person story with a clear outcome and honest reflection.

Example: Use the STAR method — Situation, Task, Action, Result — to keep your story under 3 minutes and make the signal obvious. Pick stories from the last 12 months; older ones read as stale.

Breadth-first search: explore all neighbors at the current depth BEFORE moving deeper. Uses a queue. Finds the shortest path in unweighted graphs. Think: ripple expanding outward from a stone dropped in water.

Example: Number of Islands: BFS from each unvisited '1', marking all connected land as visited. Each BFS call = one island.

How your algorithm's time or space grows as the input gets bigger. O(n) means it scales linearly — double the input, double the time. O(n²) means it scales quadratically — double the input, quadruple the time. It's about the SHAPE of growth, not the exact number.

Example: Nested loops over the same array: O(n²). Binary search: O(log n). Hash table lookup: O(1).

Cut the search space in half every step. Only works when the input is sorted (or has a monotonic property). The key insight: if the middle element is too big, the answer must be in the left half. Too small? Right half. O(log n).

Example: Search in a sorted array: check middle → go left or right → repeat. 1 billion elements? Only 30 checks.

Binary search tree: every node beats its whole left subtree and loses to its whole right subtree. That ordering is a contract, not a coincidence — it makes in-order traversal spit out sorted values, and it lets you find, insert, or delete in time proportional to the height. Balanced, that height is logarithmic; degenerate into a line and it is just a slow linked list.

Example: Validate a BST by carrying a (low, high) range down the recursion, not by comparing each node to its immediate children — a node can be larger than its parent yet still violate an ancestor bound.

A group of nodes in a graph where every node can reach every other node through some path. An isolated island in Number of Islands is one connected component. Counting them is one of the most common graph interview questions.

Example: A social network graph: each friend group that has no connections to other groups is a connected component.

Common Table Expression — a named temporary result set defined with WITH that exists only for the duration of one query. Makes complex queries readable by breaking them into named steps. Think of it as a local variable for SQL.

Example: WITH ranked AS (SELECT *, ROW_NUMBER() OVER (...) AS rn FROM orders) SELECT * FROM ranked WHERE rn = 1 — the CTE 'ranked' makes the query easy to read.

Depth-first search: go as deep as possible down one path before backtracking. Uses a stack (or recursion). Good for exhaustive search, cycle detection, and topological sorting. Think: exploring a cave — go until dead end, then back up.

Example: Generating all permutations: DFS explores every possible ordering by choosing one element at a time and backtracking.

A hash map from element to count — the bookkeeping trick behind half of all string/array interview problems. Build it once in O(n), then decrement as you shrink a window or match against a target. When every count hits zero, you've consumed the target.

Example: Valid Anagram (LC 242): a `frequency map` of `s` minus a `frequency map` of `t` should leave every count at zero — any non-zero count means the two strings aren't anagrams.

Always pick the option that looks best RIGHT NOW, without thinking about future consequences. Sometimes this gives the globally optimal answer (coin change with standard denominations). Sometimes it doesn't (and you need DP instead).

Example: Activity selection: always pick the activity that ends earliest. Greedy works here because early endings leave the most room for future activities.

A data structure that maps keys to values in average O(1) lookup, insert, and delete. It's the hidden engine behind half of all interview problems — Two Sum, Valid Anagram, LRU Cache, Group Anagrams, anything that needs 'have I seen this before?' in constant time. Under the hood: a hash function maps keys to array indices; collisions are resolved with chaining or open addressing.

Example: Two Sum: build a hash map of `value -> index` as you scan the array. For each `x`, check if `target - x` is already in the map. O(n) time, O(n) space, one pass.

The data structure behind the dictionary: a hash function maps a key to a bucket, so lookups, inserts, and deletes are roughly constant time instead of a linear scan. The cost is collisions — two keys landing in the same bucket — handled by chaining or open addressing, and a worst case that degrades to linear when the hashing goes pathological.

Example: A sliding-window frequency map is a hash table from character to count. Each step adds or removes one key in O(1), which is what keeps the whole window scan linear.

The rule that every parent node is smaller (min-heap) or larger (max-heap) than its children. This is what makes finding the minimum or maximum O(1) — it's always sitting at the top.

Example: In a min-heap, the root is always the smallest element. Pop it, and the heap fixes itself in O(log n).

Modifying the input directly without allocating extra space proportional to the input size. An in-place sort rearranges the array itself. A NOT-in-place sort creates a new array. Interviewers love this because it tests whether you understand space complexity.

Example: Reversing an array in-place: swap first and last, move inward. O(1) extra space.

A rule that stays true while your code runs. When the rule is true, the loop is safe to keep going. When it breaks, you move something, shrink something, or stop.

Example: Sliding window: the window has at most k distinct characters. If adding a character breaks that rule, move left until the rule is true again.

Saving the result of a function call so you don't compute it again. If `fib(5)` already ran, store the answer and return it instantly next time. The core trick behind dynamic programming.

Example: Without memoization, `fib(40)` makes billions of calls. With it, just 40.

A pointer is either an index you move through a list, or a reference to some object or node. In interview talk, it usually means: keep a finger on this position so you can move it later.

Example: Two pointers: `left` starts at index 0 and `right` starts at the end. Move one pointer when the current pair cannot be the answer.

A recurrence is the rule for getting the current answer from smaller answers. Before the formula looks fancy, ask: what tiny result do I already know, and how does it help this one?

Example: Climbing stairs: ways to reach step 5 = ways to reach step 4 + ways to reach step 3.

Joining a table to itself using two different aliases. Used when you need to compare rows within the same table — like finding employees who earn more than their managers, where both are rows in the Employee table.

Example: SELECT e.name FROM Employee e JOIN Employee m ON e.managerId = m.id WHERE e.salary > m.salary — compares each employee row against their manager row in the same table.

A fake value, fake node, or guard case you add so the real logic has fewer exceptions. It does not represent real input. It exists to make the loop easier to reason about.

Example: Largest Rectangle in Histogram: append a fake 0-height bar so the stack drains naturally at the end.

A technique where you maintain a 'window' (a subarray or substring) and slide it across the input, expanding or shrinking it as needed. Instead of checking every possible subarray (O(n²)), you check each element at most twice (O(n)).

Example: Longest substring without repeating characters: expand the window right, shrink from the left when you see a duplicate.

How much extra memory your algorithm uses as the input grows. A recursive DFS on a tree uses O(height) stack space. An extra hash set uses O(n) space. Interviewers test this because real systems have memory limits.

Example: In-place sort: O(1) extra space. Merge sort: O(n) extra space for the temporary array.

A query nested inside another query. It runs first, and its result feeds into the outer query. Subqueries can appear in WHERE (filtering), FROM (as a derived table), or SELECT (scalar value). Often replaceable by JOINs or CTEs for clarity.

Example: SELECT * FROM employees WHERE salary > (SELECT AVG(salary) FROM employees) — the inner query computes the average, the outer filters by it.

How many operations your algorithm performs as the input grows. Expressed in Big O notation. The interviewer's favorite follow-up question: 'what's the time complexity?' If you can't answer, you can't pass.

Example: Sorting: O(n log n). Linear scan: O(n). Nested loop: O(n²). Hash lookup: O(1).

Use two indices moving through an array — usually one from each end moving inward, or both starting at the beginning moving at different speeds. Turns O(n²) brute force into O(n) by eliminating impossible pairs early.

Example: Two Sum II (sorted array): left pointer at start, right at end. Sum too big? Move right left. Too small? Move left right.

A function that computes a value across a set of rows related to the current row WITHOUT collapsing them into one. Unlike GROUP BY, window functions keep every row visible. The OVER clause defines the 'window' — which rows to look at and in what order.

Example: RANK() OVER (PARTITION BY department ORDER BY salary DESC) ranks employees within each department without losing individual rows.

A Swift concurrency type that protects its mutable state by allowing only one task at a time to touch it. Instead of manually guarding access with locks, you isolate the state behind the actor and interact with it through `await`ed methods.

Example: An image cache actor can serialize reads and writes so two tasks never mutate the same dictionary at once. The caller uses `await cache.image(for:)` instead of reaching into shared state directly.

Some operations are expensive, but they happen rarely. Amortized means you spread those rare costs across all the cheap operations and ask what one operation costs on average over time.

Example: ArrayList.add() is O(1) amortized: most inserts are cheap, and the occasional resize gets spread across many inserts.

Automatic Reference Counting — Swift's memory management system that tracks how many strong references point at an object and deallocates it when that count hits zero. ARC is why `weak` and `unowned` exist: they change ownership so reference cycles do not keep objects alive forever.

Example: A view model and service that strongly reference each other never deallocate under ARC. Mark one side `weak` and ARC can drop both objects when the feature goes away.

A word for what happens when the input gets huge. It tells you to ignore tiny constants and focus on the growth shape: does the work grow like n, n log n, n squared, or something worse?

Example: Two solutions may both pass for n = 20. Asymptotic analysis asks which one still survives when n = 200,000.

An OS-scheduled wake-up that lets your app refresh data on its own cadence, without the user opening it. The schedule is the systems call, not yours — roughly every fifteen minutes on power, far less on battery — so design for unpredictable, infrequent runs rather than a reliable timer.

Example: A news app registers for background fetch so the morning headlines are already cached when the user unlocks their phone. On a low battery the OS may skip several cycles, so the app still refreshes on foreground.

Operations that act on the individual bits of a number (`&`, `|`, `^`, `~`, `<<`, `>>`) rather than the number as a whole. Faster than arithmetic and often unlocks tricks regular math can't — like toggling a flag without a branch, or testing a property in a single comparison.

Example: `n & (n - 1)` clears the lowest set bit, so 'is n a power of two?' becomes `n > 0 && (n & (n - 1)) == 0` — one bitwise op instead of a loop.

Keeping a copy of expensive work so you don't redo it. A hash map remembering computed results, a CDN serving static files, Redis standing in for a slow database query — they're all caches. The hard part isn't storing the copy. It's knowing when the copy goes stale and who's allowed to invalidate it.

Example: Looking up a user's avatar on every request hits the DB. Caching it in Redis with a 60s TTL drops that from one DB round-trip per request to roughly one per minute — at the cost of a 60s window where avatar changes don't show up.

The standard version people usually mean. A canonical problem, solution, or example is not the only possible one. It is the version the room expects you to recognize.

Example: Sliding Window Maximum is the canonical monotonic deque problem. Learn that shape and the smaller variants feel less mysterious.

Paging through a list by remembering WHERE you stopped instead of HOW MANY you skipped. The server hands back an opaque cursor pointing at the last item; the next request asks for whatever comes after it. Unlike offset pagination, new rows arriving mid-scroll do not shift everything down and make you re-see or skip items.

Example: A feed that loads 20 posts, then asks for the next 20 after cursor=eyJpZCI6.... New posts published while you scroll do not duplicate or drop entries, because the cursor anchors to an item, not a row number.

Finding whether a graph or linked list loops back on itself. In a linked list, use Floyd's tortoise and hare (slow + fast pointer). In a directed graph, use DFS with a 'currently visiting' state.

Example: Linked List Cycle: slow pointer moves 1 step, fast moves 2. If they meet, there's a cycle.

A bug where two concurrent pieces of code access the same mutable state at the same time and at least one access is a write. The bad part is not just wrong data — it is non-determinism. The same code can pass once and fail later with no visible input change.

Example: One task increments `count` while another reads and writes it on a different thread. Sometimes the final value is right, sometimes an update disappears. That's a data race.

A graph with directed edges and NO cycles. The foundation for dependency resolution, build systems, and topological sorting. If you can draw it without any arrows forming a loop, it's a DAG.

Example: Course prerequisites form a DAG: CS101 → CS201 → CS301. No course can be its own prerequisite (no cycle).

Break a problem into overlapping subproblems, solve each once, and build up to the final answer. The key question: 'what does the future need to know from the past?' If you can define that, you can write the recurrence.

Example: Climbing stairs: ways(n) = ways(n-1) + ways(n-2). Each step only needs the two before it.

A guarantee that replicas converge to the same value eventually — not instantly. Writes propagate in the background, so for a short window different readers can see different values. You give up read-your-writes immediacy to get availability and partition tolerance, which is the right trade for most consumer apps.

Example: Post a comment, refresh on another device a second later, and it is not there yet — then it appears. The system was eventually consistent, not strongly consistent.

When two different keys produce the same hash value and land in the same bucket. Every hash table has to handle this — usually by chaining (linked list in the bucket) or open addressing (probe to the next empty slot).

Example: If hash('cat') = 7 and hash('dog') = 7, both go to bucket 7. The hash table chains them together.

Safe to retry because doing it twice gives the same final result as doing it once. Setting a value to 5 is idempotent. Incrementing by 1 is not.

Example: PUT requests are idempotent (replace the resource). POST requests are not (create a new one each time).

Something that keeps moving in one direction: nondecreasing or nonincreasing. A monotonic stack keeps that order by popping values that would break it.

Example: A monotonic decreasing stack: [8, 5, 3]. Push 6? Pop 5 and 3 first, then push 6. Now it's [8, 6].

Cutting off branches of your search tree early because you KNOW they can't lead to a valid answer. Without pruning, backtracking checks every possibility. With pruning, it skips entire subtrees. The difference between TLE and AC.

Example: N-Queens: if placing a queen on row 3 column 2 conflicts with row 1, skip ALL arrangements that build on that placement.

A formula that defines each value in terms of previous values. It is the mathematical backbone of dynamic programming. If you can write the recurrence, you can write the code.

Example: Fibonacci: F(n) = F(n-1) + F(n-2). Climbing stairs: same recurrence, different story.

A memory leak where two or more objects keep strong references to each other, so ARC never reaches zero and nothing deallocates. The usual Swift interview trap is a closure capturing `self` while `self` also owns the closure.

Example: A service stores `onUpdate`, the closure captures `self`, and the view model owns the service. That loop keeps all three alive until you break the cycle with `[weak self]`.

A Swift concurrency protocol that marks a value as safe to move across actor or task boundaries. If a type is `Sendable`, the compiler can trust that passing it between concurrent contexts will not smuggle shared mutable state and create a race.

Example: A struct of plain value types often gets `Sendable` for free. A class with mutable properties usually does not, which is why the compiler starts complaining when you pass it into a `Task`.

A dummy node at the head or tail of a linked list that simplifies edge cases. Instead of special-casing 'what if the list is empty?' or 'what if I'm inserting at the head?', the sentinel is always there, so every real node has a predecessor.

Example: LRU Cache: use a dummy head and dummy tail. Every real node sits between them. No null checks needed.

A push notification with no visible alert whose only job is to wake your app in the background so it can fetch fresh data. The OS rate-limits these hard, and a dropped one is normal — so treat silent push as an opportunistic sync trigger, never as a guaranteed delivery channel.

Example: A chat app sends a silent push when a new message lands; the app wakes, pulls the thread, and updates the badge before the user ever opens it. If the OS throttles the push, the next foreground sync still catches up.

A sort that preserves the original order of elements with equal keys. Merge sort is stable. Quick sort is not. This matters when you sort by multiple criteria — sort by name first, then by age, and a stable sort keeps the name order within each age group.

Example: Sort students by grade, then by name. Stable sort preserves alphabetical order within the same grade.

A cache policy that serves the old copy instantly while fetching a fresh one in the background. The user never waits on the network for already-seen data; the next render quietly gets the update. It trades a brief window of staleness for a UI that always feels immediate.

Example: Open a profile screen: the cached avatar and name paint in zero milliseconds, a refresh request fires in the background, and if the data changed the screen reconciles on the next frame.

The round where the interviewer hands you a vague product goal ('design Twitter', 'design a rate limiter') and watches how you decompose it into components, pick trade-offs, and defend your choices. Not about memorizing architectures — it's about whether you can reason about capacity, consistency, latency, and failure without reaching for jargon.

Example: 'Design a URL shortener for 100M daily active users.' Strong answer starts with back-of-envelope math (QPS, storage, read:write ratio), picks a primary key strategy (base62 hash vs counter), discusses the cache layer, and names the SPOFs. Weak answer jumps straight to 'I'd use Redis and Kafka.'

A way to line up tasks so every dependency comes before the thing that depends on it. If course B requires course A, A appears first in the topological order. Only works on directed graphs with no cycles.

Example: Course Schedule on LeetCode: can you take all courses given their prerequisites? That's topological sort.

A tree where each node represents a character, and paths from root to nodes spell out words. Incredible for prefix-based lookups — 'is any word in my dictionary that starts with pre-?' takes O(length) time regardless of dictionary size.

Example: Autocomplete: type 'app' → the trie instantly gives you 'apple', 'application', 'append'.

A data structure that tracks which elements belong to the same group. Two operations: UNION (merge two groups) and FIND (which group does this element belong to?). With path compression and rank, both are nearly O(1).

Example: Number of Connected Components: union every edge, then count how many distinct roots remain.

Exclusive-or — a bitwise operator that returns 1 where two bits differ and 0 where they match. The interview-critical properties: `a ^ a = 0` (a thing cancels itself), `a ^ 0 = a` (zero is identity), and XOR is commutative/associative (order doesn't matter). XOR-ing a whole list in any order collapses every duplicate to 0.

Example: Single Number (LC 136): XOR every element in the array. Duplicates pair off and cancel, leaving only the unique number — O(n) time, O(1) space, no hash map.

Conflict-free Replicated Data Type: a structure designed so independent edits merge into the same result no matter what order they arrive in. No central referee, no last-write-wins data loss — the merge is correct by construction. The price is real complexity and metadata overhead, so you reach for them only when true concurrent editing demands it.

Example: Two people type in the same Figma or Notion document offline; when both reconnect, a CRDT merges both edit streams deterministically instead of one overwriting the other.

Amazon's 16 cultural tenets — 'Customer Obsession', 'Ownership', 'Dive Deep', 'Have Backbone', etc. — that every behavioral interview question maps to. The bar raiser isn't evaluating your story in isolation, they're evaluating which LP the story demonstrates and how clearly.

Example: 'Tell me about a time you disagreed with your manager' is not testing conflict skills — it's testing Have Backbone; Disagree and Commit. Name the LP in your answer's structure and the interviewer's scoring rubric lines up with yours.

The ratio of elements to buckets in a hash table. When the load factor gets too high (~0.75 in Java), the table resizes (doubles its buckets and rehashes everything). Understanding this explains why hash table operations are O(1) AMORTIZED, not always O(1).

Example: HashMap with 12 entries and 16 buckets: load factor = 0.75. Add one more → triggers resize to 32 buckets.

A problem has optimal substructure when the best solution to the whole problem can be built from the best solutions to its subproblems. This is what makes dynamic programming WORK — if the property doesn't hold, DP won't give the right answer.

Example: Shortest path: the shortest path from A to C through B includes the shortest path from A to B. That's optimal substructure.

A weird or worst-shaped input that exposes a bad assumption. Interviewers use pathological cases to see whether your solution only works on happy examples.

Example: A sorted array is a pathological input for naive quicksort that always picks the first element as pivot.

A recursive call that's the LAST thing the function does — nothing happens after it returns. Some languages optimize tail recursion into a loop (no stack growth). Python and Java don't. Still worth knowing because interviewers ask 'can you make this tail-recursive?'

Example: factorial(n, acc=1): return acc if n==0, else factorial(n-1, n*acc). The recursive call IS the return — that's tail position.