# You CAN solve this, right? I got asked this question during the interview for my junior SWE position at OpenAI.

You CAN solve this, right?
I got asked this question during the interview for my junior SWE position at OpenAI.

 ChatGPT Wizard Shirt \$21.68 Beware Cat Shirt \$21.68
 ChatGPT Wizard Shirt \$21.68
1. 2 months ago
Anonymous

2. 2 months ago
Anonymous

I have no tech background so I’d ask the interviewer some idiotically worded inane question using knowledge from a field I’m familiar with using intentionally vague terminology. Not fun is it you wienersucker?

• 2 months ago
Anonymous

Literally the only correct answer. These homosexuals love getting off asking convoluted questions filled with bullshit. Ask them to walk you through the sequence of events in hernia surgery repair and watch them flounder. What kind of mesh do i use captain homosexual??!

• 2 months ago
Anonymous

>What kind of mesh do i use captain homosexual??!
i'm saving this to use out of context

3. 2 months ago
Anonymous

yeah just go layer by layer.
make a 3d array of enum {solid, unchecked_air, air_connects_to_open_border, water}
>fill 3d array with solid or unchecked_air depending on input data

> for each unchecked_air block on that layer, if (has air_connects_to_open_border below it) or (is on border), flood fill any adjacent unchecked_air blocks on that layer with air_connects_to_open_border
> put water in all the unchecked_air blocks
> loop with next layer up

• 2 months ago
Anonymous

>yeah just go layer by layer
That's the easy part to figure out

>for each unchecked_air block on that layer, if (has air_connects_to_open_border below it) or (is on border), flood fill any adjacent unchecked_air blocks on that layer with air_connects_to_open_border
This won't work.

• 2 months ago
Anonymous

>This won't work.
Why not?

• 2 months ago
Anonymous

classic

4. 2 months ago
Anonymous

The adjacent nonzero height squares form a graph, find all the unique loops and compute their area, multiply the area by the height of the lowest wall to get the water volume, sum the volume for all loops to get the answer.

Simple.

• 2 months ago
Anonymous

Wrong, try again.

• 2 months ago
Anonymous

For the problem as stated, it is correct.
Verification not even required

• 2 months ago
Anonymous

>find all the unique loops and compute their area
Whoops! There are blocks inside your looped areas. What now? And what if there's nested loops, i.e. lake inside an island inside a lake?

• 2 months ago
Anonymous

Valid criticism, you'll have to find if a loop is bounded by another loop, and if it is, simply subtract the volume of all its blocks from the outermost loop's volume.
I hate these gotcha puzzles.

• 2 months ago
Anonymous

Find if any block is bounded by a loop, actually, in fact any nonzero blocks within a loop can be ignored from computation and simply have their volume subtracted.

• 2 months ago
Anonymous

Continuing my thought process.
Find all unique loops, sort them by circumference, the largest loop is guaranteed not to be contained by another loop.
Compute its area and volume as before, subtract the volume of all blocks it contains, if any of the contained blocks are part of another loop, delete that loop, repeat until there are no more loops in your list.

I'm kinda just thinking out loud so there may be more gotchas that I haven't noticed.

5. 2 months ago
Anonymous

fyi, this is one of the most popular interview questions reported on leetcode, if you can't do it, you're never going to get a good job

• 2 months ago
Anonymous

Nah, this is the non-babby version. You're probably thinking of the 2d version of this problem, where all you need to do is use two pointers from start and end, and then just check how much water fits between the two columns using the height of the smaller column (excluding columns inbetween)

• 2 months ago
Anonymous

[...]
Isn't this just the classic question about how to implement bucket tool in Paint?
https://en.wikipedia.org/wiki/Flood_fill

oh, my bad, you're right, it's the 3d one, still a moderately common question

https://leetcode.com/problems/trapping-rain-water-ii/

• 2 months ago
Anonymous

I'm reading the solution, and I still couldn't even make sense of it. Reminds me of my university days lol.
Gonna kms.

• 2 months ago
Anonymous

https://i.imgur.com/1MMWqSw.png

You CAN solve this, right?
I got asked this question during the interview for my junior SWE position at OpenAI.

Isn't this just the classic question about how to implement bucket tool in Paint?
https://en.wikipedia.org/wiki/Flood_fill

6. 2 months ago
Anonymous

>go slice by slice
>floodfill the empty spaces
>count the floodfilled pixes
Yeah, this is boring, I'm not coding it.

• 2 months ago
Anonymous

Oh, and ignore the floodfill if it touches the borders.

• 2 months ago
Anonymous

Oh, and ignore the floodfill if it touches the borders.

Lmao. Why larp? What do you even mean by "floodfill the empty spaces"?

• 2 months ago
Anonymous

>What do you even mean by "floodfill the empty spaces"?
For every cell that isn't a block, you execute a floodfill some sentinel value. The empty space means the cells that aren't block or sentinel valued. If your floodfill reaches the enges of the matrix, you simply count it as a spill and don't count those cells.

• 2 months ago
Anonymous

I mean... I just wrote this as a top-down map of sorts in my editor, and this solution immediately showed up in my head. This doesn't ever require to check for neighbors for a nearby n-dimensional array in a dimension+x array.

Computation time limit/memory exceeded 🙂

Sorry anon, we'll be moving forward with another candidate.

• 2 months ago
Anonymous

>Computation time limit/memory exceeded 🙂
No, it hasn't been exceeded, because it doesn't use any extra memory and it only goes over every relevant cell once. You're a mongoloid.

• 2 months ago
Anonymous

>and it only goes over every relevant cell once.
Except it doesn't because depending on the number of floodfills on the layer you might have to query about cell xy up to 8 times

• 2 months ago
Anonymous

>mongoloidal fizzbuzzing wagecretin can't implement a floodifll properly
Like pottery.

• 2 months ago
Anonymous

The point is you'd have to execute a flood fill potentially for every 4th block which is inefficient as frick you brainlet

• 2 months ago
Anonymous

Jesus frick, wagedrones are legit mentally challenged. Competence crisis is already here.

• 2 months ago
Anonymous

>My code is too inefficient
>It's the others fault
Ok brainlet

• 2 months ago
Anonymous

You can't solve a kiddie problem and your nonsensical schizophrenic babble simply doesn't matter.

• 2 months ago
Anonymous

Here's a little spoiler for you, neet baby: while you can speed up the solution using flood fills for large lakes, you didn't describe the actual solution itself, which is finding those lakes in the first place. You just say "lol just try literally EVERY SINGLE air block" like the little brainlet that you are.

• 2 months ago
Anonymous

>psychotic wagegolem keeps spewing GPT-2 tier babble

• 2 months ago
Anonymous

[...]
oh, my bad, you're right, it's the 3d one, still a moderately common question

https://leetcode.com/problems/trapping-rain-water-ii/

Here's a little spoiler for you, neet baby: while you can speed up the solution using flood fills for large lakes, you didn't describe the actual solution itself, which is finding those lakes in the first place. You just say "lol just try literally EVERY SINGLE air block" like the little brainlet that you are.

You can't solve a kiddie problem and your nonsensical schizophrenic babble simply doesn't matter.

>My code is too inefficient
>It's the others fault
Ok brainlet

Jesus frick, wagedrones are legit mentally challenged. Competence crisis is already here.

I thought we were gonna have fun with a little toy puzzle and you Black folk decided to hijack the thread for your little argument, this is why we can't have nice things.

• 2 months ago
Anonymous

The mentally ill wage golem decided to hijack the thread. I just provided the correct solution but apparently this thread consists of a bunch of literal braindead Black folk who don't understand how to implement a scanline-based flood fill.

• 2 months ago
Anonymous

>who don't understand how to implement a scanline-based flood fill
You will never need to implement a scanline-based floodfill in web dev, you dumb moron.

• 2 months ago
Anonymous

First day?

• 2 months ago
Anonymous

this. boring problem, no fun elegant solution

