## Goldman Sachs Interview Question for Developer Program Engineers

• 3
of 3 votes

Country: India
Interview Type: In-Person

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

``````public static String generate(char[] input) {
String result = "";
ArrayList<Integer> remain = new ArrayList<Integer>();
for(int i = 0; i < input.length; i ++) {
remain.add(input.length - i);
}
for(int i = 0; i < input.length; i ++) {
result = result + " " + remain.get(input[i]);
remain.remove(input[i]);
}
return result;
}``````

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

Just use vector to simply the label:

``````vector<int> generate(const vector<int> &in) {

int s = in.size();
vector<int> out(s+1);
vector<int> inserted;

for(int i = 1; i <= s; i++)
inserted.push_back(i);

int curRemain = s-1;
for(int i = 1; i <= s; i++)
{
int small = curRemain - in[i-1];
out[i]=inserted[small];
inserted.erase(inserted.begin()+small);
curRemain--;
}
out.erase(out.begin());
return out;
}``````

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

The output should be [1,4,7,3,2,6,5] not [1,5,7,3,2,6,4] if I got correctly the problem.
If so, this is my solution in C++:

``````vector<int> generate(const vector<int> &in) {

int s = in.size();
vector<int> out(s);

int free_elements[s];
bool inserted[s];
for(int i = 0; i < s; i++)
free_elements[i] = s - i - 1, inserted[i] = false;

int n_inserted = 0;
int currValue = 1;
int index = 0;
while(n_inserted < s) {
if(!inserted[index] && in[index] == free_elements[index]) {
out[index] = currValue;
currValue++, n_inserted++;
inserted[index] = true;
for(int i = 0; i < index; i++)
free_elements[i]--;
index = 0;
}
else
index++;
}

return out;
}

int main() {
for(auto &v : generate(vector<int>{6,3,0,2,2,0,0}))
cout << v << " ";
return 0;
}``````

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

``````public static String generate(char[] input) {
String result = "";
ArrayList<Integer> remain = new ArrayList<Integer>();
for(int i = 0; i < input.length; i ++) {
remain.add(input.length - i);
}
for(int i = 0; i < input.length; i ++) {
result = result + " " + remain.get(input[i]);
remain.remove(input[i]);
}
return result;
}``````

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

Could you please explain logic?

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

How did you come up with this solution? Please explain your logic.

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

The output should be [1,4,7,3,2,6,5].
Solution in Swift:

``````#!swift
func heightArrayToArray(heightArray: [Int]) -> [Int] {
var array = [Int](repeating: 0, count: heightArray.count)
var indexOrderingReversed: [Int] = []
// Iterating though the height array in reverse, you know the ordering of previous indices.
// Thus you can insert the current index in the correct order as well
for (greaterThanCount, index) in zip(heightArray.reversed(), (0 ..< heightArray.count).reversed()) {
indexOrderingReversed.insert(index, at: greaterThanCount)
}
// Now reverse and inverse the mapping (1-based)
for (index, number) in zip(indexOrderingReversed.reversed(), (1 ... indexOrderingReversed.count)) {
array[index] = number
}
return array
}``````

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

The output should be [1,4,7,3,2,6,5].
Swift solution:

``````func heightArrayToArray(heightArray: [Int]) -> [Int] {
var array = [Int](repeating: 0, count: heightArray.count)
var indexOrderingReversed: [Int] = []
// Iterating though the height array in reverse, you know the ordering of previous indices.
// Thus you can insert the current index in the correct order as well
for (greaterThanCount, index) in zip(heightArray.reversed(), (0 ..< heightArray.count).reversed()) {
indexOrderingReversed.insert(index, at: greaterThanCount)
}
// Now reverse and inverse the mapping (1-based)
for (index, number) in zip(indexOrderingReversed.reversed(), (1 ... indexOrderingReversed.count)) {
array[index] = number
}
return array
}``````

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

DaveRoox is right; the output should be [1,4,7,3,2,6,5] .

In Swift:

``````func heightArrayToArray(heightArray: [Int]) -> [Int] {
var array = [Int](repeating: 0, count: heightArray.count)
var indexOrderingReversed: [Int] = []
// Iterating though the height array in reverse, you know the ordering of previous indices.
// Thus you can insert the current index in the correct order as well
for (greaterThanCount, index) in zip(heightArray.reversed(), (0 ..< heightArray.count).reversed()) {
indexOrderingReversed.insert(index, at: greaterThanCount)
}
// Now reverse and inverse the mapping (1-based)
for (index, number) in zip(indexOrderingReversed.reversed(), (1 ... indexOrderingReversed.count)) {
array[index] = number
}
return array
}``````

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

