Bubble Sort — Interview Preparation¶

Junior Questions¶

Middle Questions¶

Senior Questions¶

Professional Questions¶

Coding Challenge (3 Languages)¶

Challenge 1: Implement Bubble Sort with Statistics¶

Write a Bubble Sort that returns (sorted_array, num_comparisons, num_swaps). Must implement early-exit optimization. Must handle empty array and single element.

Go¶

package main

import "fmt"

type SortResult struct {
    Sorted      []int
    Comparisons int
    Swaps       int
}

func BubbleSortWithStats(arr []int) SortResult {
    result := SortResult{Sorted: append([]int(nil), arr...)}
    n := len(result.Sorted)
    for i := 0; i < n-1; i++ {
        swapped := false
        for j := 0; j < n-1-i; j++ {
            result.Comparisons++
            if result.Sorted[j] > result.Sorted[j+1] {
                result.Sorted[j], result.Sorted[j+1] = result.Sorted[j+1], result.Sorted[j]
                result.Swaps++
                swapped = true
            }
        }
        if !swapped {
            break
        }
    }
    return result
}

func main() {
    res := BubbleSortWithStats([]int{5, 1, 4, 2, 8})
    fmt.Printf("%+v\n", res)
    // Expected: Sorted=[1 2 4 5 8], Comparisons=10, Swaps=4
}

Java¶

import java.util.Arrays;

public class BubbleSortStats {
    public static class Result {
        public int[] sorted;
        public int comparisons;
        public int swaps;
        public String toString() {
            return String.format("sorted=%s, comparisons=%d, swaps=%d",
                                 Arrays.toString(sorted), comparisons, swaps);
        }
    }

    public static Result sort(int[] arr) {
        Result r = new Result();
        r.sorted = arr.clone();
        int n = r.sorted.length;
        for (int i = 0; i < n - 1; i++) {
            boolean swapped = false;
            for (int j = 0; j < n - 1 - i; j++) {
                r.comparisons++;
                if (r.sorted[j] > r.sorted[j + 1]) {
                    int t = r.sorted[j];
                    r.sorted[j] = r.sorted[j + 1];
                    r.sorted[j + 1] = t;
                    r.swaps++;
                    swapped = true;
                }
            }
            if (!swapped) break;
        }
        return r;
    }

    public static void main(String[] args) {
        System.out.println(sort(new int[]{5, 1, 4, 2, 8}));
    }
}

Python¶

from dataclasses import dataclass, field
from typing import List

@dataclass
class SortResult:
    sorted: List[int] = field(default_factory=list)
    comparisons: int = 0
    swaps: int = 0

def bubble_sort_with_stats(arr):
    r = SortResult(sorted=list(arr))
    n = len(r.sorted)
    for i in range(n - 1):
        swapped = False
        for j in range(n - 1 - i):
            r.comparisons += 1
            if r.sorted[j] > r.sorted[j + 1]:
                r.sorted[j], r.sorted[j + 1] = r.sorted[j + 1], r.sorted[j]
                r.swaps += 1
                swapped = True
        if not swapped:
            break
    return r

if __name__ == "__main__":
    print(bubble_sort_with_stats([5, 1, 4, 2, 8]))

Challenge 2: Count Inversions in O(n²)¶

Given an array, return the number of inversions (pairs i < j with A[i] > A[j]). Use the Bubble Sort connection: number of swaps = number of inversions.

Go¶

package main

import "fmt"

func CountInversions(arr []int) int {
    a := append([]int(nil), arr...)
    n := len(a)
    inv := 0
    for i := 0; i < n-1; i++ {
        for j := 0; j < n-1-i; j++ {
            if a[j] > a[j+1] {
                a[j], a[j+1] = a[j+1], a[j]
                inv++
            }
        }
    }
    return inv
}

func main() {
    fmt.Println(CountInversions([]int{5, 4, 3, 2, 1})) // 10
    fmt.Println(CountInversions([]int{1, 2, 3, 4, 5})) // 0
}

Java¶

public class CountInversions {
    public static int count(int[] arr) {
        int[] a = arr.clone();
        int n = a.length;
        int inv = 0;
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - 1 - i; j++) {
                if (a[j] > a[j + 1]) {
                    int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t;
                    inv++;
                }
            }
        }
        return inv;
    }

    public static void main(String[] args) {
        System.out.println(count(new int[]{5,4,3,2,1})); // 10
    }
}

Python¶

def count_inversions(arr):
    a = list(arr)
    n = len(a)
    inv = 0
    for i in range(n - 1):
        for j in range(n - 1 - i):
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
                inv += 1
    return inv

print(count_inversions([5, 4, 3, 2, 1]))  # 10

Follow-up: Achieve O(n log n) using Merge Sort — see 02-merge-sort/.

Challenge 3: Cocktail Shaker Sort¶

Implement bidirectional Bubble Sort (Cocktail Shaker).

Python¶

def cocktail_sort(arr):
    n = len(arr)
    start, end = 0, n - 1
    while start < end:
        new_end = start
        for j in range(start, end):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                new_end = j
        end = new_end
        if start >= end: break
        new_start = end
        for j in range(end, start, -1):
            if arr[j - 1] > arr[j]:
                arr[j - 1], arr[j] = arr[j], arr[j - 1]
                new_start = j
        start = new_start
    return arr

print(cocktail_sort([5, 1, 4, 2, 8]))  # [1, 2, 4, 5, 8]

(Go and Java implementations identical to middle.md.)

Challenge 4 (Trick Question): "Sort Without Sorting"¶

Given an array, determine if it is sorted in ascending order — without using any sort.

def is_sorted(arr):
    return all(arr[i] <= arr[i + 1] for i in range(len(arr) - 1))

Why this matters in interviews: Candidates who reach for Bubble Sort here lose points. The right answer is a single linear scan — no sort needed. This question tests whether you "default to a sort" or "default to the simplest answer."

Common Interview Pitfalls¶

Behavioral / System Design¶

"You're reviewing a junior engineer's PR. They've implemented Bubble Sort to sort customer orders by date. Production currently has ~1k orders per day. What feedback do you give?"

Strong answer focuses on: 1. Now: at 1k items, O(n²) = 10⁶ ops ≈ 10 ms. Tolerable, but borderline. 2. Next year: at 10k items, O(n²) = 10⁸ ops ≈ 1 s. Customer-visible latency. 3. The fix: replace with sort.Slice / Collections.sort / sorted — same code complexity, O(n log n). 4. Beyond: add a perf regression test that fails if sort takes >100 ms on n=10k. Set up an SLO. 5. Mentorship angle: Don't just say "use builtin"; explain why, link to docs, and pair on the fix.

"Why does Python's sorted use TimSort instead of Bubble Sort?"

Strong answer: - TimSort is O(n log n) worst case (vs. Bubble's O(n²)). - TimSort is adaptive — exploits "runs" of already-sorted data, achieving O(n) on partially-sorted inputs (real-world data is rarely random). - TimSort is stable — important for Python's dict-based sorting by key. - TimSort is well-tested on real workloads (originally written for Python's list.sort by Tim Peters in 2002).

One-Liner Summary¶

Bubble Sort: Walk the array, swap adjacent pairs out of order, repeat. O(n²) average. Stable, in-place, adaptive (with early exit). Teaching-only — production uses O(n log n) sorts (TimSort, Quicksort, Pdqsort).