function get_rainwater_collected(arr_2d) {
let total_area = arr_2d.length * arr_2d[0].length;
let rainwater_collected = 0;
let slice;

const make_slice = (layer) => {
let empty_slice = true;
slice = arr_2d.map((col) =>
col.map((wall) => {
if (wall > layer) {
empty_slice = false;
return 1;
}
return 0;
})
);
return !empty_slice;
};

const flood_fill = (x, y) => {
if (x < 0 || y < 0 || x >= slice.length || y >= slice[0].length || slice[x][y] !== 0) return;
slice[x][y] = 1;
flood_fill(x + 1, y + 0);
flood_fill(x - 1, y + 0);
flood_fill(x + 0, y + 1);
flood_fill(x + 0, y - 1);
};

let layer = 0;
while (make_slice(layer++)) {
// loop around edges of array and flood fill
for (let x = 0; x < slice.length; x++) {
for (let y = 0; y < slice[0].length; y++) {
if ((x === 0 || x === slice.length - 1) || (y === 0 || y === slice[0].length - 1)) {
flood_fill(x, y);
}
}
}

console.log(slice);

rainwater_collected += total_area - slice.flat().reduce((acc, a) => acc + a);
}

return rainwater_collected;
}

• 2 months ago
Anonymous

I don't see the height of the walls accounted for.

• 2 months ago
Anonymous

it's there. we don't count the height since we just do it by slice. wall > layer

• 2 months ago
Anonymous

Since I don't understand your code, I'll take your word. You're hired.
t. hr

• 2 months ago
Anonymous

>Since I don't understand your code, I'll just judge based on if I want to have sex with you. We decided to go with a different candidate.
>t. hr

• 2 months ago
Anonymous

hr doesn't do technical interviews

• 2 months ago
Anonymous

I've had HR ask basic trivia questions like hurr durr what is the difference between a stack and a heap. This is at a top 10 market cap company.

• 2 months ago
Anonymous

that's probably a pre technical interview phone screen not the real interview

• 2 months ago
Anonymous

You'd be surprised how many people that filters.

• 2 months ago
Anonymous

function get_rainwater_collected(height_map) {
const max_height = Math.max(...height_map.flat())
const total_area = height_map.length * height_map[0].length
let rainwater_collected = 0;

// Fill everything up to a certain height
const flood_fill = (x, y, toHeight) => {
if (x < 0 || y < 0 || x >= height_map.length || y >= height_map[0].length || height_map[x][y] >= toHeight) return;
height_map[x][y] = toHeight;
flood_fill(x + 1, y + 0, toHeight);
flood_fill(x - 1, y + 0, toHeight);
flood_fill(x + 0, y + 1, toHeight);
flood_fill(x + 0, y - 1, toHeight);
};

for (let cur_height = 1; cur_height <= max_height; cur_height++) {
// loop around edges of array and flood fill
for (let x = 0; x < height_map.length; x++) {
flood_fill(x, 0, cur_height);
flood_fill(x, height_map[0].length - 1, cur_height);
}
for (let y = 1; y < height_map[0].length - 1; y++) {
flood_fill(0, y, cur_height);
flood_fill(height_map.length - 1, y, cur_height);
}

const filledCells = height_map.reduce((acc, a) => acc + a.reduce((acc2, a2) => acc2 + (a2 >= cur_height ? 1 : 0), 0), 0);
const collected = total_area - filledCells;
rainwater_collected += collected;
}
return rainwater_collected;
};

optimized a bit but only passing 39/42 of leetcode tests in time limit. would need to use some algorithm rather than this naive one

• 2 months ago
Anonymous

Its a man thoughbeit

7. 2 months ago
Anonymous

>floodfill
Why you can't just loop through each of the row and check each 0 element for neighbors in x+-,y+- coordinates? If x, y indexes get beyond the limits of the array, just drop counting water and go next element; if all checks out, increase the water counter by the lowest non-zero neighbor you've got.

• 2 months ago
Anonymous

I mean... I just wrote this as a top-down map of sorts in my editor, and this solution immediately showed up in my head. This doesn't ever require to check for neighbors for a nearby n-dimensional array in a dimension+x array.

• 2 months ago
Anonymous

If your algorithm isn't a floodfill it won't work. Yours isn't a floodfill.

• 2 months ago
Anonymous

>What do you even mean by "floodfill the empty spaces"?
For every cell that isn't a block, you execute a floodfill some sentinel value. The empty space means the cells that aren't block or sentinel valued. If your floodfill reaches the enges of the matrix, you simply count it as a spill and don't count those cells.

Even I can tell both of you are spouting bullshit.

• 2 months ago
Anonymous

I can tell you, like the rest of nu-/g/, have an IQ of around 90. This place is full of literal cretins. I mean the oldschool kind they used to sterilize for being feeble-minded. Pretty disgusting. How did BOT and BOT become the dumbest boards on the site?

• 2 months ago
Anonymous

You might be moronic.
According to your algo, pic rel is filled

• 2 months ago
Anonymous

>If x, y indexes (of neighbors, dipshits) get beyond the limits of the array, just drop counting water and go next element
I admit that I'm a lower life form called "non-native english speaker", but seriously, anon, are you per chance fricking your eye-sockets on a daily basis?

• 2 months ago
Anonymous

[[1, 1, 1, 1, 2, 0]
[3, 0, 1, 0, 0, 1]
[2, 0, 2, 0, 1, 0],
[0. 2. 1, 2, 3, 1]]

Which resolves into this:
[[1, 1, 1, 1, 2, 0]
[3, -1, 1, -1, -1, 1]
[2, -1, 2, -1, 1, 0],
[0, 2, 1, 2, 3, 1]]

Your solution works only for 1 enclosed cell. Try again.

8. 2 months ago
Anonymous

https://leetcode.com/problems/trapping-rain-water-ii/

• 2 months ago
Anonymous

import heapq

class Solution:
def trapRainWater(self,heightMap):
if not heightMap or not heightMap[0]: return
m,n = len(heightMap),len(heightMap[0])
heap = []
visited = [[0]*n for _ in range(m)]
while heap:
height,i,j = heapq.heappop(heap)
for d in dirs:
x,y = i+d[0],j+d[1]
if x>=0 and x<m and y>=0 and y<n and not visited[x][y]:
water += max(0,height-heightMap[x][y])
heapq.heappush(heap,(max(height,heightMap[x][y]),x,y))
visited[x][y] =1
return water

• 2 months ago
Anonymous

whoops
import heapq

class Solution:
def trapRainWater(self,heightMap):
if not heightMap or not heightMap[0]: return
m,n = len(heightMap),len(heightMap[0])
heap = []
visited = [[0]*n for _ in range(m)]

for i in range(m):
for j in range(n):
if i ==0 or j ==0 or i == m-1 or j == n-1:
heapq.heappush(heap,(heightMap[i][j],i,j))
visited[i][j] =1

dirs = [(1 ,0),(-1 ,0),(0 ,1),(0 ,-1)]
water =0

while heap:
height,i,j = heapq.heappop(heap)
for d in dirs:
x,y = i+d[0],j+d[1]
if x>=0 and x<m and y>=0 and y<n and not visited[x][y]:
water += max(0,height-heightMap[x][y])
heapq.heappush(heap,(max(height,heightMap[x][y]),x,y))
visited[x][y] =1
return water

• 2 months ago
Anonymous

>https://leetcode.com/problems/trapping-rain-water-ii/
I got filtered

9. 2 months ago
Anonymous

