## Goldman Sachs Interview Question for Developer Program Engineers

• 0

Comment hidden because of low score. Click to expand.
3
of 3 vote

int i = 0,j=9;
while(i<j){

if(a[i]==0 && a[j]==1){
a[j]=0;
a[i] =1;
i++;
j--;
}else{
if(a[i]==0)
j--;
else
i++;
}
}

Comment hidden because of low score. Click to expand.
0

Your algorithm is right, but it would take O(N) time. It's not possible to do in O(N/2) time. Only if array contains N/2 ones and N/2 zeros.

Comment hidden because of low score. Click to expand.
0

m@}{, that statement is complete nonsense. O(N) and O(N/2) specify the same set of functions.

Comment hidden because of low score. Click to expand.
0

Algorithm only need to swap N/2 of elements in array on average, but it needs to look at all N elements, unless number of 0 and 1s known a priori.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````int i = p = 0, j= q = 9;
int b[10];
while(i < j) {
if(a[i] == 0){
b[q] = 0;
q--;
} else {
b[p] = 1;
p++;
}
if(a[j] == 0){
b[q] = 0;
q--;
} else {
b[p] = 1;
p++;
}
i++;
j--;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

<pre lang="" line="1" title="CodeMonkey5559" class="run-this">public void seregate(int[] arr) {
for (int i = 0, j = arr.length - 1; i < j;) {
if (arr[i] == 1) {
++i;
continue;
}
if (arr[j] == 0) {
--j;
continue;
}
arr[i++] = 1;
arr[j--] = 0;
}
}
</pre>

Comment hidden because of low score. Click to expand.
0
of 0 vote

public void seregate(int[] arr) {
for (int i = 0, j = arr.length - 1; i < j;) {
while (arr[i] == 1) {
++i;
}
while (arr[j] == 0) {
--j;
}
if (i < j) {
arr[i++] = 1;
arr[j--] = 0;
}
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

public int[] ar (String a[]) {
if(a == null)
return null;
if(a.length == 1)
return a;

int sum = 0;
for(int i = 0; i < a.length; i++)
sum =+ a[i]; a[i] = 0;

for(int i = 0; i < sum; i++)
a[i] = 1;

return a;

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

int a[10] = {0,1,1,1,0,1,0,0,1,0};
int y = 0;
int l = 4;
for(int i = 0, int n = 9;i < n;)
{
cout << "Execution " << y++ << endl;
if((a[i] == 0) && (a[n] == 1))
{
l = a[i];
a[i] = a[n];
a[n] = l;
i++;
n--;
// k--;
}
else if((a[i] == 1) && (a[n] == 1))
{
i++;
l = a[i];
a[i] = a[n];
a[n] = l;
i++;

}
else if((a[i] == 0) && (a[n] == 0))
{
n--;
l=a[n];
a[n]=a[i];
a[i]=l;
n--;

}
else
{
n--;
i++;
}

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

Even this code will work:

``````i=0;
j=n-1;

while (i<j){

while (((a[i]==a[j])&&a[i]==0)||(a[i]<a[j]))
i++;

while ((a[i]==a[j])&&(a[i]==1))
j--;

if (i!=j)
{
int temp=a[i];
a[i]=a[j];
a[j]=temp;
i++; j--:
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

int A[10] = {0,0,0,0,0,0,0,0,0,1};
int i = 0;
int j = sizeof(A)/sizeof(int)-1;
while(i < j)
{
if(A[i] == 1)
i++;
if(A[j] == 0)
j--;
if(A[i] == 0 && A[j] == 1)
{
A[i] = 1; A[j] = 0;
i++; j--;
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

void X::sort()
{
int zero=-1,one=-1;

for(int i=0,j=length-1;i<length,j>-1;i++,j--)
{

if(a[i]==0)
{
zero = i;
cout<<endl<<zero;
}
if(a[j]==1)
one = j;
if(zero < one && zero!=-1 && one != -1)
{
cout<<"here";
swap(zero,one);
zero=one=-1;
}

}

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

The idea is to keep a pointer to the beginning(i) and to the end of the array(j).

Run a loop until i < j
Case 1: if i = 1 and j = 0, i++, j--
Case 2: if j = 1 => swap i+1th element and j, i++
Case 3: if j = 0 => j--;
Case 4: if i = 0 => Swap j-1th element and i, j--

Comment hidden because of low score. Click to expand.
0
of 0 vote

int[] input = new int[] { 1,0,0,1,1,0,0,1};
int i = 0, j = input.Length - 1;
while (i <= j)
{
if (input[i] == 1 && input[j] == 0)
{
i++; j--;
}
else if (input[i] == 0 && input[j] == 1)
{
input[i] = 1;
input[j] = 0;
i++; j--;
}
else if (input[i] == 0 && input[j] == 0)
{
j--;
}
else if (input[i] == 1 && input[j] == 1)
{
i++;
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

this is just like the in-place partition in quick sort

Comment hidden because of low score. Click to expand.
0
of 0 vote

//considering no. of 0 and 1s in array are same it will take o(n/2) time

``````int[] a = {0, 1, 1, 0, 0, 0, 0, 1, 1, 1};
int i = 0;
int j = a.length - 1;
int temp = 0;
do {
if (a[i] == 0 && a[j] == 1) {
temp = a[i];
a[i] = a[j];
a[j] = temp;
i++;
j--;
}
if (a[i] == 1) {
i++;
}
if (a[j] == 0) {
j--;
}
} while (i < j);``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

1.Count the no. of 1s and 0s , store it in two variables(x and y).
2. For index 0 to x-1 in the array , put 1s. For index x to x+y-1 put 0s.

Funny question.

Comment hidden because of low score. Click to expand.
0
of 0 vote

it can be simply done by using two pointers.

Comment hidden because of low score. Click to expand.
0
of 0 vote

same as function of finding pivot in quick sort

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Generally speaking it would always take O(1) time for a[10].

Comment hidden because of low score. Click to expand.
0

Really :D

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.