Code challenge

Good morning! Here's your coding interview problem for today.

This problem was asked by Facebook.

You are given an array of non-negative integers that represents a two-dimensional elevation map where each element is unit-width wall and the integer is the height. Suppose it will rain and all spots between two walls get filled up.

Compute how many units of water remain trapped on the map in O(N) time and O(1) space.

For example, given the input [2, 1, 2], we can hold 1 unit of water in the middle.

Given the input [3, 0, 1, 3, 0, 5], we can hold 3 units in the first index, 2 in the second, and 3 in the fourth index (we cannot hold 5 since it would run off to the left), so we can trap 8 units of water.

As always, I'll come back later and post my solution.

Attached: sneaking-skeleton-looping-animation-on-chroma-key-background_hfe3msabg_thumbnail-full01.png (1920x1080, 307K)

this again

Since I don't get to ask the interviewer more questions about the problem and it's required to be O(1), here's my solution:

const a = [2, 1, 2];

const b = [3, 0, 1, 3, 0, 5];

const waterWall = function(arr){

let s = 0;

for(let i = 1; i < arr.length-1; i++){
s += arr[0]-arr[i];
}

return s;

}

waterWall(a);
waterWall(b);

1) reduce left and right sides
1a) go from left to right and find first decreasing neighbors, remember the larger (left) one
1b) same from right to left
1c) if those 2 are same, nothing gets filled and algorithm quits, else just forget anything outer from these 2
this found largest bounded sub-array

now wall is right boundary if there is none larger on right from it (and isn't the left-most boundary, which we know)
2) remember right-most wall, mark it as R boundary
2a) from right-1 to left+1: if wall is larger than remembered wall, mark it as R boundary and remember it instead
this found all right boundaries

3) same but for left boundaries and reversed sides
possible to mark as middle boundaries because all R and L that are not those on edges are always both

4) now find filled areas
4a) remember left-most as left boundary
4b) from left+1 to right:
4c) if wall is marked as R boundary, remember minimum of L and this R sizes, go through surrounded sub-area and accum min - size to total sum
4d) remember this R boundary as next left boundary and repeat until reached right-most R boundary

5) report total sum

correction: 2a) should be "larger or equal" instead of "larger"

try [0, 1, 5, 3, 10, 7, 7, 8, 3] with your algo and see it fail horribly
you shouldn't get the job for sure

find min value between 0 and last index and then aggregate the rest as min - x

negative water?

my attempt
idk someone break it please
def water(elevation_map):
total_water_acc = 0

last_peak_idx = 0
current_section_water_acc = 0
# Forward
for i in range(len(elevation_map)):
if elevation_map[i] >= elevation_map[last_peak_idx]:
last_peak_idx = i
total_water_acc += current_section_water_acc
current_section_water_acc = 0
else:
current_section_water_acc += elevation_map[last_peak_idx] - elevation_map[i]

# Backward
last_peak_idx = len(elevation_map) - 1
current_section_water_acc = 0
for i in range(len(elevation_map) - 1, -1, -1): # uhh backwards range is hard
if elevation_map[i] > elevation_map[last_peak_idx]:
last_peak_idx = i
total_water_acc += current_section_water_acc
current_section_water_acc = 0
else:
current_section_water_acc += elevation_map[last_peak_idx] - elevation_map[i]

return total_water_acc

So the green areas of something like this?

Attached: PolicyViz-Histogram-image006-1140x700.png (1140x700, 79K)

find min value, then compare the rest with min. if there is a value greater than min, then we need to split at that index and recursively measure these 2 arrays, else just aggregate min - x if x is less than min

1) reduce left and right sides
1a) go from left to right and find first decreasing neighbors, remember the larger (left) one
1b) same from right to left
1c) if those 2 are same, nothing gets filled and algorithm quits, else just forget anything outer from these 2
this found largest bounded sub-array

2) Iterate over list and find global maximum index

3) Iterate from the left and keep track of current max value seen (mLocal) if next value < mLocal, accumulate the difference
If nect value > mLocal then the value becomes mLocal
Repeat untill global maximum reached

Do the same from the right.

If there were multiple equal global maxima, choose one at random

how is the question relevant to what i'll be doing on a daily basis?

i don't think i understand what you meant, but
>if x is less than min
something looks off just by reading this

Actually with that algorithm you don't even have to cut the left and right off, but it helped me to visualise the problem so whatever.

code, but didn't bother to put the reduced edges back