Start with an empty array of arrays for each row, initialize to 0
Iterate on each row, mark all spaces that lie between two blocks, with the height of the lowest of the two, mark them with -1 if the spot has a wall.
Repeat for columns
Take the min for each point using the two new maps. That's water capacity for that tile
Iterate through the water capacity map, and if two adjacent tiles have different numbers (excluding -1) and if so set them both to the lowest and restart the loop (shit complexity but I can't think of a better way to track cascading changes). Track the sum of all non-(-1) grids.

Can't be arsed to write code

10. 2 months ago
Anonymous

find if the point is within an entrapment in the lowest slice. It's an integer grid, so pass through each space by-row and by-column, give each coordinate a value based on the number of times you've changed from a 0-value to a non-0 value height. Every non-brick in that row or column is not in an entrapment if its value is 0 or the maximum in the row/column. A brick is in an entrapment if it can be in an entrapment in both passes.
Any position that isn't a brick is an entrapment, so the layer's water value is the sum of all the coordinates for entrapped spaces.
now turn every coordinate into a brick of value 1, repeat the process for the next slice, until there are less than 4 coordinates left on a slice (the minimum necessary to make an entrapment in a 2d integer grid)

11. 2 months ago
Anonymous

[[0, 1, 0, 1, 0, 0]
[1, 0, 1, 0, 1, 0]
[0, 1, 0, 1, 0, 0]
[0, 2, 0, 0, 0, 0]
[2, 0, 2, 0, 1, 0]
[2, 0, 2, 1, 0, 1]
[0. 2. 0. 1. 1. 1]]

12. 2 months ago
Anonymous

You just do a BFS version of OpenCV2's ConnectedComponentsWithStats, where you fill every square with a specific color and then you have information on all of them, plus their volume. Next you just discard everything that is touching the edge

• 2 months ago
Anonymous

Oh look, the first anon who proposed an actual solution

• 2 months ago
Anonymous

Yes but I forgot that height can be more than one, so after you do this fill, you decrease all wall sizes by one and do it again for all patches that were gathered before, I think this could work, but I am not sure

• 2 months ago
Anonymous

I don't like the idea of iterating over every square for this and definitely not multiple times.

• 2 months ago
Anonymous

You don't need to iterate over every square, only those within [1, size-2] borders.

• 2 months ago
Anonymous

Obviously I didn't mean every square on an infinite plane, I just suspect it might be possible to do without heavy quadraric behavior, but I'm too lazy to implement my own solution so what the frick do I know.

• 2 months ago
Anonymous

So what I meant is something like this.
struct area_info {
int surface;
bool edge;
};

std::map<int, area_info> cc_with_stats(int **arr, int w, int h) {
std::map<int, area_info> areas;
int curarr = -1;
for (int i=0; i<w; i++) {
for (int j=0; j<h; j++) {
if (arr[i][j] != 0) continue;
int cur = curarr;
if (i > 0 && arr[i-1][j] < 0)
cur = arr[i-1][j];
if (j > 0 && arr[i][j-1] < 0)
cur = arr[i][j-1];
if (i < w-1 && arr[i+1][j] < 0)
cur = arr[i+1][j];
if (j < h-1 && arr[i][j+1] < 0)
cur = arr[i][j+1];
if (areas.count(cur) < 0)
areas[cur] = {0, false};
areas[cur].surface++;
if (!areas[cur].edge && (i == 0 || j == 0 || i == w-1 || j == h-1))
areas[cur].edge = true;
arr[i][j] = cur;
if (curarr == cur)
curarr--;
}
}
return areas;
}

It's probably wrong, I haven't tested it, but this should give you a map of areas with their size and whether they touch the edge or not. Also the input array should now be marked with negative integers representing different areas. This is a bit different that cv2, because it allows for regions to touch each other (I allow this so that it is actually faster). and from here on you can do the following: loop over returned areas, add all non-edge to count, then decrease all walls by 1, if wall becomes 0, check all neigbours of the wall and set their edge to true if any other area that touches this wall has that edge set to true. and repeat that. If you set the walls to negative before running this, you can then also use a vector instead of the map, because then the areas can have positive indexes.

• 2 months ago
Anonymous

It is not very fast, it is O(w*h*m) where m is the max height at worst case scenario. algorithm can of course finish as soon as all areas are considered edge areas

13. 2 months ago
Anonymous

Learn logic
Not Maths

14. 2 months ago
Anonymous

Dont know, dont care , dont need to know. I work in management now. Frick you nerds

15. 2 months ago
Anonymous

So, the actual task isn't to count the water, but to detect the bordered spaces where water can be gathered in a given matrix. Then for each "lake" you do air_packet_count*min_border_height, sum all of them and give that as an answer.

• 2 months ago
Anonymous

The minimal size of a lake is three. So, you take a cut of input matrix of that size.
[0, 1, 0]
[1, 0, 1]
[0, 1, 0]
If upper, bottom, left, and right edges are filled, it's a lake and you do the thing for that.
[0, 1, 0]
[1, 0, 0]
[0, 0, 1]
No lake, you need to move. You decide to move right - the next possible wall is outside the lake, you move by 3 points in the left.
[0, 1, 0] [0, 1, 0]
[1, 1, 1] [1, 1, 0]
[0, 0, 1] [0, 0, 1]
In case of these, by 2 and 0 respectively.
[0, 1, 0]
[1, 0, 1]
[1, 0, 1]
You've got a potential lake. So, you take this and move it in the direction of the 0 which may have a border.
[0, 1, 0]
[1, 0, 0]
[1, 0, 1]
[0, 1, 0]
Here's a lake.
[0, 1, 0]
[1, 0, 1]
[1, 0, 1]
[1, 0, 0]
[0, 1, 1]
After going down, we need to go left. But not take the whole column, only a 3-cell chunk of it.
[0, 1, 0, x, x]
[1, 0, 1, x, x]
[1, 0, 1, 1, 1]
[1, 0, 0, 0, 1]
[0, 1, 1, 1, 0]
Here's a lake. Now that I see it, there should be two more matrixes, explored areas and unexplored. Hm...

Just thinking.

• 2 months ago
Anonymous

[1,1,1,1,1]
[1,0,0,0,1]
[1,0,0,0,1]
[1,0,0,0,1]
[1,1,1,1,1]
ACK! Thanks for playing anon

• 2 months ago
Anonymous

If there are 3 zeros in the left-bottom corner, one can always "move" array both left and down.

• 2 months ago
Anonymous

I've wanted to do this solution (run 3x3 explorer, expand it to the borders when there're pathways for the water till lake's end while counting minimal wall height, pass the lake slice to a function taking it and min wall height which will count all zero's there, after that random jump the kernel somewhwere else according to exploration map synced with the actual heightmap, disregard counter if touching the edges of the height-map... this can be ironed out still) but then anons've gone "brr brr priority queue just slice and spill bro go by layers moron" and I've lost the motivation to do this inefficient and memory-hungry solution.

16. 2 months ago
Anonymous

>tfw I work in tech and I'm too much of a brainlet to solve this

17. 2 months ago
Anonymous

I'm too lazy to try to think up a complete solution right now, but my instinct is to use some sort of floodfill-based approach. If the fill hits the outer edges then it cannot hold any water, then you determine the "interior" basins which are closed and calculate how much water they can hold using the minimum height of enclosing blocks. I assume it's possible for the floor height to be greater than 0 too but to still have a basin with enclosing blocks which are even taller than the floor, so that would need to be taken into account as well but it shouldn't be too hard.

Also when processing the tiles it would obviously be a good idea to skip tiles which have already been processed as part of a connected area that was previously encountered. I guess this is not actually necessary in the most naive implementation but it would be an obvious improvement to make.

18. 2 months ago
Anonymous

Isn't this just bfs? Keep picking random unoccupied squares and performing bfs. You'll eventually get all connected regions of unoccupied squares. Then for each region, loop over all its constituent squares. For each square, if any of its neighbors is an edge of the grid (but keep track all neighbors for the next step), discard that region (it is not enclosed). At this point, you have all enclosed regions and also all neighbors that are occupied for each region. For each region, compute the min height of any neighboring occupied edge, call this H. The total volume of water that can be stored in a region is H * #unoccupied squares per region. Sum over all regions.
Should be O(N) time/space in the number of squares in grid.

19. 2 months ago
Anonymous

[...]

Isn't this just bfs? Keep picking random unoccupied squares and performing bfs. You'll eventually get all connected regions of unoccupied squares. Then for each region, loop over all its constituent squares. For each square, if any of its neighbors is an edge of the grid (but keep track all neighbors for the next step), discard that region (it is not enclosed). At this point, you have all enclosed regions and also all neighbors that are occupied for each region. For each region, compute the min height of any neighboring occupied edge, call this H. The total volume of water that can be stored in a region is H * #unoccupied squares per region. Sum over all regions.
Should be O(N) time/space in the number of squares in grid.

Good job anons, you solved it. Now post code

20. 2 months ago
Anonymous

leetcodeBlack folk tongue my anus
>t. 200k senior dev, didn't need to answer bullshit CS questions in my interview.

• 2 months ago
Anonymous

It's just a fun puzzle, this obviously isn't real programming

21. 2 months ago
Anonymous

>for my junior SWE position at OpenAI.
Ah so you enjoy taking it up the ass too?

22. 2 months ago
Anonymous

what if this

