## Amazon Interview Question for SDE1s

• 2

Country: India
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
10
of 10 vote

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

In 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.

Looks 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]

Comment hidden because of low score. Click to expand.
2

Simple Respect!!! Awesome man !!!! kudos

Comment hidden because of low score. Click to expand.
0

Comment hidden because of low score. Click to expand.
0

How does this work for: 1 6 2 4 7 1 8? from the algo, it'll not be able to calculate rain between 6 and 7?

Comment hidden because of low score. Click to expand.
1
of 1 vote

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);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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;``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#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

Comment hidden because of low score. Click to expand.
0

{1, 6, 2, 4, 5, 1, 5} case it is failing

Comment hidden because of low score. Click to expand.
0
of 0 vote

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 towersUsedInBucket=0;
int stbucketHeight=0;
int currentTower=0;
int total_storage= 0;
int prevBucketHeight = -1;

while(1){

if(currentTower == num_of_towers){
printf("\nTotal Storage: %d",total_storage);
break;
}

if(bucketReady == 1 && towers[currentTower] >=  stbucketHeight){
towersUsedInBucket = 0;
}

if( towers[currentTower] < prevBucketHeight ){
stbucketHeight = prevBucketHeight;
}
}

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;

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#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);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#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);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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);
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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++;

}
}

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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++;

}
}

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.

### 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.