## Qualcomm Interview Question for Software Engineer / Developers

• 0

Interview Type: In-Person

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

For each index, calculate what the tallest point in the histogram preceding that index is. This is easy and O(n) because max_before[n] = max (max_before[n-1], histogram[n]). Now, also for each index, calculate a similar max_after array (calculate from the back using max_after[n] = max (histogram[n], max_after[n+1])). Now, for each index n, water_height[n] = min (max_before[n], max_after[n]). At this point, loop over the indices i = 0...n-2 and do:

``````if (water_level[i].floatingPointEquals(water_level[i+1]))
{    area += (water_level[i] - (histogram[i] + histogram[i+1]) / 2);    }
//on a water level transition we have to be careful about where a water level ends
else {
//this all makes sense if you draw it out
double lowerWaterHeight = min (waterLevel[i], waterLevel[i+1]);
double lowerLandHeight = min (histogram[i], histogram[i+1]);
double waterHeightFromBase = lowerWaterHeight - lowerLandHeight;
double fractionOfTile = waterHeightFromBase  / abs(histogram[i+1] - histogram[i]);
area += (fractionOfTile * waterHeightFromBase  / 2);
}``````

Edit: This calculation is for the case when the histogram is represented as a line graph, not a bar graph. In the case of a bar graph, you can use the same technique and the logic will be very similar (the formula will actually be simpler).

The algorithm is linear time overall.

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

The first solution takes O(n) space as well as O(n) time. By doubling the time (the time complexity will still be O(n)), we can also find out the volume.
For the sake of simplicity, let us assume that the area of cross-section of each histogram is 1 square unit. Then, the volume of water = Total height of water above all the towers cubic units. The height of water above any given tower is determined by the following formula:
heightOfWater[i] = max(min(LeftMax[i],RightMax[i]) - height[i], 0).

Now, we can look at it as follows. Move from left to right. Start from the left most maximum (the first tower), and move right. All the towers that have lesser height than that will have some amount of water above it, provided there is another tower of height >= it. Consider two towers this way, i and j, such that i < j, and height[i] < height[j] and for all k < j and k > i, height [k] < height[j]. Then, the height of water above each tower is calculated using the formula:
heightOfWater[k] = height[i] - height[k].
totalHeightOfWater += height[i] - height[k].
Then set i = j and find the next j. If there is no j, then stop.

Now, start moving from the right to the left and do the same, with i > j, and height[i] < height[j] and for all k < i and k > j, height [k] < height[j]. Then, the height of water above each tower is calculated using the formula:
heightOfWater[k] = height[i] - height[k].
totalHeightOfWater += height[i] - height[k].
Then set i = j and find the next j. If there is no j, then stop.

We can calculate the total height of water, while we are calculating individual heights.

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

Awesome explanation! Thx dude :-)

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

No need to double the time. Can be done in one pass.

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

Here is a solution which I believe should be more readable