• 2 months ago
Anonymous

It's a heightmap, so blocks cant have open spaces beneath them

• 2 months ago
Anonymous

What? Yes they can

• 2 months ago
Anonymous

>Given a 2-dimensional array where each nested array represents a row of blocks and each item in the array represents the number of stacked blocks

• 2 months ago
Anonymous

Oh, you're right

• 2 months ago
Anonymous

oh. kinda disappointing

• 2 months ago
Anonymous

Although it'd definitely make an interesting, even more difficult iteration of the problem

You'd also have to consider
>Caverns covered by blocks
>Empty spaces in columns that also get filled by water

I wonder how you'd solve these scenarios hmmm.

I could think of an approach where you just flood everything but then check for underwater floating air blocks, if they have a path to get filled by the water. But I'm not sure how tbh

• 2 months ago
Anonymous

Oh shit, and then there could also be holes in lakes meaning they would run out. Frick this makes the whole thing 3x more difficult, to the point where it might actually be just easier to write a simulator and run it kek. But I'm sure there's an algorithmic way to consider all edge cases

• 2 months ago
Anonymous

And these holes could lead to other lakes.... Yeah no floating blocks makes the whole thing 30x more complex

23. 2 months ago
Anonymous

[...]

im

yeah just go layer by layer.
make a 3d array of enum {solid, unchecked_air, air_connects_to_open_border, water}
>fill 3d array with solid or unchecked_air depending on input data

> for each unchecked_air block on that layer, if (has air_connects_to_open_border below it) or (is on border), flood fill any adjacent unchecked_air blocks on that layer with air_connects_to_open_border
> put water in all the unchecked_air blocks
> loop with next layer up

and I did intuit the solution in less than a second

• 2 months ago
Anonymous

• 2 months ago
Anonymous

how is it shit

• 2 months ago
Anonymous

it's O(n*m) time and memory. You want O(n) time and memory

• 2 months ago
Anonymous

what is n moron

• 2 months ago
Anonymous

n is the number of positions in the array
m is the largest height value in the array

• 2 months ago
Anonymous

you need to do n*m if you don't assume stacks can have gaps in them

• 2 months ago
Anonymous

rephrase for clarity:
in the case that you assume that vertical stacks don't have gaps, you can do O(n)
I don't assume that
So I did a O(n*m) solution

having gaps is a very likely feature request

• 2 months ago
Anonymous

Stop memeing brainlet.

what is n moron

Your solution is inefficient though, that's true. You can achieve O(MNlog(MN)) time complexity and O(MN) space complexity

• 2 months ago
Anonymous

>glub glub glub hurr muh O(n)
This is (You) gargling on Black person cum.

24. 2 months ago
Anonymous

Of course. It's 7

25. 2 months ago
Anonymous

[...]

Ah, it's one of these threads.
You should just leave the interview.

26. 2 months ago
Anonymous
• 2 months ago
Anonymous

(Me)
(The code works fine)
Get fricked

• 2 months ago
Anonymous

>mixtral 7x8b
can you do that same example with gtp3.5 so we can compare?

• 2 months ago
Anonymous

I don't subscribe to ~~*OpenAI*~~ so no.

• 2 months ago
Anonymous

Now ask it to do for a 3d array where 1 is a block kek

Any AI can copy-paste solutions to leetcode problems

• 2 months ago
Anonymous

>le goalpost mové

• 2 months ago
Anonymous

I understand how it works and the idea, but I can't imagine myself coming up with that. is it over for me?

• 2 months ago
Anonymous

Just think harder and longer. Start with a brute force solution first and then think of ways to optimize. It's only over if you can't even come up with a brute force solution.

Yes there are meme leetcode problems that require you to know about some semi obscure algo that some mathematician came up in the 90s kek (majority in array comes to mind), but usually most problems use well known concepts like bfs/dfs (which you can also use on this problem, DP, pointers and stacks/recursion, and so on and so on

• 2 months ago
Anonymous

So what I meant is something like this.
struct area_info {
int surface;
bool edge;
};

std::map<int, area_info> cc_with_stats(int **arr, int w, int h) {
std::map<int, area_info> areas;
int curarr = -1;
for (int i=0; i<w; i++) {
for (int j=0; j<h; j++) {
if (arr[i][j] != 0) continue;
int cur = curarr;
if (i > 0 && arr[i-1][j] < 0)
cur = arr[i-1][j];
if (j > 0 && arr[i][j-1] < 0)
cur = arr[i][j-1];
if (i < w-1 && arr[i+1][j] < 0)
cur = arr[i+1][j];
if (j < h-1 && arr[i][j+1] < 0)
cur = arr[i][j+1];
if (areas.count(cur) < 0)
areas[cur] = {0, false};
areas[cur].surface++;
if (!areas[cur].edge && (i == 0 || j == 0 || i == w-1 || j == h-1))
areas[cur].edge = true;
arr[i][j] = cur;
if (curarr == cur)
curarr--;
}
}
return areas;
}

It's probably wrong, I haven't tested it, but this should give you a map of areas with their size and whether they touch the edge or not. Also the input array should now be marked with negative integers representing different areas. This is a bit different that cv2, because it allows for regions to touch each other (I allow this so that it is actually faster). and from here on you can do the following: loop over returned areas, add all non-edge to count, then decrease all walls by 1, if wall becomes 0, check all neigbours of the wall and set their edge to true if any other area that touches this wall has that edge set to true. and repeat that. If you set the walls to negative before running this, you can then also use a vector instead of the map, because then the areas can have positive indexes.

• 2 months ago
Anonymous

This so obviously doesn't work

I understand how it works and the idea, but I can't imagine myself coming up with that. is it over for me?

That would be because it's wrong
Consider
0, 1, 0
1, 0, 0,
0, 0, 0

This would return 1...

• 2 months ago
Anonymous

Nevermind, I suck cawks

• 2 months ago
Anonymous

No it wouldn't. By the time it gets to the 1s, all zeroes are already visited, which means that it cannot increase the volume

• 2 months ago
Anonymous

Yeah, I saw. That's a great solution.

27. 2 months ago
Anonymous

Otsu's method. Done. Frick off Code monkeys.

28. 2 months ago
Anonymous

wtf is the question?
count the blue squares = 7
most efficient lake is 8 squares = 4 lakes
morons keep overcomplicating simple shit to sound less moronic. Touch grass homosexuals

• 2 months ago
Anonymous

I saw your post 1 hour and 10 minutes ago and laughed and disregarded it as bait, but it keeps popping back into my head. I keep thinking about how someone might've arrived at the same problem/solution from the image, and the more I think about it, the more I realize you might not actually be baiting. And it's really perplexing and disturbing.

29. 2 months ago
Anonymous

return 7;

30. 2 months ago
Anonymous

>softwaregays waste a significant part of their life trying to one up other losers on meaningless toy problems
certified autism

• 2 months ago
Anonymous

Actually this. In a working environment you'd be able to solve this shit trivially because you'd know everything feeding into the problem.

31. 2 months ago
Anonymous

This would actually be challenging if floating blocks were allowed. Imagine a U shaped pipe where one leg is shorter than the other

32. 2 months ago
Anonymous

chat gippytee is so smart, humies could never have come up with this shit

33. 2 months ago
Anonymous

trick question, no solution possible

• 2 months ago
Anonymous

>I cannot think of a solution therefore no solution is possible

• 2 months ago
Anonymous

Correct

34. 2 months ago
Anonymous

Why am I being asked complicated math shit to do webdev?

• 2 months ago
Anonymous

Because smart people can solve these problems even if they're not relevant to the job, and stupid people who can't solve them tend to end up making shitty unmaintainable nightmares of a frontend that barely works.

• 2 months ago
Anonymous

So it's just gatekeeping and credentialism all the way down then?

• 2 months ago
Anonymous

Yes. Keeping out people who refer to "demanding basic competency" as "gatekeeping and credentialism" is an important part of keeping any business afloat.

• 2 months ago
Anonymous

as soon as you need a sorted queue it is no longer basic competency, but an advanced problem

• 2 months ago
Anonymous

You are the kind of person we're trying to keep out

• 2 months ago
Anonymous

>hey guize can I have 6 figs SWE salary?
>what's a heap, lol?

• 2 months ago
Anonymous

>I am a leetcode pajeet therefore I am a good coder
Lmao.

• 2 months ago
Anonymous

Knowing what a heap is is only useful in leetcode problems?
What kind of dev are you, the "I don't know I just write JSON" kind?

• 2 months ago
Anonymous

I didn't say that moron. I said that problems where you have to use a priority queue and it is not immediately obvious are advanced. Such as this one. Entire thread unable to solve it with exception of people who already encountered the same problem (which doesn't count) and people who used AI to solve it. Which also doesn't count. Not a single anon who came up with a solution himself

