Goldman Sachs Interview Question for Developer Program Engineers


Country: United States
Interview Type: Phone Interview




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

int a[] = {1,3,7,5,2,8,6,4,9};
int n = 9;
 
int index = getIndexOfNthLargest(n); // index of smallest data
reverseArray(index);
 
for(int i=n-1,j=1; i>0; i--,j++)
{
    int index = getIndexOfNthLargest(i);
    reverseArray(index);
    reverseArray(index - j);
    reverseArray(index);
}

- algos October 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Why are you making it complicated? Here is a simpler version.

Lets assume we want to find 1st, 2nd.. and nth lagest elements and set them from n-1, n-2 to 0th index of the array.

for(int i=n; i>=1; i--)
{
int index = getIndexOfNthLargest(i);
reverseArray(index); // bring the i-th largest to the beginning
reverseArray(i-1); // set the i-th largest to the (i-1)-th position in the array
}

- AA December 01, 2012 | Flag
Comment hidden because of low score. Click to expand.
3
of 3 vote

for(index=1;index<=n;index++)
{
index_of_nth_largest = getIndexOfNthLaargest(index);
	if(i==0)
	{
		reverseArray(index_of_nth_largest);
		
	}
	else
	{
		reverseArray(index_of_nth_largest-1);
		reverseArray(index_of_nth_largest);
	}

}

- Supratim Sengupta October 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Better than others

- sduwangtong December 16, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

The question explanation seems wrong: In 1:

"1. getIndexOfNthLargest(int n) // returns nth largest number. Like for n=1 the largest element will be returned, for n=2 2nd larget number will be returned."

The function name "getIndexOfNthLargest(int n)" suggests this functions returns the "index" of the nth largest element. However, the question says it returns the nth largest element instead of the index of it.


Assume getIndexOfNthLargest(int n) does return the index of nth largest element, a straightforward case is

for x in 1..N
i=getIndexOfNthLargest(x)
reverseArray(i)
reverseArray(N-x)

- Anonymous October 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Thanks, corrected the question.

- singhSahab October 30, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

{
for(index=1;index<=n;index++)
{
index_of_nth_largest = getIndexOfNthLaargest(index);
if(i==0)
{
reverseArray(index_of_nth_largest);

}
else
{
reverseArray(index_of_nth_largest-1);
reverseArray(index_of_nth_largest);
}
}
}

- supratim sengupta October 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

for(int index = n; index>0; index--)
{
     ind_of_largest = getIndexofNthLaargets(index);
     reverseArray(ind_of_largest);
     reverseArray(index);
}

- Rohit Garg December 06, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

For(i=n-1;i>=0;i--)
{
x=getindexofnthlargest(i);
Swap(a[x],a[0]);
reverseArray(i);
}

- Rahul roy nitkkr December 09, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

see first line of question..

- leave it December 26, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.HashMap;
import java.util.Map;

public class MyArray {
	Map<Integer,Integer> map = null;	
	public MyArray(int[] arr) {		
		map = new HashMap<Integer, Integer>(arr.length);	
		for(int i =0; i < arr.length; i++){
			map.put(i, arr[i]);
		}
	}
	public int getIndexOfNthLargest(int n){
		return map.get(n);		
	}
	public void reverseArray(){
		int size = map.size();
		int mid = size/2;
		for(int i =0; i < mid ; i++){
			int hi = map.get(i);
			int low = map.get(size-1-i);
			map.put(size-1-i, hi);
			map.put(i, low);
		}		
	}
	public static void main(String[] args) {		
		int a[] = {11,10,9,8,7,6,5,4,3};
		MyArray ma = new MyArray(a);
		ma.reverseArray();
		for(int i =0; i <a.length; i++)
			System.out.print(" "+ma.map.get(i));		
	}
}

- Ashis Kumar March 16, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void swap(int &a, int &b) {
int temp = a;
a = b;
b = a;
}

int partition(int [] a, int left, int right)
{
int i=left, j=right;
int v = a[left];
do {
do {
i++;
} while (a[i] <= v)
do {
j--;
} while (a[j] >= v)
if (i < j)
swap(a[i], a[j]);
} while (i<=j)
a[left] = a[j];
a[j] = v;
return j;
}

int findNthLargestValue(int [] a, int left, int right, int n) {
int p = partition(a, left, right);
int delta = n - p;
if (delta == n) { // find
return a[p];
}

if (delta>n) {
return findNthLargestValue(a, p+1, right, n);
} else {
return findNthLargestValue(a, left, p-1, n-delta);
}
}

int findNthLargest(int [] a, int n)
{
findNthLargestValue(a, 0, n-1, n-1);
}

- Anonymous May 15, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int a[] = {12, 25, 5, 19, 27, 3, 8, 6, 4, 15, 13, 22};
int n = 12;
 
int index = getIndexOfNthLargest(n); // index of smallest data
reverseArray(index);
 
for(int i=2 i<=N; i++)
{
    int index = getIndexOfNthLargest(i);
    reverseArray(index -1);
    reverseArray(index);

- Anonymous December 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

for(int i = 1; i< =n; i++){
int temp = getIndexofNthLaargets(i); // get largest in temp
reverseArray(temp); // largest element in 1st position
reverse(n-1-i);largest element in last sorted position
}

- hello world! June 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is an example of pan cake sorting

- Nomad July 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

for(index=1;index<=n;index++)
{
index_of_nth_largest = getIndexOfNthLaargest(index);
	if(i==0)
	{
		reverseArray(index_of_nth_largest);
		
	}
	else
	{
		reverseArray(index_of_nth_largest-1);
		reverseArray(index_of_nth_largest);
	}

}

- supratim.sengupta October 29, 2012 | 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