Master Core Algorithms: Sorting, Graph Traversal, Greedy & Complexity Basics

Quick Sort

Quick sort is an in‑place divide‑and‑conquer sorting algorithm that selects a pivot, partitions the array into elements less than and greater than the pivot, and recursively sorts the partitions. It is not stable.

Time complexity

Best: O(n log n)

Average: O(n log n)

Worst: O(n²) – occurs when the pivot produces highly unbalanced partitions

Merge Sort

Merge sort recursively splits an array into two halves, sorts each half, and then merges the sorted halves. It is stable.

Time complexity

Best: O(n log n)

Average: O(n log n)

Worst: O(n log n)

Bucket Sort

Bucket sort distributes elements into a fixed number of buckets; each bucket is sorted independently (often with another sorting algorithm) and the buckets are concatenated. It is most efficient when the input is uniformly distributed over a known range.

Time complexity

Best: Ω(n + k) – where k is the number of buckets

Average: Θ(n + k)

Worst: O(n²) – when all elements fall into a single bucket

Radix Sort

Radix sort processes the digits of each element (from least‑significant to most‑significant) and distributes elements into buckets for each digit position, merging the buckets after each pass. It does not sort within buckets.

Time complexity

Best: Ω(n k)

Average: Θ(n k)

Worst: O(n k) – where k is the number of digit positions

Depth‑First Search (DFS)

DFS explores a graph by moving as far as possible along each branch before backtracking, using a stack (explicit or recursive).

Time complexity: O(|V| + |E|)

Breadth‑First Search (BFS)

BFS visits vertices level by level, exploring all neighbors of a vertex before moving to the next depth, typically using a queue.

Time complexity: O(|V| + |E|)

Topological Sort

Topological sorting produces a linear ordering of a directed acyclic graph (DAG) such that for every directed edge u → v, vertex u appears before v.

Time complexity: O(|V| + |E|)

Dijkstra's Algorithm

Dijkstra computes the shortest paths from a single source to all other vertices in a directed graph with non‑negative edge weights.

Time complexity: O(|V|²) with a simple array implementation; O(|E| log |V|) when using a binary heap.

Bellman‑Ford Algorithm

Bellman‑Ford also finds single‑source shortest paths and can handle negative‑weight edges (but not negative cycles).

Time complexity

Best: O(|E|) – when no relaxation occurs after the first pass

Worst: O(|V|·|E|)

Floyd‑Warshall Algorithm

Floyd‑Warshall computes shortest paths between every pair of vertices in a weighted graph (including negative weights, provided there is no negative cycle).

Time complexity: O(|V|³) for all cases.

Minimum Spanning Tree (MST)

An MST connects all vertices of an undirected weighted graph with the minimum possible total edge weight. The classic greedy approaches are Prim's and Kruskal's algorithms.

Time complexity (Prim with adjacency matrix): O(|V|²).

Kruskal's Algorithm

Kruskal builds an MST by sorting all edges by weight and adding them one by one, skipping edges that would create a cycle (detected with a union‑find data structure). It works even if the graph is not initially connected.

Time complexity: O(|E| log |V|).

Greedy Algorithms

Greedy algorithms make the locally optimal choice at each step with the hope of reaching a global optimum. They are applicable when the problem exhibits:

Optimal substructure

Greedy‑choice property (a locally optimal choice can be extended to a globally optimal solution)

Example – Coin Change Problem

Given unlimited coins of denominations {1, 5, 10, 25} and a target amount V, the greedy strategy repeatedly selects the largest coin value not exceeding the remaining amount.

For V = 41 the steps are:

Pick 25 ¢ → remaining 16 (1 coin)

Pick 10 ¢ → remaining 6 (2 coins)

Pick 5 ¢ → remaining 1 (3 coins)

Pick 1 ¢ → remaining 0 (4 coins total)

Bit Manipulation Operations

Test k‑th bit: s & (1 << k) Set k‑th bit: s |= (1 << k) Clear k‑th bit: s &= ~(1 << k) Toggle k‑th bit: s ^= (1 << k) Multiply by 2ⁿ: s << n Divide by 2ⁿ: s >> n Intersection of bitsets: s & t Union of bitsets: s | t Difference: s & ~t Extract lowest set bit: s & (-s) Extract lowest zero bit: ~s & (s + 1) Swap two integers without a temporary variable:

x ^= y; y ^= x; x ^= y;

Runtime‑Analysis Notations

Big O (O) – upper bound describing the worst‑case growth rate.

Little o (o) – strict upper bound that the algorithm’s growth approaches but never reaches.

Big Ω (Ω) – lower bound describing the best‑case growth.

Little ω (ω) – strict lower bound that the algorithm’s growth exceeds.

Theta (Θ) – tight bound; the algorithm’s growth is both O and Ω of the same function.

Reference implementation and additional interview questions are available in the GitHub repository:

https://github.com/kdn251/interviews