Data Structures & Algorithms Specialized Algorithms & Interview Prep Flashcards

24 sample cards from the Specialized Algorithms & Interview Prep deck

Sampled from the end of the deck, so these are different cards from the ones shown on the syllabus page.

1. 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.

2. 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.

3. 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.

4. 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.

5. 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.

6. 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.

7. 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)$.

8. 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.

9. 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$.

10. 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.

11. 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.

12. 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.

13. 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.

14. 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.

15. 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.

16. 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.

17. 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)$.

18. 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!).$$

19. 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.

20. 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.

21. 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.

22. 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.

23. 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.

24. 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.

What this deck covers

Specialized Algorithms & Interview Prep flashcards FAQ