@ DavidGMJacobson: certainly not B = [1,4,7,3,2,6,5] 'cause B > B, B > B, so it's only greater than 2 elements, it should be greater than 3 elements.
"A[i] value in input array is the number of greater element on right side" - of course of the output array B ...

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

Here is the logic behind the question:
The given input has size 7 so you have to fill each position by picking one element from array [1,2,3,4,5,6,7]. Now the given height array of array is [6,3,0,2,2,0,0]. Here first height is 6 it means that 6 elements must be greater than the picking element. So we every time pick the (A[i]+1)th greatest element from the remaining array of [1,2,3,4,5,6,7].

For 1st position A[i] is 6. So pick 7th greatest element that is 1. Remaining array [2,3,4,5,6,7].
For 2nd position A[i] is 3. So pick 4th greatest element that is 4. remaining array [2,3,5,6,7].
For 3rd position A[i] is 0 so pick 1st greatest element that is 7. remaining array [2,3,5,6].
Similar process will run until we fill the all position.

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

``````/*
You have given height array of array. Generate the original array.

Input: [6,3,0,2,2,0,0]
Output : [1,4,7,3,2,6,5]

A[i] value in input array is the number of greater element on right side.
November 20, 2017
*/

/*
Here is the logic behind the question:
The given input has size 7 so you have to fill each position by picking one element from array [1,2,3,4,5,6,7]. Now the given height array of array is [6,3,0,2,2,0,0]. Here first height is 6 it means that 6 elements must be greater than the picking element. So we every time pick the (A[i]+1)th greatest element from the remaining array of [1,2,3,4,5,6,7].

For 1st position A[i] is 6. So pick 7th greatest element that is 1. Remaining array [2,3,4,5,6,7].
For 2nd position A[i] is 3. So pick 4th greatest element that is 4. remaining array [2,3,5,6,7].
For 3rd position A[i] is 0 so pick 1st greatest element that is 7. remaining array [2,3,5,6].
Similar process will run until we fill the all position.

If you use an array, it's O(n^2) time due to the remove operation that copies n/2 elements worst case average.
If you use a tree, (sorted map, red black tree etc) you can get away with O(n*lg(n)) time.
*/
#include <bits/stdc++.h>
using namespace std;
vector<int> generate(const vector<int> &in) {

int s = in.size();
vector<int> out(s+1);
vector<int> inserted;

for(int i = 1; i <= s; i++)
inserted.push_back(i);

int curRemain = s-1;
for(int i = 1; i <= s; i++)
{
int small = curRemain - in[i-1];
out[i]=inserted[small];
inserted.erase(inserted.begin()+small);
curRemain--;
}
out.erase(out.begin());
return out;
}
int main(){
vector <int> cool={6,3,0,2,2,0,0};
vector<int> str_vec = generate(cool);
for(auto it = str_vec.begin(); it != str_vec.end(); it++) {
cout << *it << " ";
}
return 0;
}``````

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

Here is the logic behind the question:
The given input has size 7 so you have to fill each position by picking one element from array [1,2,3,4,5,6,7]. Now the given height array of array is [6,3,0,2,2,0,0]. Here first height is 6 it means that 6 elements must be greater than the picking element. So we every time pick the (A[i]+1)th greatest element from the remaining array of [1,2,3,4,5,6,7].

For 1st position A[i] is 6. So pick 7th greatest element that is 1. Remaining array [2,3,4,5,6,7].
For 2nd position A[i] is 3. So pick 4th greatest element that is 4. remaining array [2,3,5,6,7].
For 3rd position A[i] is 0 so pick 1st greatest element that is 7. remaining array [2,3,5,6].
Similar process will run until we fill the all position.

If you use an array, it's O(n^2) time due to the remove operation that copies n/2 elements worst case average.
If you use a tree, (sorted map, red black tree etc) you can get away with O(n*lg(n)) time.

