I am very curious if it is actually simple or not. I've had some "easy" interview questions that are pure CS trivia. But this and your other comments make it sound practical... can you just post it?
Given a 10x10 array filled with numbers. For a given (x,y) starting point, search the 3x3 grid starting with that point as its upper left corner and indicate if it contains a particular number. Ignore error conditions such as running off the edge of the array.
I estimate that 80% of candidates could not accomplish this in an hour. 50% of them could not even get out of the gate.
array data = (array(int))random_string(100)/10;
int x = random(10); int y = random(10);
int seek = random(255);
int findgrid(array data, int x, int y, int seek){
for(int i=0;i<=2;i++){
for(int j=0;j<=2;j++){
write("%d:%d\n", data[x+i][y+j], data[x+i][y+j]==seek);
if(data[x+i][y+j]==seek){ return true; }
}
}
}
took me 15 minutes, and only because i am tired and took a break in between.
i can't imagine anyone calling themselves programmer not being able to do that.
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.
> 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)
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.
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.
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.
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.
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.
And that reminded me that some people were nervous about doing the nested loop solution so asked if they could "brute force" it and we would accept that. Interview stress is a thing after all.
I'm intrigued by the slice/map solution. It would have been perfectly acceptable if you could explain what the functions did. In fact, it would have led to very probing conversations: my usual interview partner and me had a deep interest in elegant solutions.
80% is about what I remember. Haven't given that test since 2015 when I left that job. But yes, your solution would have been acceptable: it didn't even need to compile, or be bug free, just show a clear logical path to the solution.
The point is that the vast majority of candidates, including some with Master's degrees in CS, could not write even a pseudocode solution to this problem. It got so bad that I started doing a verbal fizzbuzz test during the phone screen so we didn't waste so much time.
I wouldn't get too ahead of yourself since this looks like C++ but won't work unless you make a special array class that returns pointers to the start of lines from the operator[] function. Even then you would need to switch the x and the y so that the y comes first.
You might say it's pseudo code but one of the original comments was talking about the low numbers of people who could actually get something to compile and solve a problem.
it's neither c++ nor is it pseudo code. but this language has been designed to closely follow C syntax, so the confusion is not surprising. in fact originally the language did have C in its name. i am going to leave the actual answer at what language this is open to allow more people to keep guessing ;-)
you are right about x and y. i was really tired :o
but it runs (at least as long as there is no overflow). here is a sample output:
> findgrid(data, y, x, seek); // there, fixed the x/y problem ;-)
160:0
165:0
65:0
174:0
23:0
253:0
229:0
130:1
(1) Result: 1
oh, and since we are talking about interview experiences. at one job during the interview i was allowed to provide coding solutions in this language, even though the job was about python.
Out of curiosity, here's a bit of C# to do it. This randomly populates a 10x10 grid then looks for a random target in a randomly located 3x3 sub-grid.
As per the question I've ignored error conditions, but using the simple expedient in this case of positioning the 3x3's top left within the first 8x8 not the full 10x10.
Example output is underneath.
// Make and fill the grid.
var r = new Random();
var grid = new int[10, 10];
for (var y = 0; y < 10; y++)
for (var x = 0; x < 10; x++)
grid[x, y] = r.Next(10);
// Draw the grid for reference.
Console.WriteLine();
Console.WriteLine(" 0 1 2 3 4 5 6 7 8 9");
Console.WriteLine();
for (var y = 0; y < 10; y++)
{
Console.Write($"{y} ");
for (var x = 0; x < 10; x++)
Console.Write(grid[x, y] + " ");
Console.WriteLine();
}
Console.WriteLine();
// Random starting point and target.
var tlx = r.Next(8);
var tly = r.Next(8);
var target = r.Next(10);
// Extract the 3x3 sub-grid and "[ ]" any matches.
Console.WriteLine($"Looking for {target} in 3x3 grid at {tlx},{tly}");
Console.WriteLine();
for (var dy = 0; dy < 3; dy++)
{
for (var dx = 0; dx < 3; dx++)
{
var ax = tlx + dx;
var ay = tly + dy;
var v = grid[ax, ay];
if (v == target) Console.Write($"[{v}]");
else Console.Write($" {v} ");
}
Console.WriteLine();
}
Console.WriteLine();
As others have said elsewhere this could use a one-dimensional array but as we know upfront what the constraints are I've gone for the clarity of the two-dimensional. This is said to be the very first mistake everyone makes in graphics programming - but nothing in the question says it is for use in graphics, so being an interview question I went for clarity.
Similarly there's the possible use of a ternary, less memory allocation, and tighter code, but again in this situation I'd go for readability.
There may also be edge cases not covered; this was a 10 minute hack (as it looked fun) and isn't exhaustively tested.
