Goldman Sachs Interview Question
Software EngineersCountry: United States
c++, implementation, O(n)
int countOfMeltDown(vector<int>& arr) {
vector<int> mins;
int i, k, count;
mins.assign(arr.size(), 0);
count = 0;
for (i = 0, k = 1; i < arr.size(); i++, k++) {
mins[i] = min(arr[i], k);
if (arr[i] <= 0) k = 0;
}
for (i = arr.size() - 1, k = 1; i >= 0; i--, k++) {
count = max(count, min(mins[i], min(arr[i], k)));
if (arr[i] <= 0) k = 0;
}
return count;
}
public int meltHistogram1(int[] a){
int len = a.length;
int count = 0;
boolean flag = true;
while(flag){
flag = false;
int prev = a[0];
for(int j = 1; j < len-1; ++j){
int k = a[j];
if(k == 0)
k = 0;
else if(k == prev && k == a[j+1])
k = k - 1;
else if(k < prev && k < a[j+1])
k = k - 1;
else{
if(k > prev)
k = prev;
if(k > a[j + 1])
k = a[j + 1];
}
prev = a[j];
a[j] = k;
}
a[0] = 0;
a[len-1] = 0;
count++;
for(int i = 0; i < len; ++i){
flag = flag || (a[i] != 0);
}
}
return count;
}
public int meltHistogram1(int[] a){
int len = a.length;
int count = 0;
boolean flag = true;
while(flag){
flag = false;
int prev = a[0];
for(int j = 1; j < len-1; ++j){
int k = a[j];
if(k == 0)
k = 0;
else if(k == prev && k == a[j+1])
k = k - 1;
else if(k < prev && k < a[j+1])
k = k - 1;
else{
if(k > prev)
k = prev;
if(k > a[j + 1])
k = a[j + 1];
}
prev = a[j];
a[j] = k;
}
a[0] = 0;
a[len-1] = 0;
count++;
for(int i = 0; i < len; ++i){
flag = flag || (a[i] != 0);
}
}
return count;
}
public int meltHistogram(int[] a){
int len = a.length;
int count = 0;
boolean flag = true;
while(flag){
flag = false;
int prev = a[0];
for(int j = 1; j < len-1; ++j){
int k = a[j];
if(k == 0)
k = 0;
else if(k == prev && k == a[j+1])
k = k - 1;
else if(k < prev && k < a[j+1])
k = k - 1;
else{
if(k > prev)
k = prev;
if(k > a[j + 1])
k = a[j + 1];
}
prev = a[j];
a[j] = k;
}
a[0] = 0;
a[len-1] = 0;
count++;
for(int i = 0; i < len; ++i){
flag = flag || (a[i] != 0);
}
}
return count;
}
package goldmansachs;
import java.util.*;
import java.math.*;
public class histogramMelt {
public static void main(String args[]){
//int arr[] = {5,4,3,6,0,1};
int arr[] = {0,1,1,1,1,0};
int count =histogramMelt(arr);
System.out.println("result =" +count);
}
public static boolean checkZero(int arr[]){
int flag =0;
for(int i=0;i<arr.length;i++){
if(arr[i]==0){
flag=1;
}
else{
flag=0;
break;
}
System.out.print(arr[i] +" ");
}
if(flag==0) return false;
else return true;
}
public static int histogramMelt(int arr[]){
boolean b ;
int count=0;
int l = arr.length;
int val[] = new int[l];
do{
for(int i =0 ; i<l;i++){
System.out.println(i+" "+arr[i]);
if(i==0 || i== l-1){ //corner case first and last elements of the array
val[i]=0;
System.out.println(i+" "+val[i]);
}
else{
if((arr[i]>arr[i+1])||(arr[i]>arr[i-1])){ // other values are replaced by min(left,right) neighbours
val[i] = Math.min(arr[i+1],arr[i-1]);
System.out.println(i+" "+val[i]);
}
else{
val[i] = arr[i]-1; // every column has the top block exposed, so every column gets deducted by 1
if(val[i]<0) val[i]=0; // avoid negatives
System.out.println(i+" "+val[i]);
}
}
}
b =checkZero(val);
arr =val;
count ++; // number of times the histogram was melted
} while(b==false);
return count;
}
}
Can you clarify - couldn't understand the question.
- yny.all March 09, 2016