Onsite Interview (Phenom)
Summary
During my onsite interview with Phenom, I was presented with a coding challenge to sort an array containing only 0s, 1s, and 2s in-place, aiming for O(n) time and O(1) space complexity.
Full Experience
You are given an integer array nums containing only 0, 1, and 2.
Sort the array in-place so that:
-
All 0s appear first
-
Followed by all 1s
-
Followed by all 2s
You must:
-
Solve it in O(n) time complexity
-
Use O(1) extra space (in-place sorting)
-
Avoid using built-in sort functions
Example
- Input
- nums = [2,0,0,0,1,1,1,2,2,1,0,2]
- Output
- [0,0,0,0,1,1,1,2,2,2,2,2]
Constraints
1 <= nums.length <= 10^5
nums[i] is either 0, 1, or 2
Follow-up Can you solve this problem in a single pass?
Interview Questions (1)
Sort Array of 0s, 1s, and 2s (Dutch National Flag Problem)
You are given an integer array nums containing only 0, 1, and 2.
Sort the array in-place so that:
-
All 0s appear first
-
Followed by all 1s
-
Followed by all 2s
You must:
-
Solve it in O(n) time complexity
-
Use O(1) extra space (in-place sorting)
-
Avoid using built-in sort functions
Example
- Input
- nums = [2,0,0,0,1,1,1,2,2,1,0,2]
- Output
- [0,0,0,0,1,1,1,2,2,2,2,2]
Constraints
1 <= nums.length <= 10^5
nums[i] is either 0, 1, or 2
Follow-up Can you solve this problem in a single pass?