# lake is created between two walls in which no wall is larger than those two
# wall is right boundary if there isn't any larger on right

def reduce_left(walls):
for i in range(len(walls) - 1):
if walls[i] > walls[i+1]:
return walls[i:]
return []

def reduce_right(walls):
for i in range(len(walls)-1, 1, -1):
if walls[i] > walls[i-1]:
return walls[:i+1]
return []

def reduce_walls(walls):
return reduce_right(reduce_left(walls))

def find_boundaies(walls):
boundaries = set()

m = walls[0]
for i in range(len(walls)):
if walls[i] >= m:
boundaries.add(i)
m = walls[i]

m = walls[-1]
for i in range(len(walls)-1, 0, -1):
if walls[i] >= m:
boundaries.add(i)
m = walls[i]

return boundaries

def find_depths(walls, boundaries):
depths = [0 for _ in walls]
bound = walls[0]
bound_i = 0
for i in range(1, len(walls)):
if i in boundaries:
height = min(walls[i], walls[bound_i])
for j in range(bound_i + 1, i):
depths[j] = height - walls[j]
bound = walls[i]
bound_i = i
return depths

def visualize(walls, depths):
height = max(walls)
for h in range(height+1, 0, -1):
for i in range(len(walls)):
if h > walls[i] + depths[i]:
print(' ', end='')
elif h > walls[i]:
print('~', end='')
else:
print('#', end='')
print()

def rain(walls):
walls = reduce_walls(walls)
if len(walls) == 0:
return 0;

boundaries = find_boundaies(walls)
depths = find_depths(walls, boundaries)

visualize(walls, depths)
return sum(depths)


rain([0, 0, 3, 7, 3, 1, 4, 0, 0, 3, 0, 2, 1, 1])

#
#
#
#~~#
##~#~~#
##~#~~#~#
####~~#~#

not O(1) space

#include
#include

int main() {
// Test vector
std::vector v = {0, 1, 6, 2, 9, 3, 9, 1, 3, 2};

// Find max index
int maxIndex = 0;
int max = 0;
for (int i = 0; i < v.size(); i++) {
if (v[i] > max) {
maxIndex = i;
max = v[i];
}
}

int sum = 0;
int localMinimum = 0;
// Iterate from left
for (int i = 0; i < maxIndex; i++) {
if (v[i] < localMinimum) {
sum += localMinimum - v[i];
}
else {
localMinimum = v[i];
}
}

// Iterate from right
localMinimum = 0;
for (int i = v.size() - 1; i > maxIndex; i--) {
if (v[i] < localMinimum) {
sum += localMinimum - v[i];
}
else {
localMinimum = v[i];
}
}

std::cout

yeah I just realized I don't need that boundaries since, as I said, they are all both left and right so I can calc depths on-fly
depths array is only there for visualization

localMinimum should be localMaximum

public void TestMeasure()
{
Assert.True(Measure(new int[] {2, 1, 2}, 0, 2) == 1);
Assert.True(Measure(new int[] {3, 0, 1, 3, 0, 5}, 0, 5) == 8);
Assert.True(Measure(new int[] {2, 1, 3, 0, 3}, 0, 4) == 4);
}

public int Measure(int[] items, int from, int to)
{
int min = Math.Min(items[from], items[to]);
int sum = 0;
for (int i = from + 1; i min)
return Measure(items, from, i) + Measure(items, i, to);
sum += min - items[i];
}
return sum;
}

sudo solve the problem
Done.

int f(int *a,int *b)
{
int c= 0;
while(a

function fill(walls) {
result = 0

startIndex = undefined
endIndex = undefined

previousWall = undefined
currentWall = undefined

for (i = 1; i < walls.length; i++) {
previousWall = walls[i - 1]
currentWall = walls[i]

if ((previousWall > currentWall) && !startIndex) {
startIndex = i - 1
} else if ((previousWall < currentWall) && startIndex) {
endIndex = i + 1
}

if (startIndex && endIndex) {
slice = walls.slice(startIndex, endIndex)
limit = Math.min(slice[0], slice[slice.length - 1])

for (j = 0; j < slice.length; j++)
result += (slice[j] < limit) ? (limit - slice[j]) : 0

startIndex = undefined
endIndex = undefined
}
}

return result
}

if(1024%2==0) op="faggot";

As I told you, without further questioning the interviewer and 0(1) space, I did the basic.

I don't know, I can't ask for explanation. I receive everyday an email with a code challenge. I just answer them the quick as I can and move on with my day. No time to be thinking what if this, what if that?