3 ms·

In your example the first dimension returns a pointer to a row, then the next is the offset into that row so your lookup needs to be grid[y][x] Also you seem t

In your example the first dimension returns a pointer to a row, then the next is the offset into that row so your lookup needs to be grid[y][x] Also you seem to be bounds checking for 0s, but to do that in the first dimension you need null pointers to pad your row selection and a second set of 0s at the end of your rows. It's interesting that both you and the person you replied to used arrays of arrays which is the very first mistake everyone makes in graphics programming when trying to make a 2D array or and image. A much better way is to have a single contiguous array and use buf[y*width + x] to lookup into the one dimension buffer.

bubblyworld 2y ago
It's only much better if you care about cache misses, right? I think for a 10x10 array we can safely ignore performance concerns.
- CyberDildonics 2y ago
  It's only much better if you care about cache misses, right? No, not at all. There are cache misses and simplicity, but think about when an 1k image is on the heap. You have to allocate a buffer of pointers for each row then you have do a thousand individual heap allocations to get all your rows. Now think about an image with rgba channels. Technically this is a 3d image with one short dimension. Are you going to allocate a buffer of a thousand pointers, then off of each one allocate a buffer of a thousand more pointers so that you can ultimately do another 1 million heap allocations, all 16 bytes for each rgba pixel? There is no upside and all downsides, which is why it is never ultimately done this way, though it is an almost universal mistake when people do multi-dimensional arrays for the first time.
  - bubblyworld 2y ago
    Yeah, I hear you, my point was just that we know the constraints up front and it doesn't matter in this case. Sometimes it's convenient to not have to pass around the length and do one or more multiplies with every index.
6510 2y ago
> In your example the first dimension returns a pointer to a row, then the next is the offset into that row so your lookup needs to be grid[y][x] Correct, it should be [y][x] indeed. I would have spotted that had I bothered to. > Also you seem to be bounds checking for 0s, but to do that in the first dimension you need null pointers to pad your row selection and a second set of 0s at the end of your rows. Not sure which is the first dimension but for an array of 10 if(arr[100]) returns false. Anything behind the && is ignored. Looking at this again the really funny part is that it doesn't work if num = 0 since if(arr[100]) returns false if there is a zero at position 100. > It's interesting that both you and the person you replied to used arrays of arrays which is the very first mistake everyone makes... I copy that part from their solution but probably would have myself. I've been found out not being a graphics programmer. The experiment was a success. Of course I've made all these mistakes to test if anyone was paying attention. (I always say that)
- CyberDildonics 2y ago
  Not sure which is the first dimension but for an array of 10 if(arr[100]) returns false This is taking the first pointer and offsetting it by the length of 100 pointers. There are only 10 pointers in the array so it is going into other data. If your pointers are 64 bit and your numbers are 32 bit, even if that is referencing the memory mapped data of the sub arrays it is going twice as far as the end of the array and returning 0 purely by chance of some other memory you're dealing with by accident. A better way would be to keep things simple and bounds check that x is less than width and y is less than height while using the single buffer method. The point here isn't to be too harsh with criticism, it's just that it's easy to see something as more trivial than it really is.
  - 6510 2y ago
    Thats fun too. function foo(x,y,num){ for(i=y; i<y+3 && i<10; i++){ for(w=x; w<x+3 && w<10; w++){ if(grid[i*10+w] == num) return true } } return false; } https://jsfiddle.net/gaby_de_wilde/ycx159kg/1/ https://jsfiddle.net/gaby_de_wilde/ycx159kg/1/
em-bee 2y ago
the very first mistake everyone makes in graphics programming when trying to make a 2D array or and image but that is an additional condition that was not in the original task. there was no mention of image programming. since we are discussing interview examples here, leaving out such a detail and then calling people out on an error caused only by missing that would be considered deeply unfair towards the candidate. my point is, that our choice in the solution is not interesting at all because it was part of the task. you are proposing a slightly different task, which is of course interesting too.
- deleted 2y ago
  [deleted]
