Algorithms

What does big Theta describe?

A tight bound. The running time grows at that rate from above and from below, so it is sharper than a plain upper bound.

What is space complexity?

How much extra memory the algorithm uses as the input grows. Count the structures you allocate and the call stack.

What is amortized time?

The average cost of one operation over a long run. A single call may be expensive if those calls are rare enough.

What is worst-case time?

The most steps the algorithm takes on any input of that size. Average time can look better and still hide this input.

What does a dynamic array give you?

Indexed access in constant time, and appends that are usually cheap. When the buffer fills, it allocates a larger one and copies.

What is a linked list good at?

Inserting or deleting at a node you already hold, without shifting the rest. Reaching the nth node means walking there.

What is a stack?

A collection that returns the most recently added item first. Function calls and undo history are the usual picture.

What is a queue?

A collection that returns the oldest item first. Breadth-first search uses one to visit nodes in the order they were found.

What is a deque?

A double-ended queue. Items can be added or removed at either end in constant time.

What does a hash table give you?

Expected constant-time lookup, insert, and delete by key, when the hash spreads keys across the slots.

What is a hash collision?

Two keys landing in the same slot. The table keeps both, usually in a short chain or by probing other slots.

What does load factor measure?

How full a hash table is, as items divided by slots. A high load factor means more collisions and slower operations.

What is a binary heap?

A tree, usually stored in an array, where each parent is ordered ahead of its children. The root is the minimum or the maximum.

What is a priority queue?

A collection that returns the highest-priority item next. A binary heap is the usual way to build one.

What is a binary search tree?

Each node is greater than everything in its left subtree and smaller than everything in its right subtree.

Why balance a search tree?

So the height stays logarithmic. A tree that leans to one side turns each lookup into a walk down a list.

What is a trie?

A tree of characters, one step per character, for strings that share prefixes. Lookup follows the letters of the word.

What is a graph?

A set of nodes connected by edges. An edge may have a direction, a weight, or both.

What is an adjacency list?

For each node, the list of nodes it connects to. It stays small when most pairs of nodes have no edge.

What does breadth-first search guarantee?

On an unweighted graph, the first time it reaches a node is along a shortest path, counted in edges.

What does depth-first search do?

It follows one path as far as it can, then backtracks. That is the usual way to explore every path or to notice a cycle.

What is a topological order?

An order of the nodes of a directed graph so every edge points forward. It exists only when the graph has no cycle.

What does Dijkstra's algorithm require?

Non-negative edge weights. It then finds shortest paths from one source. A negative edge makes it the wrong tool.

What is a union-find structure?

It answers whether two items are in the same group, and it merges two groups. With the usual tricks, each call is nearly constant time.

When does binary search apply?

When the space is sorted, or a yes-or-no property flips only once, so each check can throw away half of what remains.

What is the two-pointers pattern?

Two indexes moving across a line or a sorted array, usually to find a pair or a span in one pass.

What is a sliding window?

A contiguous span whose answer you update as the span moves, instead of recomputing the span from scratch each time.

What must a recursive function have?

A base case that stops, and each call must move toward that case. Otherwise the calls never end.

What is backtracking?

Building a candidate one choice at a time, and undoing a choice when it cannot lead to a valid answer.

What is dynamic programming?

Solving a problem by saving the answers to overlapping smaller problems and reusing those answers.

What is memoization?

A top-down cache. The recursive function stores each subproblem's answer the first time it computes it.

What is tabulation?

Filling a table of subproblem answers from smaller ones toward larger ones, with no recursive calls.

When is a greedy choice safe?

When taking the locally best option at each step is guaranteed to be part of some globally best answer.

What is divide and conquer?

Split the input, solve the pieces, and combine them. Merge sort is the standard example.

What is a stable sort?

A sort that keeps the original order of items that compare as equal.

What does merge sort cost?

O(n log n) comparisons, and it needs a second buffer of about n items for the merge. It is a stable sort.

What does quicksort depend on?

The pivot. Average time is O(n log n). A pivot that always lands at the end makes it quadratic.

What does heapsort guarantee?

O(n log n) time even in the worst case, using only a small amount of extra memory. It is not a stable sort.

How do you detect a cycle in a linked list?

Advance one pointer by one step and another by two. If there is a cycle, the faster pointer meets the slower one.

What is a loop invariant?

A fact you can show is true before every iteration and still true after. It is how you argue the loop does what you claim.

What does in-place mean?

The algorithm reuses the input's storage and only a small, fixed amount of extra memory that does not grow with the input.

Why does walking an array beat jumping around?

The CPU loads memory in chunks. Neighboring items are often already in cache. Scattered nodes usually are not.

What is a monotonic stack?

A stack kept in sorted order by dropping entries that can never be the next answer, such as the previous greater element.

How do you merge overlapping intervals?

Sort by start time. Extend the current interval while the next one begins before the current one ends.

What is a prefix-sum array?

Each entry holds the total of everything before that index, so the sum of any span is a subtraction of two entries.

What is a bit mask?

An integer used as a small set, one bit per item. Subsets can be stored and updated with bitwise operations.

What limits recursion on a long chain?

The call stack. A chain of length n can overflow it. An explicit stack, or a loop, uses memory you control.

Why is comparison sorting stuck at n log n?

There are n factorial possible orders, and each comparison has two outcomes, so some inputs need about n log n comparisons.

When is Bellman-Ford the right shortest path?

When an edge weight may be negative. It also reports a negative cycle. Dijkstra does not handle negative edges.