Microsoft Interview Question SDE-2s
Country: India
If you need speed over space, we can create an additional array to keep track each item in the input array and its corresponding count. So the first pass, we calculate the count of each input array item and the second pass we just update the original input array based on the content of additional array we got from the first pass:
class TestFun {
class func sortZeroOneTwo(var input:[Int]) -> [Int] {
var table = [Int](count: 3, repeatedValue: 0)
for var i = 0; i < input.count; i++ {
if table[input[i]] == 0 {
table[input[i]] = 1
} else {
table[input[i]]++
}
}
var index = 0
for var i = 0; i < input.count; i++ {
while index < table.count && table[index] <= 0 {
index++
}
if index >= table.count {
//nothing can be done here
break
}
if table[index] > 0 {
input[i] = index
table[index]--
}
}
return input
}
}
He is a solution. It keeps track of the end of the 0's and the start of the 2's.
public static void sortZeroOneTwoArray(int[] a) {
if (a == null) {
return;
}
int zeroEnd = -1, twoStart = -1;
for (int i = 0; i < a.length; i++) {
if(a[i] < 0 || a[i] > 2) {
System.out.println("Array value out of bounds");
return;
}
else if (a[i] == 2 && twoStart < 0) {
twoStart = i;
} else if (a[i] == 1 && twoStart > -1) {
a[i] = 2;
a[twoStart++] = 1;
} else if (a[i] == 0) {
if (twoStart > -1) {
a[i] = 2;
a[twoStart++] = a[++zeroEnd];
a[zeroEnd] = 0;
} else if (zeroEnd < i - 1) {
a[++zeroEnd] = 0;
a[i] = 1;
} else {
zeroEnd++;
}
}
}
}
this is the dutch national flag problem. you have to be careful to only increment mid if you know it is a one.
public void sortFlag(int[] a){
int start = 0;
int mid = 0;
int end = a.length;
for (int i = 0; i < a.length; i++){
if (mid == 0) {
swap(start, mid);
start++;
}
if (mid == 2) {
swap(mid, end);
end--;
}
if (mid == 1) mid++;
}
}
Here is a solution satisfying your conditions
1. No array length (or size) use
2. Single parse
This is C#, this question seems to expect C++
public void Sort(int[] arr)
{
try
{
int i = 0;
int firstOne = int.MaxValue, firstTwo = int.MaxValue;
while (true)
{
switch (arr[i]) {
case 0:
if (i > firstOne)
{
Swap(arr, i, firstOne);
firstOne++;
}
if (i > firstTwo)
{
Swap(arr, i, firstTwo);
firstTwo++;
}
break;
case 1:
if (i < firstOne)
{
firstOne = i;
}
if (i > firstTwo)
{
Swap(arr, i, firstTwo);
firstTwo++;
}
break;
case 2:
if (i < firstTwo)
{
firstTwo = i;
}
break;
}
i++;
}
}
catch (IndexOutOfRangeException)
{
//Means we have run through the array
}
}
private void Swap(int[] arr, int i, int j)
{
int tmp;
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
Hi IC
Your code does not work if i change the input array.
int[] input = { 2, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1};
output = {1 0 0 0 0 1 1 1 1 2 2}
Use additional array to keep track the count for each input array item and reconstruct the original array with it. Thus, we can accomplish performance O(N).
class TestFun {
class func sortZeroOneTwo(var input:[Int]) -> [Int] {
var table = [Int](count: 3, repeatedValue: 0)
for var i = 0; i < input.count; i++ {
if table[input[i]] == 0 {
table[input[i]] = 1
} else {
table[input[i]]++
}
}
var index = 0
for var i = 0; i < input.count; i++ {
while index < table.count && table[index] <= 0 {
index++
}
if index >= table.count {
//nothing can be done here
break
}
if table[index] > 0 {
input[i] = index
table[index]--
}
}
return input
}
}
Youd require O(3n) => O(n) time complexity.
track end of all the running arrays. Assume that the last 0 is at xth position, last 1 is at yth position, and last 2 is at zth position. s.t. x < y < z; for example {0,0,1,1,2,2,2} , then x = 1, y= 3, z = 6} .
Lets assume there is a additional 0, then we need 3 steps.
arr[x+1] = 0; x++;
arr[y+1] = 1; y++; // we know that arr[x+1] was 1 before we replaced it to 0.
arr[z+1] = 2; z++;
Now, x= 2, y= 4, z= 7. and array = {0,0,1,1,2, 2, 2}
For adding a 1, you'd just have to do 2 operations, ar[y+1] = 1; arr[z+1] = 2, and z++ y++
For 2, you simply do ar[z+1] = 2 and z++.
static int[] FlagSort2(this int[] a)
{
var b = (int[])a.Clone();
int zero = 0;
int one = 0;
int twos = 0;
for (int i = 0; i < b.Length; i++)
{
switch (b[i])
{
case 0: Swap(ref b[zero++], ref b[one++]); break;
case 1: one++; break;
case 2: b[i] = 1; one++; twos++; break;
}
}
for (int i = b.Length - twos; i < b.Length; i++)
{
b[i] = 2;
}
return b;
}
We traverse the array once and calculate number of 0s, 1s and 2s and put it in the hashMap. In the second pass, we fill in the same array starting with zeros, once we are out of zeros, we go to the next key which is 1 so on.
This way we only scan the array once and do it in O(n) where n = number of elements in the array. So T = O(n), S = O(n)
We can just count number of 0's, 1' s & 2's in the array in a single pass and use memset() to first update all 0's at once, then 1's and finally 2's. It saves lot of comparisons, space and time. memset() is supposed to be faster than accessing and updating individual elements. Most of the algorithms presented here are O(n). However, this approach needs only n comparisons.
We can attempt to reduce individual elements inspection in counting 0's, 1's and 2's by inspecting all the values or subset of the values together. However, this depends on the type of values in real application we expect. I am still working on this.
Use below method to do in position replace, and time complex should be O(n).
int left = 0, right = array.Length - 1, i = 0;
while (i < right)
{
if (array[i] == 0)
{
Swap(array, i++, left++);
}
else if (array[i] == 1)
{
i++;
}
else if (array[i] == 2)
{
Swap(array, i++, right--);
}
}
Use the same idea of partition the array in the quick sort. Take the mid value (1 in this case) as the pivotal value. Partition the array with less than the pivotal value and more than the pivotal value. Therefore it is a O(n) solution (with traverse the array only once) and O(1) space solution. Please refer to: cpluspluslearning-petert.blogspot.co.uk/2015/10/sort-array-with-three-distinct-numbers.html
Test
void TestSortArrayWithThreeDistinctNumbers()
{
std::vector<int> arr;
SortArrayWith3DistinctNumbers(arr, 0, 1, 2);
assert(arr.empty() == true);
arr = { 2, 2, 2, 0, 0, 0, 1, 1, 1 };
SortArrayWith3DistinctNumbers(arr, 0 , 1, 2);
assert(arr == std::vector<int>({ 0, 0, 0, 1, 1, 1, 2, 2, 2 }));
arr = { 0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1 };
SortArrayWith3DistinctNumbers(arr, 0, 1, 2);
assert(arr == std::vector<int>({ 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2 }));
}
void swap(int* arr, int i, int j)
{
if (i!=j)
{
int temp =arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
void sort(int * arr, int length)
{
int lo = 0;
int mid = 0;
int hi = 0;
while (hi < length) // If length is not given then use whatever termination condition is allowed by the interviewer
{
switch (arr[hi])
{
case 0: {
swap(arr, lo, hi);
++lo;
break;
}
case 1: {
swap(arr, mid, hi);
++mid;
break;
}
case 2: {
++hi;
break;
}
default :{
std::cout << "Error situation" << std::endl;
break;
}
}
}
}
This can be done in linear time, with no extra space. We do a linear based insertion sort, but do it twice, once for 0, and once for 1. Here's the code
- Ravish chawla October 18, 2015void sort (vector<int> nums) { //call linear insertion on 0 once, moves all 0's to the front int zEnd = move(nums, 0, 0); //call linear insertion on 1, moves all 1s after end of 0s. 2's are automatically sorted. int oEnd = move(nums, zEnd, 1); } //this is the linear insertion sort. it swaps each occurence of val with the moving pointer. int move(vector<int> nums, int start, int val) { int i = start; int j = start; while(true) { try { if(nums.at(j) == val) swap(nums, i++, j); j++; } catch(exception e) { break; } } return i; }