``````#include <bits/stdc++.h>
using namespace std;
vector<int> generate(const vector<int> &in) {

int s = in.size();
vector<int> out(s+1);
vector<int> inserted;

for(int i = 1; i <= s; i++)
inserted.push_back(i);

int curRemain = s-1;
for(int i = 1; i <= s; i++)
{
int small = curRemain - in[i-1];
out[i]=inserted[small];
inserted.erase(inserted.begin()+small);
curRemain--;
}
out.erase(out.begin());
return out;
}
int main(){
vector <int> cool={6,3,0,2,2,0,0};
vector<int> str_vec = generate(cool);
for(auto it = str_vec.begin(); it != str_vec.end(); it++) {
cout << *it << " ";
}
return 0;
}``````

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

``````public class HeightArray {

public static void main(String[] args) {
// A is a height array(Rank array),
// e.g. there are 6 elements to the right of A
int[] A = { 6, 3, 0, 2, 2, 0, 0 };

int[] B = getOriginalArray(A);

System.out.println(Arrays.toString(B));
}

private static int[] getOriginalArray(int[] a) {
int[] B = new int[a.length];
int max = B.length;

// setting up rank for the elements
Set<Integer> s = new TreeSet<>(new Comparator<Integer>() {
@Override
public int compare(Integer a, Integer b) {
return b.compareTo(a);
}
});

int t = 1;
while (t <= max) {
s.add(t++);
}
System.out.println("Set => " + s);

for (int i = 0; i < a.length; i++) {
int rank = a[i];
B[i] = findElement(rank, s);
}

return B;
}

// check range and find the fitting element
private static int findElement(int rank, Set<Integer> s) {
int i = 0, e = 0;
for (Integer j : s) {
e = j;
if (i == rank) {
s.remove(j);
break;
}
i++;
}
return e;
}
}``````

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

Here list=[1,2,3,4,5,6,7]
We can see that (arr.length-arr[i]-i)th element in the list is ith element in the list.
that is in the above example (7-6-0)th element ie., list.get(1)th element is arrth element.
Once you find the element remove the element from list for logic to work perfectly.

public int[] Height(int[] arr){
List<Integer> list=new ArrayList<>();
for(int i=1;i<=arr.length;i++){
list.add(i);

}
for(int i=0;i<arr.length;i++){
int k=arr.length - arr[i]-i;
arr[i]=list.get(k-1);

list.remove(k-1);
}
return arr;
}

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

``````public static void main(String[] args) {
int[] arr = { 6, 3, 0, 2, 2, 0, 0 };
int n = arr.length;
int[] elem = new int[n];
for (int i = 0; i < n; i++)
elem[i] = i + 1;
create(arr, elem, n);
for (int i = 0; i < n; i++)
System.out.print(elem[i] + " ");
}

public static void create(int[] arr, int[] elem, int n) {

for (int i = n - 2; i >= 0; i--) {
if (!balance(arr[i], elem, i, n))
create(arr, elem, n);
}
}

public static boolean balance(int k, int[] elem, int st, int n) {
int y = k;
for (int i = st + 1; i < n; i++)
if (elem[st] < elem[i])
k--;

if (k == 0)
return true;
else {
int[] arr = Arrays.copyOfRange(elem, st, n);
int p = kthlargest(arr, y);
for (int i = st + 1; i < n; i++) {
if (p == elem[i]) {
swap(elem, i, st);
break;
}
}
return false;
}
}

public static int kthlargest(int[] arr, int k) {
int max = -1;
int i = 0;
while (k >= 0) {
for (int p = arr.length / 2 - 1; p >= 0; p--)
heapify(arr, p, arr.length);

heapify(arr, 0, arr.length - i);
max = arr;
arr = Integer.MIN_VALUE;
swap(arr, 0, arr.length - i - 1);
i++;
k--;
}
return max;
}

public static void heapify(int[] arr, int i, int n) {
int l = 2 * i + 1;
int r = 2 * i + 2;

int max = i;

if (l < n && arr[l] > arr[max])
max = l;

if (r < n && arr[r] > arr[max])
max = r;

if (max != i) {
swap(arr, i, max);
heapify(arr, max, n);
}
}

public static void swap(int[] arr, int i, int j) {
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}``````

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

Logic is: the number in the input is the rank of the element you need to place. So you need an array with unique elements sorted ascending (e.g. 1..n, or 0..n-1)
you keep picking the k-th rank, where k is given by the input array (n-a[i]). Why, because then you will have n-k elements being larger that you can place on the right.

If you use an array, it's O(n^2) time due to the remove operation that copies n/2 elements worst case average.
If you use a tree, (sorted map, red black tree etc) you can get away with O(n*lg(n)) time.

Add a Comment
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.

Learn More

### 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.

Learn More

### Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

### Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More