## Goldman Sachs Interview Question

Software Engineers**Country:**India

**Interview Type:**In-Person

package com.program;

public class Sort0s1s2s {

public static void main(String[] args) {

int arr[] = { 0, 1, 1, 0, 1, 2, 1,

2, 0, 0, 0, 1 };

int n = 12;

sort012(arr, n);

for(int i=0;i<n;i++) {

System.out.print(arr[i]+" -");

}

}

private static void sort012(int[] arr, int n) {

int count0s=0;

int count1s=0;

int count2s=0;

for(int i=0;i<n;i++) {

if(arr[i]==0) {

count0s++;

}

if(arr[i]==1) {

count1s++;

}

if(arr[i]==2) {

count2s++;

}

}

for(int i=0;i<count0s;i++) {

arr[i]=0;

}

for(int i=count0s;i<count0s+count1s;i++) {

arr[i]=1;

}

for(int i=count0s+count1s;i<count0s+count1s+count2s;i++) {

arr[i]=2;

}

}

}

I think it is a bit simpler than the "Dutch national flag problem".

It resolves to range count instead of high/mid/low sort.

```
void CountSort(int beg, int end, std::vector<int> v)
{
std::vector<int> counts(end - beg + 1, 0);
for (int i : v)
counts[i - beg]++;
auto start = v.begin();
for (int i = beg; i <= end; i++)
start = std::fill_n(start, counts[i - beg], i);
}
```

public class ArrangeZeroOneTwo {

public static void main(String arv[]) {

int arr[] = {1,0,1,2,0,2,0,2,1,0,2,1,0,1,1,1,1,1,2,0,0,0,0,0,0,0,0,0,1,1,1,1,2,2,0,0,0,0,0,0};

int pointerForZero=0;

int pointerForTwo=arr.length-1;

for(int i=0;i<arr.length && i<pointerForTwo ;i++) {

if(arr[i] == 0) {

arr[i] = arr[pointerForZero];

arr[pointerForZero] = 0;

++pointerForZero;

}

if(arr[i] == 2) {

arr[i] = arr[pointerForTwo];

arr[pointerForTwo] = 2;

--pointerForTwo;

--i;

}

}

for(int i=0;i<arr.length;i++) {

System.out.print(arr[i] +" ");

}

}

}

A solution in q language:

```
f:{ / function to sort the elements of the array
c0::c1::c2::0; / counter variables
{$[0=x;c0+:1;1=x;c1+:1;2=x;c2+:1;::]} each x; / inner function to count occurrence of each element
:raze [[(c0;c1;c2)]{#[x;y]}'til 3]; / returning the occurrence of 0,1,2 based on count
};
```

Test:

a:0 1 1 0 2 1 2; / array initialization

f a / calling the function

Output: 0 0 1 1 1 2 2

Dutch national flag problem

- Sithis April 08, 2019