Amazon Interview Question SDE1s
Country: India
Interview Type: In-Person
The key concept of the question is water is filled over a tower only if there is a tower of greater height on the left AS WELL AS on right.
This can be solved in O(n) or 3*O(n)
For each tower calculate the max height of tower on its left and right. Then min( max_on_left, max_on_right ) - tower(height) is the water filled over that tower. Sum the water on top of each tower. Remember if on either side there is no tower with height greater than the height of current tower in consideration then water cant filled over that tower.
Time Compexity 3O(n), Space Complexity 3n
#include<stdio.h>
#define n 5 // n is the number of towers
int min(int a, int b){
return a<=b ? a : b;
}
void main(){
int th[n]={1,5,3,7,2}; // th: tower height
int mol[n],mor[n]; // mol: max on left, mor: max on right
int max=0;
int i = 0;
for(i=0; i<n; i++){
if( th[i] >= max){
max = th[i];
mol[i] = 0;
}
else{
mol[i] = max;
}
}
max = 0;
for(i=n-1; i>=0; i--){
if( th[i] >= max){
max = th[i];
mor[i] = 0;
}
else{
mor[i] = max;
}
}
int sumwater = 0;
for( i=0; i<n; i++){
if(mol[i]!=0 && mor[i]!=0){
sumwater+= min(mol[i],mor[i]) - th[i];
}
}
printf("Water accumalation is %d", sumwater);
}
int n=SIZE(a);
int diff=INT_MAX;
int maxleft=INT_MIN;
int I,J,i;
int *max=new int[n];
memset(max,0,sizeof(int)*n);
max[n-1]=a[n-1];
for(i=n-2;i>=0;i--)
max[i]=maxval(max[i+1],a[i]);
for(i=0;i<n;i++)
{
if(a[i]>maxleft)
maxleft=a[i];
if(max[i]-maxleft<diff && max[i]-maxleft>0)
{
diff=max[i]-maxleft;
I=max[i];
J=maxleft;
}
}
printf("\n%d\t%d\t%d\n",I,J,diff);
delete [] max;
Hi Here is a simpler solution. O(n) time with O(1) space.
public int Solution(int[] A) {
if(A.length <=2)
return 0;
int start=0, end=A.length-1, left=A[0], right=A[A.length-1], result=0;
while(start<end-1)
{
if(left<=right) {
start++;
if(A[start] >= left)
left=A[start];
else
result+=left-A[start];
}
else
{
end--;
if(A[end] >= right)
right=A[end];
else
result+=right-A[end];
}
}
return result;
}
#include<bits/stdc++.h>
using namespace std;
int main()
{
int arr[] = {1, 6, 2, 4, 7, 1, 8};//{1,2,5,1,2,3,4,5};
int n = sizeof(arr)/sizeof(arr[0]);
int max1=arr[0], max2=arr[0], diff=0, ans=0;
for(int i=1; i<n; i++)
{
if(max1 > arr[i])
{
diff += max1-arr[i];
}
else if(arr[i] >= max1)
{
max2 = max1;
max1 = arr[i];
ans += diff;
diff = 0;
}
}
printf("%d\n", ans);
return 0;
}
Can anyone test my code correctness.
Time: O(n), space: O(1).
THANKS
Guys whey everybody is using 2 or more loop..its can be done in one loop. The key is , you can potentially store water when moving from High to low tower, which can form a bucket like shape. This high tower will become your starting edge of bucket. you can store water until you encounter a tower greater or equal to height of your starting tower.
Like this your can find all the buckets , until the last tower.
void calculate_storage(int towers[], int num_of_towers)
{
int bucketReady=0;
int towersUsedInBucket=0;
int stbucketHeight=0;
int currentTower=0;
int total_storage= 0;
int prevBucketHeight = -1;
while(1){
if(currentTower == num_of_towers){
total_storage = adjust_leaked_water(total_storage,stbucketHeight,towers[currentTower],towersUsedInBucket);
printf("\nTotal Storage: %d",total_storage);
break;
}
if(bucketReady == 1 && towers[currentTower] >= stbucketHeight){
bucketReady = 0;
towersUsedInBucket = 0;
}
if(bucketReady == 0 ){
if( towers[currentTower] < prevBucketHeight ){
bucketReady = 1;
stbucketHeight = prevBucketHeight;
}
}
if(bucketReady == 1){
total_storage = total_storage + (stbucketHeight - towers[currentTower]);
towersUsedInBucket++;
}
prevBucketHeight = towers[currentTower];
currentTower++;
}
}
int adjust_leaked_water(int total_storage,int st_bucket_height, int end_bucket_height,int numTowers)
{
int leakedWater = (st_bucket_height - end_bucket_height) * numTowers;
if(leakedWater > 0 )
total_storage = total_storage - leakedWater;
return total_storage;
}
public static int getWater(int[] heights){
if(heights == null){
return 0;
}
int max = -1;
int n = heights.length;
int[] left = new int[n];
for(int i = 0; i< n;i++) {
if(heights[i] > max) {
max =heights[i];
}
left[i] = max;
}
max= -1;
int[] right = new int[n];
for(int i =n-1; i>=0; i--) {
if(heights[i] >max) {
max = heights[i];
}
right[i] =max;
}
int ans = 0;
for(int i = 0; i < n; i++) {
if(heights[i] == left[i] || heights[i] == right[i]) {
continue;
}
else {
ans = ans + Math.min(left[i],right[i]) - heights[i];
}
}
return ans;
}
#include <stdio.h>
#include <stdlib.h>
int waterfilled(int arr[], int right[], int n) {
int i = 0, cum =0, min, left = arr[0];
printf("n: %d\n", n);
for (i = 1; i < n-1; ++i) {
if (arr[i] < left && arr[i] < right[i])
{
min = left < right[i] ? left : right[i];
cum += (min - arr[i]);
}
else
{
if (left < arr[i])
left = arr[i];
}
}
return cum;
}
int main(){
//int arr[] = {1,5,3,7,2,4};
int arr[] = {1,6,2,4,5,1,5};
int n = sizeof(arr)/sizeof(arr[0]);
int *right = calloc(sizeof(int), n);;
int i;
right[n-1] = arr[n-1];
for (i = n-2; i >= 0 ; --i) {
if (arr[i] < arr[i+1])
right[i] = arr[i+ 1];
else
right[i] = arr[i];
}
int res = waterfilled(arr, right, n);
printf("res: %d\n", res);
}
#include <stdio.h>
#include <stdlib.h>
int waterfilled(int arr[], int right[], int n) {
int i = 0, cum =0, min, left = arr[0];
printf("n: %d\n", n);
for (i = 1; i < n-1; ++i) {
if (arr[i] < left && arr[i] < right[i])
{
min = left < right[i] ? left : right[i];
cum += (min - arr[i]);
}
else
{
if (left < arr[i])
left = arr[i];
}
}
return cum;
}
int main(){
//int arr[] = {1,5,3,7,2,4};
int arr[] = {1,6,2,4,5,1,5};
int n = sizeof(arr)/sizeof(arr[0]);
int *right = calloc(sizeof(int), n);;
int i;
right[n-1] = arr[n-1];
for (i = n-2; i >= 0 ; --i) {
if (arr[i] < arr[i+1])
right[i] = arr[i+ 1];
else
right[i] = arr[i];
}
int res = waterfilled(arr, right, n);
printf("res: %d\n", res);
}
int waterfilled(int arr[], int right[], int n) {
int i = 0, cum =0, min, left = arr[0];
printf("n: %d\n", n);
for (i = 1; i < n-1; ++i) {
if (arr[i] < left && arr[i] < right[i])
{
min = left < right[i] ? left : right[i];
cum += (min - arr[i]);
}
else
{
if (left < arr[i])
left = arr[i];
}
}
return cum;
}
int main(){
//int arr[] = {1,5,3,7,2,4};
int arr[] = {1,6,2,4,5,1,5};
int n = sizeof(arr)/sizeof(arr[0]);
int *right = calloc(sizeof(int), n);;
int i;
right[n-1] = arr[n-1];
for (i = n-2; i >= 0 ; --i) {
if (arr[i] < arr[i+1])
right[i] = arr[i+ 1];
else
right[i] = arr[i];
}
int res = waterfilled(arr, right, n);
printf("res: %d\n", res);
}
int findwater(int a[ ])
{
i=0;
total=0;
while(i<len(a))
{
if(a[i]>a[i+1])
{ j=i+1;
while(a[j]<a[i]&&j<len(a))
{
j++;
}
if(j==len(a))
{ max=i+1
for(p=i+2;p<len(a);p++)
if(a[p]>a[max])
max=p;
}
else
max=i;
if(max==i+1)
break;
cur=i+1;
while(a[cur]<=a[max])
{
total=total+(a[max]-a[cur]);
cur++
}
i=cur;
}
else
i++;
}
return total;
}
added i++ before break. hopefully should work.
int findwater(int a[ ])
{
i=0;
total=0;
while(i<len(a))
{
if(a[i]>a[i+1])
{
j=i+1;
while(a[j]<a[i]&&j<len(a))
{
j++;
}
if(j==len(a))
{
max=i+1
for(p=i+2;p<len(a);p++)
if(a[p]>a[max])
max=p;
}
else
max=i;
if(max==i+1)
{ i++;
break;
}
cur=i+1;
while(a[cur]<=a[max])
{
total=total+(a[max]-a[cur]);
cur++;
}
i=cur;
}
else
i++;
}
return total;
}
Ohh this is an interesting one. Where do you guys dig these questions out?
Let tower[i] be your initial tower array.
Define the height of the tallest tower to the right of position i be right[i].
{Essentially the largest integer to the right of position i}
So build right[i] by scanning right to left O(n) time O(n) space.
We need left[i] also, similarly, but we can store this in O(1) by not keeping previous values as we scan from left to right. That is, continuously update a "left" type variable as you sweep left to right as you update the totalrain variable on the spot as you sweep left to right...
Here is my idea. Have a totalrain variable accumulate while you sweep from left to right the rain above each tower.
1) Sweep right to left, get right[i] filled up. 2) Sweep left to right, and for each i: a) totalrain += max( min( left , right[i] ) - tower[i], 0 ) <==** key calculation. Accumulate rain above tower i. b) update "left" variable if tower[i] > left , i.e., current tower is larger than all others to left 3) return totalrainIn above, take care in one of several ways (sentinel in left /right, or starting and stopping the linear sweep in 2) inside the limits of the tower[i], to make sure that rain[0]=rain[N-1] = 0 . Just pointing out a possible bug.
- S O U N D W A V E October 07, 2013Looks like 2 linear passes, plus 1 linear array needed.
Time ~2n, space ~n
Key calculation explanation:
=============================
The rain above tower i is:
0 rain UNLESS <=== this explain the outter max( , 0 )
- The largest tower to the left and the largest tower to the right are both greater than tower[i]
- in which case, the rain above tower[i] is the difference in height between the {smaller of the two towers listed just above} and tower[i]