Data Structures & Algorithms - Essential Interview Prep Flashcards

Question 1

What is Time Complexity and how is it expressed?

Accepted Answer

Measures how the runtime of an algorithm scales with the input size $N$. It's expressed using Big O notation, focusing on the upper bound of growth (e.g., $O(1)$, $O(\log N)$, $O(N)$, $O(N \log N)$, $O(N^2)$).

Question 2

What is Space Complexity and common examples?

Accepted Answer

Measures the amount of auxiliary memory an algorithm uses relative to the input size $N$. Examples include $O(1)$ for constant space, $O(N)$ for linear space (e.g., an array of size $N$), and $O(\log N)$ for recursive call stacks in some algorithms.

Question 3

Explain Breadth-First Search (BFS) and its typical use cases.

Accepted Answer

A graph traversal algorithm that explores all nodes at the current depth level before moving to the next. It uses a `queue`. Common uses: shortest path in unweighted graphs, level order tree traversal, finding connected components. Time/Space: $O(V + E)$.

Question 4

Explain Depth-First Search (DFS) and its typical use cases.

Accepted Answer

A graph traversal algorithm that explores as far as possible along each branch before backtracking. It uses a `stack` (or recursion). Common uses: cycle detection, topological sort, pathfinding, connected components. Time/Space: $O(V + E)$.

Question 5

What are the key differences between BFS and DFS?

Accepted Answer

BFS explores level by level, guarantees shortest path in unweighted graphs, uses a `queue`. DFS explores depth-first, good for cycle detection and topological sort, uses a `stack` (or recursion). BFS is generally iterative, DFS can be recursive or iterative.

Question 6

Describe Dijkstra's Algorithm and its time complexity.

Accepted Answer

A greedy algorithm for finding the shortest paths from a single source node to all other nodes in a graph with non-negative edge weights. It uses a `min-priority queue`. Time complexity: $O(E \log V)$ or $O(E + V \log V)$ with a binary heap.

Question 7

What is Topological Sort and when is it used?

Accepted Answer

A linear ordering of vertices in a Directed Acyclic Graph (DAG) such that for every directed edge `u -> v`, `u` comes before `v` in the ordering. Used for task scheduling with dependencies (e.g., build systems, course prerequisites). Time complexity: $O(V + E)$.

Question 8

Explain the Two Pointers algorithmic pattern.

Accepted Answer

Involves using two pointers (indices) that iterate through a data structure (e.g., array, string) from different positions (e.g., start/end, or both from start at different speeds) to solve problems efficiently, often reducing time complexity from $O(N^2)$ to $O(N)$.

Question 9

Give an example problem solvable with the Two Pointers pattern.

Accepted Answer

Finding a pair with a given sum in a sorted array, reversing an array/string in-place, checking for palindromes, removing duplicates from a sorted array.

Question 10

Explain the Sliding Window algorithmic pattern.

Accepted Answer

Used on linear data structures (arrays, strings) to maintain a "window" (a contiguous subsegment) of elements. The window slides over the data, expanding or shrinking, to solve problems like finding maximum/minimum subarray sums, or longest substrings meeting certain criteria.

Question 11

Give an example problem solvable with the Sliding Window pattern.

Accepted Answer

Finding the maximum sum subarray of a fixed size `k`, finding the longest substring with `k` distinct characters, minimum window substring, finding the smallest subarray with sum greater than `X`.

Question 12

What is Dynamic Programming (DP)?

Accepted Answer

An optimization technique for problems exhibiting `overlapping subproblems` and `optimal substructure`. It solves each subproblem only once and stores its result (memoization or tabulation) to avoid redundant computations, typically improving exponential complexity to polynomial.

Question 13

Differentiate between Memoization and Tabulation in DP.

Accepted Answer

`Memoization` (top-down) is a recursive approach where computed subproblem results are stored in a cache (e.g., hash map) as they are encountered. `Tabulation` (bottom-up) is an iterative approach where a table is filled starting from base cases, building up to the final solution.

Question 14

What is a Trie (Prefix Tree) and its primary use cases?

Accepted Answer

A tree-like data structure used to store a dynamic set of strings. Each node represents a character, and paths from the root form prefixes. Useful for efficient prefix-based searches, autocomplete, spell checkers, and dictionary implementations.

Question 15

What is a Heap data structure?

Accepted Answer

A specialized tree-based data structure (often implemented as an array) that satisfies the heap property: in a `min-heap`, parent nodes are less than or equal to their children; in a `max-heap`, parent nodes are greater than or equal. Used to implement `priority queues`.

Question 16

What are common applications of Heaps?

Accepted Answer

Implementing `priority queues`, HeapSort algorithm, finding the $k$-th smallest/largest element in $O(N \log k)$ time, median finding in a data stream.

Question 17

Explain QuickSort, including its average and worst-case complexities.

Accepted Answer

A divide-and-conquer sorting algorithm that picks a pivot element and partitions the array around it. It's an in-place, unstable sort. Average time complexity: $O(N \log N)$. Worst-case: $O(N^2)$ (occurs with poor pivot choices, e.g., already sorted array).

Question 18

Explain MergeSort, including its time and space complexities.

Accepted Answer

A divide-and-conquer sorting algorithm that divides the list into halves, sorts them recursively, and then merges the sorted halves. It's a stable sort. Time complexity: $O(N \log N)$ in all cases. Space complexity: $O(N)$ due to the auxiliary array used for merging.

Question 19

Compare QuickSort and MergeSort.

Accepted Answer

QuickSort is generally faster in practice due to better cache performance and in-place partitioning (avg $O(\log N)$ space), but has $O(N^2)$ worst-case time. MergeSort has guaranteed $O(N \log N)$ time and is stable, but requires $O(N)$ auxiliary space.

Question 20

Why are Balanced Binary Search Trees (e.g., AVL, Red-Black) important?

Accepted Answer

They maintain a balanced height (e.g., $O(\log N)$) during insertions and deletions, preventing worst-case $O(N)$ search/insert/delete times that can occur in unbalanced BSTs. This ensures all operations remain efficient at $O(\log N)$.

Question 21

What are the two primary ways to represent a graph?

Accepted Answer

1. `Adjacency Matrix`: A $V 	imes V$ matrix where `matrix[i][j]` is 1 (or weight) if an edge exists from `i` to `j`, 0 otherwise. Good for dense graphs, $O(V^2)$ space.
2. `Adjacency List`: An array of lists where `list[i]` contains all vertices adjacent to vertex `i`. Good for sparse graphs, $O(V + E)$ space.

Data Structures & Algorithms - Essential Interview Prep

Cards in this deck

Related Flashcard Sets

JLPT N4 - Grammar Patterns & Kanji

German B1 - Intermediate Grammar & Vocabulary

Kubernetes Fundamentals & Orchestration

CFA Level I - Ethical and Professional Standards