Goldman Sachs Interview Question
Developer Program EngineersCountry: India
Interview Type: In-Person
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;
}
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;
}
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;
}
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
}
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
}
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
}
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.
/*
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;
}
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;
}
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;
}
}
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;
}
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;
}
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.
- zy_vxd November 20, 2017