Data Structures & Algorithms Specialized Algorithms & Interview Prep Syllabus

What does it mean for a problem to be NP-hard?

Every problem in $\mathbf{NP}$ reduces to it in polynomial time; it is at least as hard as every NP problem but need not itself be in $\mathbf{NP}$.

What does it mean for a problem to be NP-complete?

It is both in $\mathbf{NP}$ and NP-hard; it is among the hardest problems in $\mathbf{NP}$, and a polynomial algorithm for any one would put all of $\mathbf{NP}$ in $\mathbf{P}$.

State the central open question relating P and NP and the known containment.

It is unknown whether $\mathbf{P} = \mathbf{NP}$; it is known that $\mathbf{P} \subseteq \mathbf{NP}$, and most researchers conjecture $\mathbf{P} \neq \mathbf{NP}$.

Which problem was the first proven NP-complete, and by which theorem?

Boolean satisfiability (SAT), by the Cook-Levin theorem.

What is a polynomial-time (Karp) reduction from problem $A$ to problem $B$, written $A \leq_{p} B$?

A polynomial-time computable function $f$ mapping instances of $A$ to instances of $B$ such that $x$ is a yes-instance of $A$ iff $f(x)$ is a yes-instance of $B$.

If $A \leq_{p} B$ and $B \in \mathbf{P}$, what can you conclude about $A$?

$A \in \mathbf{P}$: reductions transfer tractability downward and hardness upward.

To prove a new problem $X$ is NP-hard, what must you show via reduction?

Reduce a known NP-hard problem $Y$ to $X$ in polynomial time ($Y \leq_{p} X$), showing $X$ is at least as hard as $Y$.

What is an approximation algorithm and why is it used?

A polynomial-time algorithm for an optimization problem (often NP-hard) that returns a solution provably close to optimal, trading exactness for tractability.

Define the approximation ratio $\rho$ for a minimization problem.

An algorithm is a $\rho$-approximation if for all inputs $\frac{\text{ALG}}{\text{OPT}} \leq \rho$, where $\text{ALG}$ is the algorithm's cost and $\text{OPT}$ is the optimal cost (so $\rho \geq 1$).

What approximation ratio does the classic greedy vertex cover (add both endpoints of an uncovered edge) achieve?

A $2$-approximation: the returned cover is at most twice the size of a minimum vertex cover.

What is a PTAS (Polynomial-Time Approximation Scheme)?

A family of algorithms that, for any fixed $\varepsilon > 0$, produce a $(1 + \varepsilon)$-approximation in time polynomial in $n$ (though possibly exponential in $\frac{1}{\varepsilon}$).

How does an FPTAS differ from a PTAS?

An FPTAS runs in time polynomial in both $n$ and $\frac{1}{\varepsilon}$, a stronger guarantee; e.g., the knapsack problem admits an FPTAS.

Which coding-interview pattern is signaled by a problem asking for a subarray/substring satisfying a condition over contiguous elements?

The sliding window pattern, typically achieving $O(n)$ by expanding and contracting a window instead of $O(n^{2})$ nested loops.

When does the two-pointer pattern apply, and what precondition often enables it?

For pair/triplet-sum or partition problems, usually on a sorted array; two indices move inward or in tandem, giving $O(n)$ scanning after any needed $O(n \log n)$ sort.