- CyberDildonics 2y ago
  you are proposing a slightly different task I'm not proposing a different task, I'm pointing out that you both thought it was trivial and both ended up doing arrays of arrays then having something that wouldn't work because of the complexities of that. You're right that someone could solve the problem with arrays of arrays, but no one did. I think the problem is mostly trivial too, but before doing graphics programming and solving almost identical problems multiple times, I would have made most of the same mistakes.

bubblyworld 2y ago

It's only much better if you care about cache misses, right? I think for a 10x10 array we can safely ignore performance concerns.

CyberDildonics 2y ago
It's only much better if you care about cache misses, right? No, not at all. There are cache misses and simplicity, but think about when an 1k image is on the heap. You have to allocate a buffer of pointers for each row then you have do a thousand individual heap allocations to get all your rows. Now think about an image with rgba channels. Technically this is a 3d image with one short dimension. Are you going to allocate a buffer of a thousand pointers, then off of each one allocate a buffer of a thousand more pointers so that you can ultimately do another 1 million heap allocations, all 16 bytes for each rgba pixel? There is no upside and all downsides, which is why it is never ultimately done this way, though it is an almost universal mistake when people do multi-dimensional arrays for the first time.
- bubblyworld 2y ago
  Yeah, I hear you, my point was just that we know the constraints up front and it doesn't matter in this case. Sometimes it's convenient to not have to pass around the length and do one or more multiplies with every index.

6510 2y ago

> In your example the first dimension returns a pointer to a row, then the next is the offset into that row so your lookup needs to be grid[y][x] Correct, it should be [y][x] indeed. I would have spotted that had I bothered to. > Also you seem to be bounds checking for 0s, but to do that in the first dimension you need null pointers to pad your row selection and a second set of 0s at the end of your rows. Not sure which is the first dimension but for an array of 10 if(arr[100]) returns false. Anything behind the && is ignored. Looking at this again the really funny part is that it doesn't work if num = 0 since if(arr[100]) returns false if there is a zero at position 100. > It's interesting that both you and the person you replied to used arrays of arrays which is the very first mistake everyone makes... I copy that part from their solution but probably would have myself. I've been found out not being a graphics programmer. The experiment was a success. Of course I've made all these mistakes to test if anyone was paying attention. (I always say that)

CyberDildonics 2y ago
Not sure which is the first dimension but for an array of 10 if(arr[100]) returns false This is taking the first pointer and offsetting it by the length of 100 pointers. There are only 10 pointers in the array so it is going into other data. If your pointers are 64 bit and your numbers are 32 bit, even if that is referencing the memory mapped data of the sub arrays it is going twice as far as the end of the array and returning 0 purely by chance of some other memory you're dealing with by accident. A better way would be to keep things simple and bounds check that x is less than width and y is less than height while using the single buffer method. The point here isn't to be too harsh with criticism, it's just that it's easy to see something as more trivial than it really is.
- 6510 2y ago
  Thats fun too. function foo(x,y,num){ for(i=y; i<y+3 && i<10; i++){ for(w=x; w<x+3 && w<10; w++){ if(grid[i*10+w] == num) return true } } return false; } https://jsfiddle.net/gaby_de_wilde/ycx159kg/1/ https://jsfiddle.net/gaby_de_wilde/ycx159kg/1/

em-bee 2y ago

the very first mistake everyone makes in graphics programming when trying to make a 2D array or and image but that is an additional condition that was not in the original task. there was no mention of image programming. since we are discussing interview examples here, leaving out such a detail and then calling people out on an error caused only by missing that would be considered deeply unfair towards the candidate. my point is, that our choice in the solution is not interesting at all because it was part of the task. you are proposing a slightly different task, which is of course interesting too.

deleted 2y ago
[deleted]
CyberDildonics 2y ago
you are proposing a slightly different task I'm not proposing a different task, I'm pointing out that you both thought it was trivial and both ended up doing arrays of arrays then having something that wouldn't work because of the complexities of that. You're right that someone could solve the problem with arrays of arrays, but no one did. I think the problem is mostly trivial too, but before doing graphics programming and solving almost identical problems multiple times, I would have made most of the same mistakes.