How would you sort an array of 0s, 1s, and 2s in linear time?
This is a variation of the Dutch National Flag problem. It tests sorting efficiency and in-place manipulation skills.
Why Interviewers Ask This
Standard sorting algorithms take O(n log n), but this question challenges candidates to achieve O(n). Interviewers want to see if you know the three-pointer technique and can implement it without extra space. It evaluates your attention to detail in boundary conditions and loop invariants.
How to Answer This Question
Use three pointers: low, mid, and high. Initialize low and mid at the start, and high at the end. Iterate while mid is less than or equal to high. If the element at mid is 0, swap with low and increment both. If it is 1, just increment mid. If it is 2, swap with high and decrement high. Ensure you explain why this works and that it sorts in a single pass.
Key Points to Cover
- Three-pointer technique
- In-place swapping
- Single pass O(n) complexity
- Handling distinct values
Sample Answer
To sort this array in O(n) time, I would use the Dutch National Flag algorithm with three pointers. Low points to the end of the 0s section, mid scans the array, and high points to the start of the 2s section. When arr[mid] is 0, swap with arr[low] and move both forward. If arr[mid] is 1, just move mid forward. If arr[mid] is 2, swap with arr[high] and move high backward. This ensures all 0s are before 1s and all 1s are before 2s in a single traversal.
Common Mistakes to Avoid
- Using standard sort libraries
- Incorrect pointer movement logic
- Failing to handle the middle element correctly
Practice This Question with AI
Answer this question orally or via text and get instant AI-powered feedback on your response quality, structure, and delivery.
Related Interview Questions
How do you add two numbers represented by linked lists?
Medium
AmazonWrite Selenium and Java code to automate an Amazon search
Medium
InfosysHow do you implement binary search on a sorted array?
Easy
MicrosoftWhat is the difference between value type and reference type?
Easy
TCSConvert Binary Tree to Doubly Linked List in Place
Hard
MicrosoftDiscuss ACID vs. BASE properties
Easy
Microsoft