Bucket Sort — Interview Preparation¶

Junior Questions¶

Middle Questions¶

Senior Questions¶

Professional Questions¶

Coding Challenge (3 Languages)¶

Challenge: Sort Floats in [0, 1) Using Bucket Sort¶

Implement Bucket Sort assuming uniformly distributed input. Use n buckets and Insertion Sort as the inner sort. Return a new sorted array. Handle the boundary x = 1.0 correctly. Must pass all test cases including empty array, single element, all equal, and reverse-sorted input.

Go¶

package main

import "fmt"

func BucketSort(arr []float64) []float64 {
    n := len(arr)
    if n <= 1 {
        return arr
    }
    buckets := make([][]float64, n)
    for _, x := range arr {
        idx := int(float64(n) * x)
        if idx >= n {
            idx = n - 1
        }
        buckets[idx] = append(buckets[idx], x)
    }
    for i := range buckets {
        insertionSort(buckets[i])
    }
    out := make([]float64, 0, n)
    for _, b := range buckets {
        out = append(out, b...)
    }
    return out
}

func insertionSort(a []float64) {
    for i := 1; i < len(a); i++ {
        x := a[i]
        j := i - 1
        for j >= 0 && a[j] > x {
            a[j+1] = a[j]
            j--
        }
        a[j+1] = x
    }
}

func main() {
    in := []float64{0.42, 0.32, 0.23, 0.52, 0.25, 0.47, 0.51}
    fmt.Println(BucketSort(in)) // [0.23 0.25 0.32 0.42 0.47 0.51 0.52]
}

Java¶

import java.util.*;

public class BucketSortChallenge {
    public static double[] bucketSort(double[] arr) {
        int n = arr.length;
        if (n <= 1) return arr;
        List<List<Double>> buckets = new ArrayList<>(n);
        for (int i = 0; i < n; i++) buckets.add(new ArrayList<>());
        for (double x : arr) {
            int idx = (int)(n * x);
            if (idx >= n) idx = n - 1;
            buckets.get(idx).add(x);
        }
        for (List<Double> b : buckets) insertionSort(b);
        double[] out = new double[n];
        int pos = 0;
        for (List<Double> b : buckets) for (double v : b) out[pos++] = v;
        return out;
    }

    private static void insertionSort(List<Double> a) {
        for (int i = 1; i < a.size(); i++) {
            double x = a.get(i);
            int j = i - 1;
            while (j >= 0 && a.get(j) > x) {
                a.set(j + 1, a.get(j));
                j--;
            }
            a.set(j + 1, x);
        }
    }

    public static void main(String[] args) {
        double[] in = {0.42, 0.32, 0.23, 0.52, 0.25, 0.47, 0.51};
        System.out.println(Arrays.toString(bucketSort(in)));
    }
}

Python¶

def bucket_sort(arr):
    n = len(arr)
    if n <= 1:
        return arr
    buckets = [[] for _ in range(n)]
    for x in arr:
        idx = int(n * x)
        if idx >= n:
            idx = n - 1
        buckets[idx].append(x)
    for b in buckets:
        for i in range(1, len(b)):
            key = b[i]
            j = i - 1
            while j >= 0 and b[j] > key:
                b[j + 1] = b[j]
                j -= 1
            b[j + 1] = key
    out = []
    for b in buckets:
        out.extend(b)
    return out

if __name__ == "__main__":
    print(bucket_sort([0.42, 0.32, 0.23, 0.52, 0.25, 0.47, 0.51]))

Test Cases¶

Input                                            Expected
[]                                               []
[0.5]                                            [0.5]
[0.3, 0.3, 0.3]                                  [0.3, 0.3, 0.3]
[0.9, 0.8, 0.7, 0.6, 0.5]                        [0.5, 0.6, 0.7, 0.8, 0.9]
[0.42, 0.32, 0.23, 0.52, 0.25, 0.47, 0.51]       [0.23, 0.25, 0.32, 0.42, 0.47, 0.51, 0.52]
[0.0, 0.99999, 1.0 - 1e-9]                        sorted ascending; index clamps for x near 1.0

Evaluation Rubric¶

Follow-Up Questions the Interviewer May Ask¶

1. "Now sort integers in [lo, hi] with the same approach." — adapt the mapping function: idx = (x - lo) * k / (hi - lo + 1).
2. "What if the input is skewed?" — pivot to sample-based boundaries (see middle.md Pattern 1).
3. "How would you parallelize this on 8 cores?" — assign each bucket to a worker; show goroutine / ExecutorService / ThreadPool code.
4. "Prove the expected O(n) bound." — show the Binomial calculation and E[n_0²] = 2 - 1/n.
5. "What if buckets are linked lists instead of arrays?" — insert in sorted order during scatter, eliminating a separate inner sort pass.
6. "Compare to Counting Sort and Radix Sort." — explain the three-way taxonomy: Counting (one value per bucket), Bucket (range per bucket), Radix (iterated bucketing).
7. "What metric would you alert on in production?" — max_bucket_size / avg_bucket_size ratio; alert if > 5×.
8. "Describe TeraSort." — sample → boundaries → scatter (Map) → per-bucket sort (Reduce) → concatenate.