• 2 months ago
Anonymous

So from my non-coder perspective, the only way to prove your intelligence here is...
>be programmer
>have never heard of something called a "priority queue", scratch head when asked what that is
>get interview for seemingly-cushy job
>be given this question
>with only the information supplied by the question, independently re-invent the wheel, constructing the exact method needed for the correct solution

...and having any outside info or prior knowledge of priority queues disqualifies you from the actual job which is for creating new, novel solutions— not regurgitating what you already know.
Looks like every anon in this thread is ngmi

• 2 months ago
Anonymous

Again twisting words, homosexual? There is a reason why nobody ITT has solved it

• 2 months ago
Anonymous

Dude, chill out. What's your deal? Could you afford therapy or professional help?

• 2 months ago
Anonymous

>therapyspeak
you know what you need to do? you need to SHIT in the street and then pick it up with you TONGUE and eat it. YES, WHOLE. I hate therapyspeak nighgers so much it's unreal, literal pajeet ranjeet tier, plus the added fact of posting on facebook all day about java this java that, SHUT UP ranjeet, nobody wants to hear it. Whay are yiu even here? Pajeetchan is over there >>>

• 2 months ago
Anonymous

frick and ranjeets constantkly roaming on this board looking to dump their load of shit on our streets as id this is indfia, this is NOT India, nor is i tpajeetistan for that matter, take yopur street shitting behaviour on

[...]

right now you ranjeet pajeet with a load of shit in his stomach. java is not for us sirs, java is for indian chand only not for hjeeree

• 2 months ago
Anonymous

