You CAN solve this, right?
I got asked this question during the interview for my junior SWE position at OpenAI.
 Thalidomide Vintage Ad Shirt $22.14 |
 CRIME Shirt $21.68 |
Thalidomide Vintage Ad Shirt $22.14 |
You CAN solve this, right? I got asked this question during the interview for my junior SWE position at OpenAI.
Do your own homework Deshawn.
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?
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??!
>What kind of mesh do i use captain homosexual??!
i'm saving this to use out of context
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
>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.
>This won't work.
Why not?
>no reply
classic
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.
Wrong, try again.
For the problem as stated, it is correct.
Verification not even required
>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?
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.
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.
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.
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
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)
oh, my bad, you're right, it's the 3d one, still a moderately common question
https://leetcode.com/problems/trapping-rain-water-ii/
I'm reading the solution, and I still couldn't even make sense of it. Reminds me of my university days lol.
Gonna kms.
Any links?
Isn't this just the classic question about how to implement bucket tool in Paint?
https://en.wikipedia.org/wiki/Flood_fill
>go slice by slice
>floodfill the empty spaces
>count the floodfilled pixes
Yeah, this is boring, I'm not coding it.
Oh, and ignore the floodfill if it touches the borders.
Lmao. Why larp? What do you even mean by "floodfill the empty spaces"?
>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.
Computation time limit/memory exceeded 🙂
Sorry anon, we'll be moving forward with another candidate.
>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.
>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
>mongoloidal fizzbuzzing wagecretin can't implement a floodifll properly
Like pottery.
The point is you'd have to execute a flood fill potentially for every 4th block which is inefficient as frick you brainlet
Jesus frick, wagedrones are legit mentally challenged. Competence crisis is already here.
>My code is too inefficient
>It's the others fault
Ok brainlet
You can't solve a kiddie problem and your nonsensical schizophrenic babble simply doesn't matter.
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.
>psychotic wagegolem keeps spewing GPT-2 tier babble
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.
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.
>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.
First day?
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;
}
I don't see the height of the walls accounted for.
it's there. we don't count the height since we just do it by slice. wall > layer
Since I don't understand your code, I'll take your word. You're hired.
t. hr
>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
hr doesn't do technical interviews
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.
that's probably a pre technical interview phone screen not the real interview
You'd be surprised how many people that filters.
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
Its a man thoughbeit
>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.
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.
If your algorithm isn't a floodfill it won't work. Yours isn't a floodfill.
Even I can tell both of you are spouting bullshit.
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?
You might be moronic.
According to your algo, pic rel is filled
>If x, y indexes (of neighbors, dipshits) get beyond the limits of the array, just drop counting water and go next element
>according to your algorithm
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?
[[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.
https://leetcode.com/problems/trapping-rain-water-ii/
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
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
>https://leetcode.com/problems/trapping-rain-water-ii/
I got filtered
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.
The sum is your result
Can't be arsed to write code
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)
[[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]]
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
Oh look, the first anon who proposed an actual solution
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
I don't like the idea of iterating over every square for this and definitely not multiple times.
You don't need to iterate over every square, only those within [1, size-2] borders.
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.
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.
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
Learn logic
Not Maths
Dont know, dont care , dont need to know. I work in management now. Frick you nerds
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.
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.
[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
If there are 3 zeros in the left-bottom corner, one can always "move" array both left and down.
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.
>tfw I work in tech and I'm too much of a brainlet to solve this
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.
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
leetcodeBlack folk tongue my anus
>t. 200k senior dev, didn't need to answer bullshit CS questions in my interview.
It's just a fun puzzle, this obviously isn't real programming
>for my junior SWE position at OpenAI.
Ah so you enjoy taking it up the ass too?
what if this
It's a heightmap, so blocks cant have open spaces beneath them
What? Yes they can
>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
Oh, you're right
oh. kinda disappointing
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
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
And these holes could lead to other lakes.... Yeah no floating blocks makes the whole thing 30x more complex
im
and I did intuit the solution in less than a second
and your solution is shit
how is it shit
it's O(n*m) time and memory. You want O(n) time and memory
what is n moron
n is the number of positions in the array
m is the largest height value in the array
you need to do n*m if you don't assume stacks can have gaps in them
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
Stop memeing brainlet.
Your solution is inefficient though, that's true. You can achieve O(MNlog(MN)) time complexity and O(MN) space complexity
>glub glub glub hurr muh O(n)
This is (You) gargling on Black person cum.
Of course. It's 7
Ah, it's one of these threads.
You should just leave the interview.
(Me)
(The code works fine)
Get fricked
>mixtral 7x8b
can you do that same example with gtp3.5 so we can compare?
I don't subscribe to ~~*OpenAI*~~ so no.
Now ask it to do for a 3d array where 1 is a block kek
Any AI can copy-paste solutions to leetcode problems
>le goalpost mové
I understand how it works and the idea, but I can't imagine myself coming up with that. is it over for me?
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
I already tried that here
This so obviously doesn't work
That would be because it's wrong
Consider
0, 1, 0
1, 0, 0,
0, 0, 0
This would return 1...
Nevermind, I suck cawks
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
Yeah, I saw. That's a great solution.
Otsu's method. Done. Frick off Code monkeys.
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
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.
return 7;
>softwaregays waste a significant part of their life trying to one up other losers on meaningless toy problems
certified autism
Actually this. In a working environment you'd be able to solve this shit trivially because you'd know everything feeding into the problem.
This would actually be challenging if floating blocks were allowed. Imagine a U shaped pipe where one leg is shorter than the other
chat gippytee is so smart, humies could never have come up with this shit
trick question, no solution possible
>I cannot think of a solution therefore no solution is possible
Correct
Why am I being asked complicated math shit to do webdev?
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.
So it's just gatekeeping and credentialism all the way down then?
Yes. Keeping out people who refer to "demanding basic competency" as "gatekeeping and credentialism" is an important part of keeping any business afloat.
as soon as you need a sorted queue it is no longer basic competency, but an advanced problem
You are the kind of person we're trying to keep out
>hey guize can I have 6 figs SWE salary?
>what's a heap, lol?
>I am a leetcode pajeet therefore I am a good coder
Lmao.
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?
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
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
Again twisting words, homosexual? There is a reason why nobody ITT has solved it
Dude, chill out. What's your deal? Could you afford therapy or professional help?
>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 >>>
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
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.
>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.
Flood fill doesn't account for different heights moron.
You obviously do it layer by layer, tardolini, which all the people who said to use floodfill mentioned.
Which is extremely inefficient and has no reason to use a priority queue moron.
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.
moron. JUST FLOODFILL HURR DURR YOU DON'T UNDERSTAND HOW IT WORKS.
It's not my fault that you don't understand how a scanline floodfill works, you mongoloidal animal. lol
>hurr durr just run floodfill for each different height value that's totally the correct solution!
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.
moron. If you are using bfs with a priority queue at any point that's not a fricking flood fill.
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.
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".
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.
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.
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.
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.
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.
You are a moron for clearly doubling down a solution that doesn't work.
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).
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.
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
>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?
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.
>single layer
>O(n) for a two dimensional array
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.
>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)
You will never have basic human sentience. Bottom line is that the runtime is proportional to the number of cells.
yeah bro what if i gave you
1 1 1
1 748383637 1
1 1 1
your program would just give up
See
When you post something better than O(cell num) we'll talk.
That either loops infinitely or is so slow that I ran out of patience. You fail.
Your code literally just doesn't work. Next.
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
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
ok ill just mark you down as a fail then thanks for coming
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
I told you the heap solution is correct. I've already passed gayman interviews and have a job but feel free to seethe
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.
ok
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"
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.
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.
>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.
>This is psychotic babble
Your lack of reading comprehension isn't my problem
>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.
>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.
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.
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.
deny*
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.
Provide a fully specified input you think it doesn't work for in your next post.
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]]
Here's your matrix:
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?
>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.
>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.
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?
>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.
>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.
>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
, 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.
>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:
. 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.
You both are correct but you're too autistic to communicate what you're saying to each other, it's really funny to watch
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
Layer by layer is O(N*H) rather than O(NlogN) which is better
Post a working algorithm that does better than being poportional to the number of cells.
Return where?
>You CAN solve this
yeah i played wetrix
you place the heavy block so it spills
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.
I just did the 1d version so probably yeah
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
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.
yes, you're supposed to study
>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.
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.
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.
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
>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
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
Not if the center is empty, you find the difference between the minimum wall height and the center, and clamp that to >= 0
My bad
Mine only works for 1x1 holes, one sec
I don't know what array is so probably not
havent done cp a long time, get ready homosexuals
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
t. dumb tradesman
Ps I enjoy building your data centers. Real Cadillac jobs, much OT, big bucks, thanks nerds, merry Christmas.
In retrospect this will never work and I'll stick to bending pipes
Got it. Implementation is probably inefficient but whatever
https://pastebin.com/gpX0i3c9
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
Good catch, weird.
Seemingly fixed it with this change
here you go
https://pastebin.com/T5622i6J
>Example for babbies
I hope interviewers at OpenAI can at least spell, not falling for the bait
>Anon doesn't know about "babbies"
Back to r*ddit
>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
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.
>finding bordered in regions
Does not count unless you explain how. You can't handwave the only hard part of your solution.
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.
come up with a perfect answer, they're gonna know you cheated OP
> 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
>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
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.
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.
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.
Kind of funny that you guys are still shitflinging about this when it was solved almost a full day ago ITT
Just tell the interviewer if he doesn't give you the job you'll kill him and his entire family.
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
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.
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.
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.
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?
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"
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"
>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
You morons are still arguing about this? Flood fill the empty blocks, not the water.
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")
}
}
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();
}
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.
5 water blox in pic: means volum is 5x5x5 proven water blox
why this so hard for you morons?
i don't even want to explain this, too much leet for me.
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.