Goldman Sachs Interview Question
Developer Program EngineersCountry: United States
Interview Type: Phone Interview
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
}
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);
}
}
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)
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));
}
}
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);
}
- algos October 29, 2012