Bonus Challenge: Find the Maximum Gap in Sorted Order¶

Problem: Given an unsorted array of integers, find the largest difference between consecutive elements after sorting, without actually sorting in O(n log n). Achieve O(n) using Bucket Sort.

Key insight: if you have n elements in range [min, max] and you create n - 1 buckets each of width (max - min) / (n - 1), the Pigeonhole Principle says at least one bucket is empty. Therefore the maximum gap must span across two adjacent non-empty buckets — and you only need to track each bucket's min and max.

Go¶

package main

import (
    "fmt"
    "math"
)

func MaximumGap(nums []int) int {
    n := len(nums)
    if n < 2 {
        return 0
    }
    mn, mx := nums[0], nums[0]
    for _, x := range nums {
        if x < mn { mn = x }
        if x > mx { mx = x }
    }
    if mn == mx {
        return 0
    }
    bucketCount := n - 1
    bucketSize := float64(mx-mn) / float64(bucketCount)
    type bucket struct {
        used    bool
        min, max int
    }
    buckets := make([]bucket, bucketCount+1)
    for _, x := range nums {
        idx := int(float64(x-mn) / bucketSize)
        if idx > bucketCount {
            idx = bucketCount
        }
        if !buckets[idx].used {
            buckets[idx] = bucket{true, x, x}
        } else {
            if x < buckets[idx].min { buckets[idx].min = x }
            if x > buckets[idx].max { buckets[idx].max = x }
        }
    }
    maxGap := 0
    prevMax := math.MinInt
    for _, b := range buckets {
        if !b.used { continue }
        if prevMax != math.MinInt && b.min-prevMax > maxGap {
            maxGap = b.min - prevMax
        }
        prevMax = b.max
    }
    return maxGap
}

func main() {
    fmt.Println(MaximumGap([]int{3, 6, 9, 1})) // 3
}

Java¶

public class MaximumGap {
    public static int maximumGap(int[] nums) {
        int n = nums.length;
        if (n < 2) return 0;
        int mn = nums[0], mx = nums[0];
        for (int x : nums) {
            if (x < mn) mn = x;
            if (x > mx) mx = x;
        }
        if (mn == mx) return 0;
        int bucketCount = n - 1;
        double bucketSize = (double)(mx - mn) / bucketCount;
        int[] bMin = new int[bucketCount + 1];
        int[] bMax = new int[bucketCount + 1];
        boolean[] used = new boolean[bucketCount + 1];
        for (int x : nums) {
            int idx = (int)((x - mn) / bucketSize);
            if (idx > bucketCount) idx = bucketCount;
            if (!used[idx]) {
                used[idx] = true;
                bMin[idx] = bMax[idx] = x;
            } else {
                bMin[idx] = Math.min(bMin[idx], x);
                bMax[idx] = Math.max(bMax[idx], x);
            }
        }
        int maxGap = 0, prevMax = Integer.MIN_VALUE;
        for (int i = 0; i <= bucketCount; i++) {
            if (!used[i]) continue;
            if (prevMax != Integer.MIN_VALUE) {
                maxGap = Math.max(maxGap, bMin[i] - prevMax);
            }
            prevMax = bMax[i];
        }
        return maxGap;
    }

    public static void main(String[] args) {
        System.out.println(maximumGap(new int[]{3, 6, 9, 1}));
    }
}

Python¶

def maximum_gap(nums):
    n = len(nums)
    if n < 2:
        return 0
    mn, mx = min(nums), max(nums)
    if mn == mx:
        return 0
    bucket_count = n - 1
    bucket_size = (mx - mn) / bucket_count
    buckets = [None] * (bucket_count + 1)
    for x in nums:
        idx = int((x - mn) / bucket_size)
        if idx > bucket_count:
            idx = bucket_count
        if buckets[idx] is None:
            buckets[idx] = [x, x]
        else:
            buckets[idx][0] = min(buckets[idx][0], x)
            buckets[idx][1] = max(buckets[idx][1], x)
    max_gap = 0
    prev_max = None
    for b in buckets:
        if b is None:
            continue
        if prev_max is not None:
            max_gap = max(max_gap, b[0] - prev_max)
        prev_max = b[1]
    return max_gap

if __name__ == "__main__":
    print(maximum_gap([3, 6, 9, 1]))  # 3

Why this is a classic Bucket Sort interview problem: - The Pigeonhole Principle is what allows you to skip the inner sort entirely. - Each bucket only needs (min, max) — O(1) state instead of a full list. - Single pass to populate buckets + single pass to find the gap → strict O(n) time, O(n) space. - Beats the obvious O(n log n) sort-then-scan approach.

This problem (LeetCode 164 — "Maximum Gap") is the most common production-flavored Bucket Sort interview question because it demonstrates an understanding of when distribution sort beats comparison sort.