Algorithms

Part of the Interview Prep Roadmap. Coverage ratings are explained there.

Work through alongside this section

• NeetCode 150 — its binary search, backtracking, dynamic programming, greedy, and graph sections cover most of the topics below. Worth finishing as a whole rather than cherry-picking.
• CP Algorithms — reference implementations and proofs for the graph and DP algorithms here.

Complexity Analysis

Measuring and comparing the cost of an algorithm — the vocabulary every other topic in this phase depends on.

Coverage: moderate

Resources · Big-O Cheat Sheet — complexities of every common structure and algorithm in one table

Asymptotic Notation

• Big-O, Big-Θ, and Big-Ω
• Best, average, and worst case
• Growth rate comparison

Practice

• Why a print statement is O(1) — WellDev, with answer
• Which sort is least efficient in the worst case — Brain Station 23

Analyzing Code

• Loops and nested loops
• Recursive calls
• Recurrence relations and the Master theorem

Practice

• Complexity of a recursive function — WellDev, with answer
• Work out the complexity of given code — Brain Station 23
• Solve T(n) = 2T(√n) + 1 — Brain Station 23

Trade-offs

• Time vs. space
• Amortized analysis

Practice

• Amortized analysis in dynamic structures — World University
• Five elements searched a million times — SRBD, with answer
• Pick a structure for a given operation mix — Chaldal

Sorting & Searching

How the common sorting algorithms work and their time complexity, then binary search and its less obvious applications.

Coverage: moderate

Resources · VisuAlgo — sorting — watch each algorithm run step by step · NeetCode — Binary Search

Elementary Sorting

• Bubble sort
• Selection sort
• Insertion sort

Practice

• How insertion sort works — WellDev
• Selection sort vs. insertion sort — WellDev

Efficient Sorting

• Merge sort
• Quick sort and pivot selection
• Heap sort
• Worst-case behavior of each

Practice

• Implement merge sort — Rokomari, with answer
• Which sort is best on average — Exabyting, with answer
• Heaps, heap sort and its runtime — Spectrum

Non-Comparison Sorting

• Counting sort
• Radix sort
• Bucket sort
• Lower bound on comparison-based sorting

Practice

• Sorting 1000 mixed-sign numbers — Exabyting, with answer
• Sort an array of 0s, 1s and 2s — Therap, with answer

Sorting Properties

• Stability
• In-place vs. out-of-place
• Choosing a sort for a given constraint

Practice

• Which sort degrades worst in the worst case — Brain Station 23
• Sort only the odd elements in place — WellDev

Searching

• Linear search
• Binary search on a sorted array
• Binary search on an answer space
• Search in rotated arrays

Practice

• Explain binary search — IUBAT
• Square root by binary search — Brain Station 23
• Search a row-sorted 2D matrix — WSD
• Search a nearly sorted array — Therap
• When the search key is always at the front — SRBD, with answer
• Searching 5000 keys of 500 digits each — SRBD, with answer

Recursion & Backtracking

Breaking a problem into itself, and backtracking when a branch doesn't work out.

Coverage: moderate

Resources · NeetCode — Backtracking

Recursion Fundamentals

• Base case and recursive case
• The call stack and stack depth
• Recursion vs. iteration
• Tail recursion

Practice

• Factorial of n — Brain Station 23, with answer
• Nth Fibonacci number — Enosis
• Sum of even Fibonacci terms — Chaldal, with answer
• A basic recursive implementation — WellDev

Recursive Patterns

• Divide and conquer
• Tree and graph recursion
• Subsets and permutations

Practice

• Preorder traversal, recursive and iterative — Shanghai BD
• Build a recursive partitioner — Fringecore, with answer

Backtracking

• State-space exploration
• Pruning invalid branches
• Classic problems: N-Queens, Sudoku, word search
• Complexity of backtracking

Practice

• Generate all permutations — Chaldal, with answer
• Generate all subsets — Chaldal, with answer
• Find every subset of a set — Chaldal, with answer
• Count "good" permutations — Kite Games, with answer

Dynamic Programming

What makes a problem a DP problem — overlapping subproblems and optimal substructure — then memoization vs. tabulation.