What problem structure signals the fast-and-slow pointers (Floyd's) pattern?

Cycle detection in a linked list or sequence; a pointer moving 1 step and another 2 steps meet inside a cycle, using $O(1)$ extra space.

Which pattern efficiently merges or processes $k$ sorted lists/streams, and with what data structure?

The K-way merge pattern using a min-heap of size $k$, giving $O(N \log k)$ time for $N$ total elements.

What data structure underlies the Top-K elements pattern, and why?

A heap (priority queue): a min-heap of size $k$ keeps the $k$ largest elements, since the smallest of the top-$k$ sits at the root for $O(1)$ comparison and $O(\log k)$ replacement.

What is the time complexity of finding the $k$ largest elements in an array of size $n$ using a size-$k$ min-heap?

$O(n \log k)$: each of the $n$ elements may cause a $O(\log k)$ heap operation.

What alternative to heaps finds the $k$-th largest element in expected linear time?

Quickselect (partition-based selection), with expected $O(n)$ time and $O(n^{2})$ worst case; median-of-medians pivot gives guaranteed $O(n)$.

How many subsets does a set of $n$ distinct elements have, and what does this imply for subset enumeration?

$2^{n}$ subsets, so any algorithm that lists all subsets is at least $O(2^{n})$; each element is independently in or out.

Describe the iterative bit-mask method for generating all subsets of $n$ elements.

Loop $mask$ from $0$ to $2^{n} - 1$; include element $i$ in the subset whenever the $i$-th bit of $mask$ is set, i.e., $mask \ \&\ (1 \ll i) \neq 0$.

How many permutations does a set of $n$ distinct elements have?

$n!$ permutations, so exhaustive permutation generation is $O(n \cdot n!)$ including the cost of emitting each length-$n$ arrangement.

What general technique generates subsets, permutations, and combinations, and what is its shape?

Backtracking: build partial solutions incrementally via DFS, and undo (backtrack) a choice after exploring it, pruning invalid branches early.

When generating permutations of a multiset with duplicates, how do you avoid duplicate outputs?

Sort first, then at each recursion level skip a value equal to the previously used sibling (skip $nums[i]$ if $nums[i] = nums[i-1]$ and $nums[i-1]$ was not used), ensuring each distinct permutation appears once.

What is the recommended first step when approaching an unfamiliar coding-interview problem?

Clarify and restate the problem: confirm inputs, outputs, constraints, and edge cases with concrete examples before writing any code.

Why should you state a brute-force solution before optimizing in an interview?

It proves you understand the problem, establishes a correctness baseline and a complexity to beat, and often reveals the structure that motivates a faster approach.

What is the UMPIRE (or similar) framework for structured problem solving?

Understand, Match (to a known pattern), Plan, Implement, Review, and Evaluate (analyze complexity) — a repeatable interview process from clarification to complexity analysis.

How should you communicate a time/space tradeoff, e.g., hashing vs. sorting for two-sum?

State both options explicitly: a hash map gives $O(n)$ time with $O(n)$ extra space, while sort-plus-two-pointers gives $O(n \log n)$ time with $O(1)$ extra space, then justify the choice against the constraints.

What does Big-O, Big-Omega, and Big-Theta each bound?

$O$ is an asymptotic upper bound, $\Omega$ a lower bound, and $\Theta$ a tight bound (both upper and lower): $f = \Theta(g)$ iff $f = O(g)$ and $f = \Omega(g)$.

Order these common complexities from fastest to slowest growth: $O(n!)$, $O(\log n)$, $O(n \log n)$, $O(2^{n})$, $O(n^{2})$, $O(1)$, $O(n)$.

$$O(1) < O(\log n) < O(n) < O(n \log n) < O(n^{2}) < O(2^{n}) < O(n!).$$

What coding best practice reduces bugs at array boundaries and empty inputs?

Explicitly handle edge cases — empty input, single element, all-equal, min/max values, and off-by-one boundaries — and test them before declaring the solution done.

Name two coding best practices for writing clean, interview-ready code.

Use clear, descriptive variable/function names and decompose logic into small helper functions; keep functions single-purpose and avoid deep nesting via early returns.

Why is dry-running your code on a sample input important before saying you are finished?

Tracing execution line-by-line on a concrete example catches logic errors, off-by-one mistakes, and incorrect state updates that the compiler will not flag.

What is a recommended structure for a mock-interview practice plan?

Simulate real conditions: fixed time limit (~30-45 min), think aloud, no IDE autocomplete, then review with feedback on communication, correctness, and complexity, and log mistakes for spaced review.

How should you spread practice over time for durable retention of algorithm patterns?

Use spaced repetition: revisit problems and patterns at increasing intervals rather than cramming, and re-solve missed problems after a delay to confirm the concept, not the memorized answer, was learned.

In a mock interview, what should you do if you get stuck and cannot find the optimal solution?

Verbalize your thought process, propose a working brute-force solution, state its complexity, and describe what optimization you would explore — partial, well-communicated progress beats silent stalling.