Goldman Sachs Interview Question for Developer Program Engineers


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

- zy_vxd November 20, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 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;
}

- DaveRoox November 20, 2017 | Flag Reply
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;
}

- jiazheng2222 November 22, 2017 | Flag Reply
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;
	}

- zy_vxd November 20, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Could you please explain logic?

- Sandeep November 21, 2017 | Flag Reply
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.

- Sandeep November 21, 2017 | Flag Reply
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
}

- Anonymous November 21, 2017 | Flag Reply
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
}

- Anonymous November 21, 2017 | Flag Reply
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
}

- DavidGMJacobson November 22, 2017 | Flag Reply
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[1] > B[2], B[1] > B[3], 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 ...

- Anonymous November 22, 2017 | Flag Reply
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.

- maneeshp626 November 23, 2017 | Flag Reply
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;
}

- harrypotter0 November 24, 2017 | Flag Reply
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;
}

- harrypotter0 November 24, 2017 | Flag Reply
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[0]
		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;
	}
}

- shramdc November 26, 2017 | Flag Reply
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 arr[0]th 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;
}

- Deeksha April 15, 2018 | Flag Reply
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[0];
			arr[0] = 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;
	}

- sudip.innovates November 21, 2017 | Flag Reply
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.

- Chris November 21, 2017 | Flag Reply


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