Coverage: moderate

Resources · NeetCode — 1-D and 2-D DP · CP Algorithms — DP

DP Fundamentals

• Overlapping subproblems
• Optimal substructure
• Recognizing a DP problem

Practice

• Which statement about DP is false — Brain Station 23
• A 0/1 knapsack variant — AppsCode

Implementation Approaches

• Top-down memoization
• Bottom-up tabulation
• Space optimization

Practice

• Fibonacci using only two variables — WellDev

Classic DP Patterns

• 1D DP: Fibonacci, climbing stairs, house robber
• Knapsack variants
• Subsequence problems: LCS, LIS
• Grid and path-counting problems
• Partition and subset-sum problems

Practice

• Best time to buy and sell stock — Therap, with answer
• Maximum profit from a price series — Therap
• Two eggs and an n-storey building — WellDev, with answer
• Burst balloons for maximum coins — Kite Games
• Minimum cost buying apples in lots — IQVIA

Greedy Algorithms

Making the locally optimal choice at each step, and knowing when that actually yields a globally optimal answer.

Coverage: thin

Resources · NeetCode — Greedy

Greedy Fundamentals

• Greedy-choice property
• Cases where greedy fails
• Greedy vs. dynamic programming

Practice

• Can every student attend every assignment — Chaldal, with answer

Classic Greedy Problems

• Activity selection and interval scheduling
• Fractional knapsack
• Huffman coding
• Coin change

Practice

• Total length covered by overlapping ranges — IQVIA, with answer
• Fit coloured balls into capacity-limited boxes — Priyo
• Build a priority task scheduler — Fringecore, with answer

Graph Algorithms

BFS and DFS as the foundation, then Dijkstra, Bellman-Ford, and MST — which algorithm fits which constraint, and why.

Coverage: rich

Resources · CP Algorithms — graph algorithms — reference implementations and proofs · VisuAlgo — graph traversal

Traversal

• Breadth-first search
• Depth-first search
• Visited tracking and traversal order
• Finding connected components

Practice

• What DFS is, and implementing it — Enosis
• BFS vs. DFS — which is faster, and when — weDevs
• Number of islands — Chaldal, with answer
• Islands in 8 directions, plus the largest — Relisource
• Farmer-owned regions in a village grid — Kite Games, with answer
• Identify patterns in a 0/1 grid — Kite Games

Shortest Path

• BFS for unweighted graphs
• Dijkstra's algorithm
• Bellman-Ford and negative weights
• Floyd-Warshall for all pairs

Practice

• Shortest path A to F using BFS — Brain Station 23
• Fastest algorithm on an unweighted graph — Brain Station 23
• Which claim about Dijkstra is untrue — Brain Station 23
• What holds for Bellman-Ford — Brain Station 23
• Shortest path in a scenario graph — ShellBeeHaken

Minimum Spanning Tree

• Kruskal's algorithm
• Prim's algorithm
• Union-find (disjoint set union)

Practice

• Which algorithm finds an MST — Brain Station 23, with answer
• Find the minimum spanning tree — RoBenDevs
• Connect n cities with m roads — Brain Station 23, with answer

Ordering & Structure

• Topological sort
• Cycle detection in directed and undirected graphs
• Strongly connected components

Practice

• Topological order from letter orderings — Chaldal
• Detect a cycle in a directed graph — SRBD, with answer
• Count reachable vertices — AppifyLab

Bit Manipulation

Basic bitwise operations and shifting, then bitmasking and common XOR tricks.

Coverage: thin

Resources · Bit Twiddling Hacks — the canonical collection

Bitwise Operators

• AND, OR, NOT, XOR
• Left and right shift
• Signed vs. unsigned shifts

Practice

• Encode a sequence as binary by parity — AppifyLab, with answer

Bit Tricks

• Checking, setting, clearing, and toggling a bit
• Counting set bits
• Powers of two
• XOR properties for finding unique elements

Practice

• Minimum bit flips between two strings — IQVIA
• Produce a bit string not in the input — DSI

Bitmasking

• Representing subsets as bitmasks
• Iterating over subsets
• Bitmask DP