Not twisting, merely stating my observation based on everyone's comments. It's nothing against you and I think (if you're the one who said this stuff is advanced) that you're correct.

• 2 months ago
Anonymous

>I didn't say that moron. I said that problems where you have to use a priority queue and it is not immediately obvious are advanced. Such as this one
It was immediately obvious to anyone who said "flood fill". You're just too low-IQ to understand how a scanline floodfill works.

• 2 months ago
Anonymous

Flood fill doesn't account for different heights moron.

• 2 months ago
Anonymous

You obviously do it layer by layer, tardolini, which all the people who said to use floodfill mentioned.

• 2 months ago
Anonymous

Which is extremely inefficient and has no reason to use a priority queue moron.

• 2 months ago
Anonymous

You're a mouth-breathing mongoloid who doesn't understand how a scanline floodfill works. This place is teeming with clinical mental cripples and they can't even fathom they're disabled.

• 2 months ago
Anonymous

moron. JUST FLOODFILL HURR DURR YOU DON'T UNDERSTAND HOW IT WORKS.

• 2 months ago
Anonymous

It's not my fault that you don't understand how a scanline floodfill works, you mongoloidal animal. lol

• 2 months ago
Anonymous

>hurr durr just run floodfill for each different height value that's totally the correct solution!

• 2 months ago
Anonymous

You're a clinical cretin, no two ways about it. Imagine being so moronic that you're given 98% of the solution and can't figure out how to use it to solve 2% of the problem.

• 2 months ago
Anonymous

moron. If you are using bfs with a priority queue at any point that's not a fricking flood fill.

• 2 months ago
Anonymous

No, that's literally just a floodfill, you literal moron, and it's actually nice that you go out of your way to demonstrate your inability to understand this, because it shows that no matter how many algorithms you show to a moronic code ape, it can't truly grasp the essence of them.

• 2 months ago
Anonymous

Rearrd. Look "scanline flood fill" on literally any resource and see if that is what you get. A scanline is a line, not a fricking plane. Look up this problem and show me anywhere else where the solution is described as "scanline flood fill".

• 2 months ago
Anonymous

I don't need to look anything up, mongoloidal animal. You already played yourself by bringing this up, because anyone who understands what breadth-first search is can immediately see that a scanline-based floodfill is precisely a breadth-first traversal of the graph implicitly defined by neighboring cells. Not having an argument about this, I'm just using you to make a point: it doesn't matter how many leetcode toy problems a code ape solves, the code ape learns nothing.

• 2 months ago
Anonymous

YOU DON'T EVEN KNOW WHAT THE TERMS SCANLINE OR FLOODFILL EVEN MEANS. STOP BEING FRICKING moronic. What the frick is the """LINE""" you are talking about in a fricking graph.

• 2 months ago
Anonymous

The more you deny the obvious, the more you make my point for me. Imagine being so devoid of abstract thought you can't recognize obvious breadth-first traversal.

• 2 months ago
Anonymous

Man I was giving you the benefit of the doubt and thinking you actually understood the solution and are referring to different heights as "scanlines" for some reason but at this point you are too far gone and it's obvious you don't know what you are talking about.

• 2 months ago
Anonymous

I wasn't giving you any benefit of the doubt, on the other hand. It was obvious to me that you're a moronic ape from your first reply.

• 2 months ago
Anonymous

You are a moron for clearly doubling down a solution that doesn't work.

• 2 months ago
Anonymous

Oh, so you're actually so subhuman you don't see that it obviously works? I thought you were just too stupid to see that it's O(n).

• 2 months ago
Anonymous

The real optimal solution I'm talking about isn't O(n) because adding and removing elements from a priority queue isn't constant time, but you wouldn't know that because you aren't educated, as evident from the fact that you can't even explain what a scanline is.

• 2 months ago
Anonymous

Not reading your subhuman posts at this point. When I get home, I'll just take the 15 minutes it takes to implement just to shit all over you. We'll see how you cope then. lol

• 2 months ago
Anonymous

>I'll look up a solution and copy and paste it when I get home
That proves everything. How long will it take you to find one that says "scanline" somewhere or will you just change a random variable name?

• 2 months ago
Anonymous

Here's a moronicly simple O(n) scanline floodfill solution for a single layer:
https://pastebin.com/JBCabqSQ

And here's the basic scanline floodfill I started from:
https://pastebin.com/t8xXcK5z

It can be made much faster by using a more sophisticated scanline floodfill but that's besides the point with a mongoloid like you who can't even grasp the simple version.

• 2 months ago
Anonymous

>single layer
>O(n) for a two dimensional array

• 2 months ago
Anonymous

You do it layer by layer and it's still obviously O(n), you mongoloidal animal; it's still proportional to the number of cells.

• 2 months ago
Anonymous

>You do it layer by layer and it's still obviously O(n), you mongoloidal animal
Literal sub 20 iq gorilla Black person, thinks you can do something layer by layer and it's still O(n), no moron, it's O(n*l)

• 2 months ago
Anonymous

You will never have basic human sentience. Bottom line is that the runtime is proportional to the number of cells.

• 2 months ago
Anonymous

Layer by layer is O(N*H) rather than O(NlogN) which is better

yeah bro what if i gave you
1 1 1
1 748383637 1
1 1 1
your program would just give up

• 2 months ago
Anonymous

See

Post a working algorithm that does better than being poportional to the number of cells.

When you post something better than O(cell num) we'll talk.

• 2 months ago
Anonymous

here you go
https://pastebin.com/T5622i6J

• 2 months ago
Anonymous

That either loops infinitely or is so slow that I ran out of patience. You fail.

• 2 months ago
Anonymous
• 2 months ago
Anonymous

Your code literally just doesn't work. Next.

• 2 months ago
Anonymous

the heap solution is the correct one, submitting a O(max_height) solution and calling it O(N) is pure moronation and I'd laugh you out of the interview

• 2 months ago
Anonymous

My solution works and is therefore correct.
>b-b-but it's not le heckin' fast enough
It's reasonably fast and you didn't specify any constraints. Also see

https://i.imgur.com/1bPXjFd.png

Since a bunch of homos (none of whom managed to present a better algorithm) complain that O(number of cells) isn't fast enough, here's a simple improvement: do the flood fill on the bottom level and memorize the outlines of the pools + the number of cells inside the pool. Every time you go up a level, scan the outlines for breaches. If none are found, add the cell number for that pool to the volume, otherwise delete the entry for that pool. Keep going until you run out of pools or reach the top.

• 2 months ago
Anonymous

ok ill just mark you down as a fail then thanks for coming

• 2 months ago
Anonymous

Are Blacktic fizzbuzz wagie-wannabe even human? Either way I provided a much faster version of the basic floodfill one, and you provided nothing. lol

• 2 months ago
Anonymous

I told you the heap solution is correct. I've already passed gayman interviews and have a job but feel free to seethe

• 2 months ago
Anonymous

The sheer extent of your fizzbuzzing leetcode Blacksis is already exemplified by the phrase "the X solution is correct". Imagine being so mongrelized you think the "correct" solution is the one you read about on the wagegolem fizzbuzz interview prepper site.

• 2 months ago
Anonymous

ok

• 2 months ago
Anonymous

there is no need to solve anything for yourself. it's neither enjoyable nor beneficial. you simply need to look up the solution and retain it in your memory so that you can present it when asked. university, interview prep, and the professional environment all work the same way. if you disagree then i assume you're simply a neet who "codes" as a "hobby"

• 2 months ago
Anonymous

Since a bunch of homos (none of whom managed to present a better algorithm) complain that O(number of cells) isn't fast enough, here's a simple improvement: do the flood fill on the bottom level and memorize the outlines of the pools + the number of cells inside the pool. Every time you go up a level, scan the outlines for breaches. If none are found, add the cell number for that pool to the volume, otherwise delete the entry for that pool. Keep going until you run out of pools or reach the top.

• 2 months ago
Anonymous

A pool on an upper layer can be completely disconnected from ones on lower layers (ie, have a floor that isn't at 0), so this is wrong. Don't be moronic if you're going to act condescending.

• 2 months ago
Anonymous

>A pool on an upper layer can be completely disconnected from ones on lower layers
This is psychotic babble. It can't be disconnected because the matrix is a heightmap.

• 2 months ago
Anonymous

>This is psychotic babble
>It can't be disconnected because the matrix is a heightmap
That just means blocks can't float, not that pools can't exist exclusively above the 0 layer. Think for a fricking second.

• 2 months ago
Anonymous

>That just means blocks can't float
If they can't float they can't be disconnected, you mongoloidal ape. Either way, you are most likely the same subhuman animal that couldn't comprehend how the floodfill solution works and engaged in turly denial a few hours ago so there is no discussion to be had here.

• 2 months ago
Anonymous

The blocks aren't disconnected you tard, the pools are.
You can change the example input in the OP to
[[...], [...], [...], [...], [2,1,2,0,1,0], [2,1,2,1,0,1], [...]]
For a pretty obvious example of something that doesn't work with your solution, but I'm sure you still lack the spacial reasoning to understand that. Let me know if your moron-brain needs a pretty little diagram instead.

• 2 months ago
Anonymous

Are the the same mongoloidal animal I thought you were or are you a different one? You didn't define being the same one so I rest my case.

• 2 months ago
Anonymous

deny*

• 2 months ago
Anonymous

I am not whatever other guy you're having a schizo fit about, no.
Since you're completely avoiding the actual subject, I'll assume you've realized that you're wrong and are now just trying to save yourself the embarrassment of admitting it.

• 2 months ago
Anonymous

Provide a fully specified input you think it doesn't work for in your next post.

• 2 months ago
Anonymous

Christ, are you serious? You can't modify two numbers yourself?
Here, dipshit.
[[0,1,0,1,0,0], [1,0,1,0,1,0], [0,1,0,1,0,0], [0,2,0,0,0,0], [2,1,2,0,1,0], [2,1,2,1,0,1], [0,2,0,1,1,1]]

• 2 months ago
Anonymous

1 1
1 1 1
1 1
2
212 1
2121 1
2 111

Here it is, floodfilled with dots for water:
1 1
1.1.1
1 1
2
2.2 1
2.21.1
2 111

Here it is going one level up:
0 0
0.0.0
0 0
1
1.1 0
1.10.0
1 000

The outlines with a zero are breached so their dots don't count. What's the problem, tard?

• 2 months ago
Anonymous

>Here it is, floodfilled with dots for water
You floodfilled the second layer that had no water below it, in direct contrast to your initial explanation.

https://i.imgur.com/1bPXjFd.png

Since a bunch of homos (none of whom managed to present a better algorithm) complain that O(number of cells) isn't fast enough, here's a simple improvement: do the flood fill on the bottom level and memorize the outlines of the pools + the number of cells inside the pool. Every time you go up a level, scan the outlines for breaches. If none are found, add the cell number for that pool to the volume, otherwise delete the entry for that pool. Keep going until you run out of pools or reach the top.

>do the flood fill on the *bottom* level
So you've just changed your answer to be correct by floodfilling the entire 3D space, which also eliminates the purported efficiency benefit of your "solution"
Go be moronic somewhere else. Everyone can see through your bullshit easily.

• 2 months ago
Anonymous

You are a literal subhuman with zero reading comprehension.
>So you've just changed your answer to be correct by floodfilling the entire 3D space
No, those are still the same dots flood-filled on the first level. Some of them just get removed when the outlines are breached. You are too stupid to breathe. How did BOT become the dumbest board on this site?

• 2 months ago
Anonymous

>those are still the same dots flood-filled on the first level
Then you did it wrong, because there's no water in that section on the first level.

• 2 months ago
Anonymous

>no water in that section on the first level.
Who the frick cares? You can still segment all the possible pools looking from above with the same kind of floodfill I posted earlier. It's just a matter of starting to count their contents when you reach their lowest level and removing them from the list as soon as the outline is breached.

• 2 months ago
Anonymous

>you can do X
>no you can't
>who the frick cares, you can still do Y
Floodfilling throughout the entire 3D space, again, is in direct contrast to what you proposed in

https://i.imgur.com/1bPXjFd.png

Since a bunch of homos (none of whom managed to present a better algorithm) complain that O(number of cells) isn't fast enough, here's a simple improvement: do the flood fill on the bottom level and memorize the outlines of the pools + the number of cells inside the pool. Every time you go up a level, scan the outlines for breaches. If none are found, add the cell number for that pool to the volume, otherwise delete the entry for that pool. Keep going until you run out of pools or reach the top.

, and isn't particularly efficient.
Go ahead and give some moronic circular nonsense excuse about how your proposal wasn't actually moronic and didn't mean what you said though. This seems really important to you so I'll just stop responding so you don't keep looking like a moron in front of your anonymous friends.

• 2 months ago
Anonymous

>Floodfilling throughout the entire 3D space
No, you stupid Black person, you just segment by height using the same kind of O(n) method used here:

https://i.imgur.com/EkEtLqR.png

Here's a moronicly simple O(n) scanline floodfill solution for a single layer:
https://pastebin.com/JBCabqSQ

And here's the basic scanline floodfill I started from:
https://pastebin.com/t8xXcK5z

It can be made much faster by using a more sophisticated scanline floodfill but that's besides the point with a mongoloid like you who can't even grasp the simple version.

. You do this once for the 2D matrix. You don't do this on every level. Once you segment it, you just figure out which segments to count based on the height and the segment outlines with the height substracted to see if there's a spill on a given level, gradually removing segments as you go up.

• 2 months ago
Anonymous

YOU DON'T EVEN KNOW WHAT THE TERMS SCANLINE OR FLOODFILL EVEN MEANS. STOP BEING FRICKING moronic. What the frick is the """LINE""" you are talking about in a fricking graph.

You both are correct but you're too autistic to communicate what you're saying to each other, it's really funny to watch

• 2 months ago
Anonymous

That's not floodfill lmao that is literally one algo only useful for this task and nothing else. You think you are smarter but you just encountered this exact problem before and think you are smart. You aren't

• 2 months ago
Anonymous

Layer by layer is O(N*H) rather than O(NlogN) which is better

• 2 months ago
Anonymous

Post a working algorithm that does better than being poportional to the number of cells.

35. 2 months ago
Anonymous

Return where?

36. 2 months ago
Anonymous

>You CAN solve this
yeah i played wetrix
you place the heavy block so it spills

37. 2 months ago
Anonymous

I'd probably just load up my recursive maze solver that was an assignment for my intro to programming course 15+ years ago and adapt it to start at every empty cell, and store the path of cells if it can't find a solution to the edge of each layer of the matrix.
Seems okay for a junior programming question but doesn't seem particularly related to AI.

38. 2 months ago
Anonymous

I just did the 1d version so probably yeah

39. 2 months ago
Anonymous

pretty cool problem. I don't think I would come up with a 100% robust solution on the spot. definitely wouldn't be able to code it during the interview. I hope you did well anon.
t. senior SWE, not in OpenAI

• 2 months ago
Anonymous

Do they even expect you to code something fully during an interview *this* complicated? I could tell them my general idea, but frick writing it correctly under pressure, not to mention I make 90% of my breakthroughs in analytical problems when I take a break in between to shit or piss.

• 2 months ago
Anonymous

yes, you're supposed to study

• 2 months ago
Anonymous

>Do they even expect you to code something fully during an interview *this* complicated?
>*this* complicated
Holy shit, no wonder the SWE field is fricking dying.

• 2 months ago
Anonymous

Im not even a programmer and I solved it.
I had the idea instantly but it takes some time to write it properly that is all.

40. 2 months ago
Anonymous

This was a fun problem, where can I find more problems like this?

Here is my solution in python
https://github.com/iasonq/block_water

Basically you just fill all attaching 0s with a value and check if it spills to the borders.
If not you add the amount to the total volume.

As for the height, I just reduce all values by one (negatives become 0) and do the same thing again until the entire "level" is flattened.

I dont think I could code it in an interview and I don't think it is very optimized but it solves the problem.
Took me 1-2 hrs of unconcentrated effort to get it done, also I am not a programmer but a physicist.

• 2 months ago
Anonymous

here is the code:

#Start scanning for a 0
cn = 0
ar = ar0.copy()
x, y = np.shape(ar)
iter = 0
tvol = 0

while np.any(ar != 0):
iter +=1
for i in range(1, x-1):
for j in range(1, y-1):
#If a zero is detected then initiate flood fill, which replaces all bordering 0s with a different number, e.g 11
if ar[i, j] == 0:

val.append( iter*(2**i + 10*j) ) #it needs a better unique value generator but it will do for now
ar = flood_fill(ar, i, j, val[cn])

check, vol = calc(ar, val[cn])
if check == False:
tvol += vol
cn += 1
print(ar)
ar = rlevel(ar0, iter)
####functions used
import numpy as np
from itertools import product as iters

#
def flood_fill(ar, i ,j, val):
ar[i, j] = val
ar = fill(ar, i, j, val)
return ar
#
def fill(ar, i, j, val):
for k, l in iters(range(-1, 2), repeat=2):
if np.abs(k) + np.abs(l) != 2 and wbc(ar, i + k , j + l):
if ar[i+k, j+l] == 0:
ar[i+k, j+l] = val
ar = fill(ar, i+k, j+l, val)
return ar

#within border check
def wbc(ar, i, j):
flag = False
size = np.shape(ar)
if (-1 < i < 6 ) and ( -1 < j < 6):
flag = True
return flag

#on border check
def obc(ar, i, j):
flag = False
size = np.shape(ar)
if ( i == 0 ) or ( i == size[0] - 1):
if ( j == 0 ) or ( j == size[1] - 1):
flag = True
return flag

#Calculate the volume and if it spills out
def calc(ar, val):
flag = False
s = np.shape(ar)
vol = 0
for i in range(0, s[0]):
for j in range(0, s[1]):
if ar[i, j] == val:
vol +=1
if obc(ar, i, j):
flag = True
return flag, vol

#Reduce level
def rlevel(ar_in, level):
arr = ar_in - level
arr[ arr < 0] = 0
return arr

41. 2 months ago
Anonymous

>Given a 2-dimensional array where each nested array represents a row of blocks and each item in the array represents the number of stacked blocks
I don't even know what this means lmao, thank god the cybersecurity industry lets morons like me in

42. 2 months ago
Anonymous

If I'm interpreting this correctly, you'd want to run a 3x3 kernel over the 2d array that ignores corners as well as the center, and minimizes the middle edges. If the center is empty, you then add the resulting height and sum these. Just spitballing though

• 2 months ago
Anonymous

Not if the center is empty, you find the difference between the minimum wall height and the center, and clamp that to >= 0

• 2 months ago
Anonymous

Not if the center is empty, you find the difference between the minimum wall height and the center, and clamp that to >= 0

Mine only works for 1x1 holes, one sec

43. 2 months ago
Anonymous

I don't know what array is so probably not

44. 2 months ago
Anonymous

havent done cp a long time, get ready homosexuals

45. 2 months ago
Anonymous

For each cube go up (y axis) until you hit something, then travel to the right (x axis) one and try going up again. If you hit to the right, go down one then go right one then try going up.
Always test what's below you, and if its open then go down (z axis) and test that entire area before returning to the higher level.
If the entire down level area is fully contained, add it to [water] set.
If you try to go down and hit a block, go left, try again.
If you try to go left and can't go up.
If you hit a border, then every empty tile you traversed on your current level or higher gets added to [border] and won't be checked again.
If you get back to the start then every empty tile you traversed gets added to [water] and won't be checked again.
If your search ever encounters a cube from [water] when it goes down (z axis) then it considers that sufficient and won't recheck.
Do this for each cube. When done count [water]

"Chatgpt make me a FORTRAN script that does the above"
Ez
Ps I enjoy building your data centers. Real Cadillac jobs, much OT, big bucks, thanks nerds, merry Christmas.

• 2 months ago
Anonymous

In retrospect this will never work and I'll stick to bending pipes

46. 2 months ago
Anonymous

Got it. Implementation is probably inefficient but whatever
https://pastebin.com/gpX0i3c9

• 2 months ago
Anonymous

it's not super clear from OP that this is possible but it doesn't pass for case [[3,3,3,3,3],[3,2,2,2,3],[3,2,1,2,3],[3,2,2,2,3],[3,3,3,3,3]] where we are catching rainwater not on level 0 but on levels 1 and 2

• 2 months ago
Anonymous

Good catch, weird.

• 2 months ago
Anonymous

https://i.imgur.com/z5W1hCd.png

it's not super clear from OP that this is possible but it doesn't pass for case [[3,3,3,3,3],[3,2,2,2,3],[3,2,1,2,3],[3,2,2,2,3],[3,3,3,3,3]] where we are catching rainwater not on level 0 but on levels 1 and 2

https://i.imgur.com/U71loON.png

Good catch, weird.

Seemingly fixed it with this change

47. 2 months ago
Anonymous

here you go
https://pastebin.com/T5622i6J

48. 2 months ago
Anonymous

>Example for babbies
I hope interviewers at OpenAI can at least spell, not falling for the bait

• 2 months ago
Anonymous

Back to r*ddit

49. 2 months ago
Anonymous

>everybody was posting incorrect suboptimal solutions for hours, then one person posted a correct solution generated by AI, and suddenly everyone knows to use a priority queue

50. 2 months ago
Anonymous

Not that hard. Either you can try going big brain mode and solve it in some complicated way, or just go simple. Do it for a 2d array first, finding bordered in regions, filling in enclosed areas pixel by pixel (to account for stuff within the 'lakes'). Then add a recursive function that generates a map of what squares can theoretically support water on top, and run your 2d code again while only filling in the surft that your support map allows. Not the most efficient solution, but easy to understand and simple. Can still be improved if needed.

• 2 months ago
Anonymous

>finding bordered in regions
Does not count unless you explain how. You can't handwave the only hard part of your solution.

51. 2 months ago
Anonymous

Of course I can do it.

What I can't do is use grueling months of leetcode bullshit to just drag up the graph theorem to do it efficiently from memory.

52. 2 months ago
Anonymous

come up with a perfect answer, they're gonna know you cheated OP

53. 2 months ago
Anonymous

> 0 0 2 0 2 0 0
> 0 2 1 2 1 2 0
> 1 0 2 0 2 0 1
> 1 0 2 2 2 0 1
> 0 1 0 0 0 1 0
So, we go by layers like this
> 0 0 1 0 1 0 0 --- 0 0 1 0 1 0 0
> 0 1 1 1 1 1 1 --- 0 1 0 1 0 1 0
> 1 0 1 0 1 0 1 --- 0 0 1 0 1 0 0
> 1 0 1 1 1 0 1 --- 0 0 1 1 1 0 0
> 0 1 0 0 0 1 0 --- 0 0 0 0 0 0 0
> (height 1) ------- (height 2)
And then we see the shapes of lakes
> 0 1 0 --- 0 1 0
> 1 0 1 --- 1 0 1
> 1 0 1 --- 0 1 0
> 0 1 0 ---
There must be formulas which allow to:
a. Detect the 1's connected to a shape.
b. Calculate the area of an arbitrary-sided shape.
t. discouraged anon

54. 2 months ago
Anonymous

>pee so I make sure muy bladder is empty
>drink the water
>pee on bottles until I get the exact measure
>take note
>return the water to it's original recipient

55. 2 months ago
Anonymous

im fairly confident id be able to write down a correct algorithm to solve this if i had to for a job (interview).
but i could never be arsed to solve it for a BOT OP, and then fight over the validity of my solution.
i admire you tenacity, i guess.

56. 2 months ago
Anonymous

One thing that might invalidate a lot of 'correct answers' and is not given:

If a theoretically fillable void has something covering it (n layers above), does it get filled or not? If it's 'rain collection' then something like

U

U
Floor

should only account for 'one fill' as the 'rain' cannot reach the bottom 'pool'.

In that case, the only real solution is to 'simulate the rain', dwarf fortress style.

• 2 months ago
Anonymous

i just realized, it's simpler than thought, it's not even 'actual 3d', it's just 2d with heights. Blocks need to be right on top of other blocks.

57. 2 months ago
Anonymous

Kind of funny that you guys are still shitflinging about this when it was solved almost a full day ago ITT

58. 2 months ago
Anonymous

Just tell the interviewer if he doesn't give you the job you'll kill him and his entire family.

59. 2 months ago
Anonymous

the problem is quite easy tbh but the wording is just plain incorrect,its like some moron cs zoomer tried to larp as a math professor ,
>2d array has nested arrays?
how exactly do you mean Black person
>nested arrays are rows but also each item is stacks
I could find more but i wasring my time

60. 2 months ago
Anonymous

I'm reading all the replies and no wonder tech went to literal shit lol. For a decent company position they ask you to do shit like this that pajeets from India learn by heart how to solve and ask 0 questions regarding the actual position and the job you will be doing. This is more of an interview question for a game dev, but even this is unrealistic. You need to know basic algorithms and CS paradigm and not study for 100s of hours learning algorithms that you will never use at your job, this is just useless.

Make a hobby project, something actually useful, not some boring iterations over same fricking arrays of numbers for the 1000th time in order to solve some imaginary problem.

People and companies in tech have literally become insane, so it's not surprising that software is going to shit by the speed of light - imagine if you were a heart surgeon and you went to an interview for a heart surgeon job at a private clinic and they asked you if you can make some medicine by scratch or how to cure some liver disease lol. What's even worse is that there are people who submit to these humiliation rituals and just so they have a chance to earn a high salary in a high cost area, without having any free time.

• 2 months ago
Anonymous

I just wanted to add also that people who solve this type of imaginary problems can't even manage simple memory allocation and pointers and then complain how others are stupid when they cannot solve some random Leetcode problem lol. This is why we have languages like Rust and why people now make software that runs extremely slow on newest hardware, probably slower than software 10-15 years ago.

• 2 months ago
Anonymous

BOT is mostly shit so it shouldn't be that much of a surprise. I suppose I'm fine with these kinds of questions because I like good challenges but the people doing it for interviews and crap are just ridiculous. If I were hiring I'd rather them display knowledge of "slightly" esoteric but important concepts like Cs side-effects and implementation-defined behavior since most C resources actually IGNORE these to an extent. Seriously, if you learn C through K&R or through Beej's web guide you're fricked.

• 2 months ago
Anonymous

This, the technological details, programming language details and implementation, network protocols, OS terms, multithreading, security etcetc. are much more important than some random Leetcode algorithm. There's actually a lot of things that you need to know to be a good programmer and learning Leetcode algorithms/assignments is not one of these things. As a beginner working for a large company should be the least of your concerns, you should start humble and learn interesting things - leave jobs where you don't learn anything useful. If you don't love your job or what you do and do it only for the money how will you code for the next 40-50 years until retirement?

61. 2 months ago
Anonymous

can't be fricked to do proper code

- find [highest value] in the 2D input array
- create 3D L x W x [highest value] array to mark visited nodes
- create "visited" counter
- for (int layer = 1; layer <= [highest value]; layer++):
1) automatically mark all edge edge nodes as visited in the 3D array, since the rules implicate that no edge nodes can contain water; increment "visited" counter accordingly
2) flood fill algorithm from empty edge nodes to adjacent nodes, marking empty and block nodes as visited and incrementing "visited" counter along the way
2a) if [adjacent 2D array index value] < layer (empty node), increment "visited" and traverse to [adjacent 2D array index]
2b) if [adjacent 2D array index value] >= layer (block node), increment "visited" but do not traverse
3) int water = (L x W x [highest value]) - "visited"
- return "water"

