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

    Do your own homework Deshawn.

  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

          >no reply
          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

        Any links?
        [...]
        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

      Any links?

      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
        >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?

    • 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.
    The sum is your result

    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

      and your solution is shit

      • 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

          I already tried that here

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

              • 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

                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?

              • 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
      My bad

    • 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
      My bad

      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
    t. dumb tradesman
    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

      >Anon doesn't know about "babbies"
      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

    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")
    }
    }

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

Your email address will not be published. Required fields are marked *