Credits to Tristan (Tristan's collection of Interview Question) for his approach

``````int FillWater(int* histogram, int length)
{
int waterCollected = 0;
int *maxLeft = new int [length];
int *maxRight = new int [length];

//For each values, calculate the maximum value to its left
maxLeft = 0;
for(int i = 1; i < length; i++)
{
maxLeft[i] = max(histogram[i-1], maxLeft[i-1]);
}

//For each values, calculate the maximum value to its right
maxRight[length-1] = 0;
for(int i = length - 2; i >= 0; i--)
{
maxRight[i] = max(histogram[i+1], maxRight[i+1]);
}

//At each index, water collected will be collected, if it is a dip
//Amount of water collected will be [min(maxLeft[i], maxRight[i]) - value at that index]
for(int i = 0; i < length; i++)
{
if(maxLeft[i] > histogram[i] && maxRight[i] > histogram[i])
{
waterCollected += (min(maxLeft[i], maxRight[i]) - histogram[i]);
}
}
delete[] maxLeft;
delete[] maxRight;
return waterCollected;
}``````

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

The above solution takes constant space, if we don't store the intermediate values of height[k]. However, it requires 2 passes of the array, and hence double the time.

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

Time complexity: O(N)

``````int findTrappedWater(int* H,int size)
{
int i,j,water=0,temp;
for(i=0;i<size;)
{
j=i+1;
temp=0;
while(j<size && H[i]>H[j])
{
temp+=H[j];
j++;
}
if(j!=size) // decreasing length histogram
water+=(j-i-1)*H[i]-temp;
i=j;
}
return water;
}``````

Complete code here: ideone.com/xCsHn

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

@shondik
i think you are missing the case when going from left to right you don't find any H[j] > H[i]. But even in that case we might have water getting collected and the way to do it completely would be to traverse the array once more from right to left using the same logic.

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

@mr, Can you provide one counter example?

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

This is also a neat solution.. the tricky part being the condition

``````if(j!=size) // decreasing length histogram
water+=(j-i-1)*H[i]-temp;``````

which ensures that if the histogram is decresing order (either in its entirity or portion of it) then that section is skipped while calculating the trapped water.

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

3,2,1,2 Breaks this. As:

``````i = 0
H > all other numbers``````

But there is 1 unit of water held between the two columns with 2.

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

On similar lines, this should work

``````/* Set previous and next values for all buildings */
void SetPrevNext()
{
int i, max_height = -1;
prev = -1;
next[n-1] = -1;
/* Set previous values */
for (i=1;i<n;i++)
{
if(h[i-1]>h[i])            /* If height of prvious building is more */
{
prev[i] = i-1;
}
else if(h[i]<h[prev[i-1]]) /*Check previous height */
{
prev[i]=prev[i-1];
}
else if(max_height > -1 && h[i]<h[max_height])  /* Local Maximum height */
{
prev[i] = max_height;
}
else                                            /* heighest tower */
{
prev[i] = -1;
max_height = i;
}
}

/* Set next heights */
max_height = -1;
for (i=n-2;i>=0;i--)
{
if(h[i+1]>h[i])             /* height of next tower is more */
{
next[i] = i+1;
}
else if(h[i]<h[next[i+1]])
{
next[i]= next[i+1];
}
else if(max_height > -1 && h[i]<h[max_height]) /* local maximum tower height */
{
next[i] = max_height;
}
else                                           /* heighes tower */
{
next[i] = -1;
max_height = i;
}
}
}

int FillWater()
{
int i, total_water = 0;
int height, width;
for (i=1;i<n-1;i++)
{
if(prev[i]>0 && next[i]>0)
{
/*height of water based on smaller next or previous tower */
height = (h[prev[i]]<h[next[i]])?(h[prev[i]]-h[i]):(h[next[i]]-h[i]);

/* Width spanning the previos and next towers */
width = (next[i]-prev[i]-1)*W;

//printf("\nHeight : %d, Width : %d for %d",height, width, h[i]);
total_water += (height * width);
}
}
}``````

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

``````/**
* find water captured between towers
* works perfactly and complexity is O(n)
*/
long int getWaterStorage(std::vector<long int> const & towers) {
if(towers.size() < 3) return 0;
int i = 1;
long int water= 0;

while(i<towers.size()) {
//first find last element in ascending order
while(i<towers.size() && towers[i-1]<=towers[i]) ++i;
int s = i-1;
//second find last element in discending order
while(i<towers.size() && towers[i-1]>=towers[i]) ++i;
int m = i -1;
if(s == m) break;
//third find last element in ascending order
while(i<towers.size() && towers[i-1]<=towers[i]) ++i;
int e = i -1;
if(m == e) break;
water += std::min(towers[s], towers[e]) - towers[m];
}

return water;
}
int main() {

std::vector<long int> v;
int n;
std::cin>>n;
for(int i =0;i<n;++i)
{
long int e;
std::cin>>e;
v.push_back(e);
}

std::cout<<getWaterStorage(v)<<std::endl;

return 0;
}

areeb\$ ./a.out
3  << this is size of the array
2 1 3 << these are element separated by space
1  << output

areeb\$ ./a.out
3
1 2 3
0

areeb\$ ./a.out
3
3 2 1
0

areeb\$ ./a.out
3
3 1 2
1``````

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

``````/**
* find water captured between towers
* works perfactly and complexity is O(n)
*/
long int getWaterStorage(std::vector<long int> const & towers) {
if(towers.size() < 3) return 0;
int i = 1;
long int water= 0;

while(i<towers.size()) {
//first find last element in ascending order
while(i<towers.size() && towers[i-1]<=towers[i]) ++i;
int s = i-1;
//second find last element in discending order
while(i<towers.size() && towers[i-1]>=towers[i]) ++i;
int m = i -1;
if(s == m) break;
//third find last element in ascending order
while(i<towers.size() && towers[i-1]<=towers[i]) ++i;
int e = i -1;
if(m == e) break;
water += std::min(towers[s], towers[e]) - towers[m];
}

return water;
}

int main() {

std::vector<long int> v;
int n;
std::cin>>n;
for(int i =0;i<n;++i)
{
long int e;
std::cin>>e;
v.push_back(e);
}

std::cout<<getWaterStorage(v)<<std::endl;

return 0;
}

areeb\$ ./a.out
3   << this is number of elements in the array
2 1 3  << array, all element on one line space sparated
1  << output
areeb\$ ./a.out
3
1 2 3
0
areeb@\$ ./a.out
3
3 2 1
0
areeb\$ ./a.out
3
3 1 2
1``````

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

# O(n) time, O(1) space
def area(heights):
ret = 0
cur_valley_area = 0
max_so_far = 0
index_of_max_so_far = -1

for i, h in enumerate(heights):
if h < max_so_far:
cur_valley_area += max_so_far - h
else:
ret += cur_valley_area
max_so_far = h
index_of_max_so_far = i
cur_valley_area = 0

# add everything that comes after (to the right of) the max height in the array
max_right_so_far = 0
for i in xrange(len(heights) - 1, index_of_max_so_far, -1):
h = heights[i]
max_right_so_far = max(h, max_right_so_far)
ret += max_right_so_far - h

return ret

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

``````# O(n) time, O(1) space
def area(heights):
ret = 0
cur_valley_area = 0
max_so_far = 0
index_of_max_so_far = -1

for i, h in enumerate(heights):
if h < max_so_far:
cur_valley_area += max_so_far - h
else:
ret += cur_valley_area
max_so_far = h
index_of_max_so_far = i
cur_valley_area = 0

# add everything that comes after (to the right of) the max height in the array
max_right_so_far = 0
for i in xrange(len(heights) - 1, index_of_max_so_far, -1):
h = heights[i]
max_right_so_far = max(h, max_right_so_far)
ret += max_right_so_far - h

return ret``````

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

A solution with linear time (2 passes), constant space.
Loop to find the local maxima (aka towers). A local maximum is bigger than the element before and the element after, or it is an edge element (first / last) and bigger than the one after / before respectively. Take into account maximum with more than one column (columns are equal). Store the maxima locations in a pair vector (if single column maximum, both values of the pair are equal).
If you have less than 2 maxima, return 0 - no water kept.
Loop on the maxima locations, two at a time (looking at the valley between). The water kept between two maxima is the difference between the histogram value and the smaller of the two maxima values, floored by 0.

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

A discrete graph can be partitioned into alternating increasing and decreasing runs optionally interspersed with optional runs. Define a valley as a decreasing run followed by an optional number of constant runs followed by an increasing run. The height of the valley is the minimum of its leftmost point (the highest point on the decreasing run) and its rightmost point (the highest point on the increasing run). Its length is the total number of elements in its constituent runs. A valley's basin is its height times its length, which is the amount of water that valley can contain. Draw a picture to see why this makes sense.

Translating this idea into an algorithm is easy. You just traverse the histogram left to right, keeping track of decreasing, constant and increasing runs as you go. If you set it up correctly, you won't need to handle leftmost and rightmost "half-valleys" as special cases; they will just be valleys where the height is zero because one of the two end points has height zero.

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

Sorry, my description of calculating the basin area left something out. You also need to calculate the sum of the heights of each of the points in the valley. You then subtract that from the product of the length and min height I already described.

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

No need to overcomplicate with increasing and decreasing runs. Simply consider the list of elements which are greater than all elements to its left. Then define anything in between a consecutive pair of such elements as a valley. The water in such a valley is just sum (height of left end of valley - height of bar). Now just handle all the things to the right of the greatest height specially.

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.