• 2 months ago
Anonymous

2a2) if [adjacent 2D array index value] < layer (empty node) but corresponding 3D array index is marked as visited, do not increment "visited" and do not traverse
2b2) if [adjacent 2D array index value] >= layer (block node) but corresponding 3D array index is marked as visited, do not increment "visited"

62. 2 months ago
Anonymous

>fill equally sized array with all -1
>add all the cells from the first one to the new array
>potential waters are now -1 while walls are =< 0
>flood fill from every edge piece, incrementing every cell while treating =< 0 as walls
>if there are no positive numbers left, sum up all the numbers and invert the sign
>otherwise recurse

63. 2 months ago
Anonymous

Convert the input into a 3d grid, with each block marked as "filled" or "unknown".
Do a modified flood fill on each layer for empty blocks, where the flood fill will only check blocks surrounding and above (not below). The boundary blocks must be empty. Afterwards, any block that is still unknown will have water.
Here's part of a solution in go, there's some extra shit from printing that I've left in. Obviously could have stack overflow with large inputs because of the recursive calls, but that's a trivial change to an explicit stack.
const W = 6
const H = 7
const D = 2

var grid = [D][W][H]int{}

const (
unknown = 0
block = 1
empty = -1
)

func processLayer(h int) {
// boundary must be empty
for x := 0; x < W; x++ {
floodFill(h, x, 0, "B")
floodFill(h, x, H-1, "B")
}
for y := 0; y < H; y++ {
floodFill(h, 0, y, "B")
floodFill(h, W-1, y, "B")
}
}

