Interview Notes - Page 2

Radix Sort Implementation

Radix sort explained: sort integers digit by digit using a stable counting sort per digit. O(d(n + k)) time, in Python, Java and C++.

Data Structures

Counting Sort Implementation

Counting sort explained: tally occurrences of each value, then rebuild the array. O(n + k) time for small integer ranges, in Python, Java and C++.

Data Structures

Heap Sort Implementation

Heap sort explained: build a max-heap, then repeatedly move the max to the end. O(n log n) worst case, in-place, with Python, Java and C++ code.

Data Structures

Quick Sort Implementation

Quick sort explained: partition around a pivot and recurse. O(n log n) average, in-place, with the Lomuto partition in Python, Java and C++.

Data Structures

Merge Sort Implementation

Merge sort explained: divide the array in half, sort each half, then merge. Guaranteed O(n log n), stable, with Python, Java and C++ code.

Data Structures

Insertion Sort Implementation

Insertion sort explained: build a sorted prefix by inserting each element into place. O(n^2) worst but O(n) on nearly sorted data; stable, in Python...

Data Structures

Selection Sort Implementation

Selection sort explained: repeatedly pick the smallest remaining element and place it next. O(n^2) time with the fewest swaps, in Python, Java and C++...

Data Structures

Bubble Sort Implementation

Bubble sort explained simply: repeatedly swap adjacent out-of-order items, with an early-exit optimisation. O(n^2) time, stable, in Python, Java and C...

Data Structures

Interview Concept: Binary Search on Answer Pattern Explained

The "binary search on the answer" pattern explained: when the answer space has a monotone yes/no predicate, binary-search the answer itself. With a re...

Data Structures