Goldman Sachs Interview Question for Software Engineers

• 3

Country: India
Interview Type: In-Person

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

Dutch national flag problem

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

Use counting sort.

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

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;
}

}

}

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

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);
}``````

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

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] +" ");
}
}
}

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

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

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

k solution:

``f:{c0::c1::c2::0;{\$[0=x;c0+:1;1=x;c1+:1;2=x;c2+:1;::]}'x;,/(c0;c1;c2){#[x;y]}'!3}``

Test:
> f 0 1 1 0 2 1 2 /- output 0 0 1 1 1 2 2
> f 0 1 2 0 1 2 0 1 2 /- output - 0 0 0 1 1 1 2 2 2

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

``````int[] ar = {1,1,0,0,1,1,0,0,1,1,2,2,2,2,1,1,1,1,0,0,0};
int[] c = new int[3];

for(int i=0; i<ar.length; i++){
if(ar[i] == 0) c[0]++;
else if(ar[i] == 1) c[1]++;
else c[2]++;
}

for(int i=0; i<c.length; i++){
while(c[i]-- > 0){
System.out.print(i + " ");
}
}``````

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

``````int[] ar = {1,1,0,0,1,1,0,0,1,1,2,2,2,2,1,1,1,1,0,0,0};
int[] c = new int[3];

for(int i=0; i<ar.length; i++){
if(ar[i] == 0) c[0]++;
else if(ar[i] == 1) c[1]++;
else c[2]++;
}

for(int i=0; i<c.length; i++){
while(c[i]-- > 0){
System.out.print(i + " ");
}
}``````

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

Logic: COunt the number of 1, 2 and 3 in the array, and then iterate again to write them in order as per the counts. will take two traversal though.

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

Lets make it little complex , what if only one iteration is allowed

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

from collections import Counter
input_list = [0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1]
val = Counter(input_list)
for i in val.keys():
j=1
while j <= val[i]:
print(i)
j += 1

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.