func floodFill(h, x, y int, dir string) {
if x < 0 || x >= W || y < 0 || y >= H || h >= D {
return
}
fmt.Printf("fill %d,%d,%dn", h, x, y)

if grid[h][x][y] == unknown {
grid[h][x][y] = empty

printGridUpdate(h, x, y, dir)
time.Sleep(time.Millisecond * 100)

floodFill(h, x-1, y, "<")
floodFill(h, x+1, y, ">")
floodFill(h, x, y-1, "^")
floodFill(h, x, y+1, "V")
floodFill(h+1, x, y, "O")
}
}

• 2 months ago
Anonymous

Meh, your solution is a bit inefficient. Here's my better solution in Go, I left out some details but you can get the general idea of my method:
func solve() {
catchRainwater();
}

• 2 months ago
Anonymous
• 2 months ago
Anonymous

You don't need to translate it into 3d. You just need to flood fill via BFS in one layer and multiply it by the minimum number greater than 0 touching the flood filled point. This problem is physically indistinguishable from the same problem with only 1 layer other than that you need to keep track of the depth of the pool in each segment.

64. 2 months ago
Anonymous

5 water blox in pic: means volum is 5x5x5 proven water blox
why this so hard for you morons?

65. 2 months ago
Anonymous

i don't even want to explain this, too much leet for me.

66. 2 months ago
Anonymous

At OpenAI we're looking for rainwater harvesters. Not because we collect rainwater but because we don't know how to ask for a short algorithm used in the job.