C++ Data Structures, Algorithms & Technical
Interview Study Guide
Practical Study Guide
1. Complexity Analysis
Time complexity describes how running time grows as input size n increases. Common classes include
O(1), O(log n), O(n), O(n log n), O(n²), and exponential complexity. Space complexity measures additional
memory usage.
A good interview answer does not merely name a Big-O value. Explain what operation dominates the
algorithm, whether the complexity is worst-case or amortized, and whether extra memory is required. For
example, binary search is O(log n) because each comparison removes roughly half of the remaining
search space.
2. Arrays, Strings and Two Pointers
Arrays provide O(1) random access but insertion and deletion in the middle are generally O(n). Strings can
be treated similarly when discussing indexed access. Two-pointer techniques are especially effective for
sorted arrays, subarray problems, palindrome checks, and partitioning.
Typical patterns include a left/right pointer pair, a slow/fast pair, and a sliding window. Before coding,
identify what invariant the pointers maintain. For example, in a palindrome test, compare the leftmost and
rightmost characters and move inward until the pointers meet.
3. Linked Lists
A singly linked list stores a value and a pointer to the next node. Insertion at a known node can be O(1),
while searching for a position is O(n). A doubly linked list adds a previous pointer, allowing convenient
backward traversal but requiring additional memory.
Important interview problems include reversing a list, detecting a cycle with Floyd's tortoise-and-hare
algorithm, finding the middle node, merging two sorted lists, and removing the nth node from the end. The
key skill is manipulating pointers without losing access to the remainder of the list.
4. Stacks and Queues
A stack follows LIFO ordering and is useful for parentheses validation, expression parsing, depth-first
search, and undo operations. A queue follows FIFO ordering and is fundamental to breadth-first search
and scheduling.
In C++, std::stack and std::queue provide standard interfaces. For a monotonic stack, maintain elements in
increasing or decreasing order so that each element is pushed and popped at most once, often producing
O(n) solutions for next-greater-element and histogram problems.
5. Hash Tables
Hash tables provide average O(1) insertion, lookup, and deletion. In C++, std::unordered_map and
std::unordered_set are common choices. They are excellent when the problem asks whether something
has appeared before, how frequently values occur, or whether a complementary value exists.
A classic example is Two Sum: scan the array once and store previously seen values in a hash map. For
each value x, check whether target-x is already present. This reduces the typical O(n²) brute-force
approach to expected O(n) time.
6. Trees and Binary Search Trees
A binary tree has at most two children per node. Depth-first traversals are preorder, inorder, and postorder.
Breadth-first traversal uses a queue. In a binary search tree, keys in the left subtree are smaller and keys
in the right subtree are larger under the usual invariant.
Important concepts include tree height, balanced trees, lowest common ancestor, level-order traversal, and
validating a BST. A common mistake is validating only each node against its immediate children; correct
validation must preserve the allowable range inherited from all ancestors.
7. Heaps and Priority Queues
A heap supports efficient access to the minimum or maximum element. A binary heap can be represented
compactly in an array. C++ provides std::priority_queue, which is a max-heap by default; using std::greater
can create a min-heap.
Heaps are useful for top-k problems, scheduling, merging sorted sequences, Dijkstra's algorithm, and
maintaining a running median. Insertion and deletion of the extreme element are O(log n), while accessing
it is O(1).
8. Graph Algorithms
Represent graphs using adjacency lists when the graph is sparse. BFS is appropriate for unweighted
shortest paths and level-based exploration. DFS is useful for connectivity, cycle detection, components,
and backtracking.
For weighted graphs with non-negative edge weights, Dijkstra's algorithm is a standard choice. For all-
pairs shortest paths, Floyd-Warshall runs in O(V³). A minimum spanning tree can be found using Kruskal's
algorithm with a disjoint-set union structure or Prim's algorithm with a priority queue.
9. Dynamic Programming
Dynamic programming applies when a problem contains overlapping subproblems and optimal
substructure. Start by defining the state precisely. Then determine the transition, base cases, computation
order, and answer extraction.
For example, Fibonacci can be expressed as dp[i] = dp[i-1] + dp[i-2]. The naive recursive version is
exponential, while memoization or bottom-up computation is O(n). More advanced patterns include 0/1
knapsack, longest common subsequence, coin change, grid DP, interval DP, and bitmask DP.
10. C++ Interview Essentials
Know references versus pointers, stack versus heap allocation, const correctness, pass-by-value versus
pass-by-reference, constructors and destructors, RAII, inheritance, virtual functions, smart pointers,
templates, STL containers, iterators, and lambda expressions.
For modern C++, prefer RAII and standard library abstractions over manual memory management where
appropriate. Understand unique_ptr, shared_ptr, and weak_ptr conceptually. Be prepared to explain why
virtual destructors matter when deleting derived objects through base-class pointers.
11. Problem-Solving Workflow
A strong coding-interview workflow is: clarify the input and output, state constraints, propose a brute-force
baseline, identify the bottleneck, derive an optimized approach, explain correctness, analyze complexity,
and then code.
Do not begin typing immediately. Interviewers often evaluate reasoning more heavily than syntax. After
coding, test normal cases, boundary cases, empty input, duplicate values, very large input, and cases that
trigger the worst-case behavior.
12. Final Revision Checklist
Before an interview, be able to implement from memory: binary search, merge sort, quicksort conceptually,
linked-list reversal, cycle detection, BFS, DFS, Dijkstra, union-find, heap operations, sliding window, two
pointers, prefix sums, backtracking, memoization, 0/1 knapsack, LCS, and common string/hash-map
patterns.
Also practice explaining your solution aloud. A technically correct algorithm can still perform poorly in an
interview if its assumptions, invariants, or complexity are unclear.
Practice Problems
Find the first and last occurrence of a target in a sorted array.
Reverse a linked list iteratively and recursively.
Determine whether a linked list contains a cycle.
Return the top K most frequent elements.
Validate whether a binary tree satisfies the BST invariant.
Find the shortest path in an unweighted graph.
Implement Dijkstra's algorithm using a priority queue.
Solve 0/1 knapsack using both memoization and tabulation.
Find the longest common subsequence of two strings.
Design a sliding-window solution for the longest substring without repeating characters.