Reviewed by Aditya Kumar · Last reviewed 2026-03-24
**Why Three-Way Partition:** Sort 0s, 1s, 2s in one pass—O(n), O(1). Foundation for 3-way quicksort (Dijkstra's). Used in routing (low/med/high priority), bucketing. **Invariant:** [0..low)=0, [low..mid)=1, [high..n)=2. mid sweeps; swap 0 with low, 2 with high; 1 stays....
This hard-level Python/Coding question appears frequently in data engineering interviews at companies like Microsoft. While less common, it tests deeper understanding that distinguishes strong candidates. Mastering the underlying concepts (partition) will help you answer variations of this question confidently.
This is a senior-level question that tests architectural thinking. Lead with the high-level design, then drill into specifics. Discuss trade-offs explicitly - there is rarely one correct answer. Show awareness of scale, fault tolerance, and operational complexity.
Why Three-Way Partition: Sort 0s, 1s, 2s in one pass—O(n), O(1). Foundation for 3-way quicksort (Dijkstra's). Used in routing (low/med/high priority), bucketing.
Invariant: [0..low)=0, [low..mid)=1, [high..n)=2. mid sweeps; swap 0 with low, 2 with high; 1 stays.
Extensions: K-way partition needs different approach. With duplicates, stability is lost—acceptable for sort. In streaming: classify into 3 buckets without full sort.
def sort_012(arr):
lo, mid, hi = 0, 0, len(arr)-1
while mid <= hi:
if arr[mid] == 0:
arr[lo], arr[mid] = arr[mid], arr[lo]
lo += 1; mid += 1
elif arr[mid] == 1: mid += 1
else:
arr[mid], arr[hi] = arr[hi], arr[mid]
hi -= 1
Red Flag: Two-pass (count then fill). Pro-Move: 'We use same 3-way partition for event priority routing—low/med/high to different queues.'
Some links below are affiliate links. If you buy through them we may earn a small commission at no extra cost to you — it helps keep DataEngPrep free.
According to DataEngPrep.tech, this is one of the most frequently asked Python/Coding interview questions, reported at 1 company. DataEngPrep.tech maintains an editor-reviewed database of 1,863 data engineering interview questions across 7 categories.