Define "actually program".
What are you evaluating them on? Leetcode?
What are you evaluating them on? Leetcode?
But it's also then possible to make use of "one step up" by asking people for variations and seeing whether they can talk about tradeoffs (still at a very basic level, but still).
E.g. in a higher level language, if asked to reverse the order of the words you often get variations of split on space, reverse the resulting array, join. In which case you have an opening to ask them if they can do it lower level, in minimal space.
In which case, the "typical" solution becomes to reverse the string in place, then iterate and find the start of each word, and reverse that in place. Both reverse operations need at most two pointers and a temporary, and can be done with the same function if you take in a start and end pointer.
If you have that helper to reverse a given character range in place, reversing the order of the characters within each word without reversing the word order is just the same thing without reversing the whole string first.
One google interviewers ask me a question that starts with “implement google search” and ends with my implementing splitting a paragraph. Of course I failed the interview, but I have to think he has failed me way before we get to write any code.
I'd say about half of the candidates that interview are unfamiliar with the String#substring equivalent of their language. This is for a senior position, and everyone has multiple years of experience on their resume. It's... interesting.
Many people would say those candidates should be failed anyway due to X, Y, Z reasons. But I want to highlight that in those cases, the interviewers should realize they are assessing something else, and not programming skill.
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; }
}
}
}
80%? hard to believe it's that bad.
grid = [
[1, 2, 3, 4, 5, 6, 7, 8, 9, 0],
[1, 2, 3, 4, 5, 6, 7, 8, 9, 0],
[1, 2, 3, 4, 5, 6, 7, 8, 9, 0],
[1, 2, 3, 4, 5, 6, 7, 8, 9, 0],
[1, 2, 3, 4, 5, 6, 7, 8, 9, 0],
[1, 2, 3, 4, 5, 6, 7, 8, 9, 0],
[1, 2, 3, 4, 5, 6, 7, 8, 9, 0],
[1, 2, 3, 4, 5, 6, 7, 8, 9, 0],
[1, 2, 3, 4, 5, 6, 7, 8, 9, 0],
[1, 2, 3, 4, 5, 6, 7, 8, 9, 0]
]
foo = function(x,y,num){
if (grid[x][y] == num) return true;
if (grid[x+1] && grid[x+1][y] == num) return true;
if (grid[x+2] && grid[x+2][y] == num) return true;
if (grid[y+1]){
if (grid[x][y + 1] == num) return true;
if (grid[x+1] && grid[x+1][y+1] == num) return true;
if (grid[x+2] && grid[x+2][y+1] == num) return true;
}
if (grid[y+2]){
if (grid[x][y+2] == num) return true;
if (grid[x+1] && grid[x+1][y+2] == num) return true;
if (grid[x+2] && grid[x+2][y+2] == num) return true;
}
return false;
}
alert(foo(1,2,3));
alert(foo(1,2,30));
https://jsfiddle.net/ycx159kg/
13 min later...
round2 = function(x,y,num){
return grid.slice(x,x+3).map(g=>g.slice(y,y+3)).flat().includes(num);
}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.
grid.slice(x,x+3)
If the second value in slice is larger than the length it slices to the end. It could be a 2x10 or 1x10 but lets pretend it is 3.
.map(g=>g.slice(y,y+3))
.flat()
.includes(num)
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.
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.
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)
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.
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;
}
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.
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.
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.
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
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();
0 1 2 3 4 5 6 7 8 9
0 1 2 5 4 1 8 0 2 8 5
1 4 2 2 5 8 4 4 0 4 8
2 7 1 8 2 5 6 3 6 3 6
3 8 7 3 2 4 6 5 9 6 2
4 6 3 4 2 9 7 4 7 6 1
5 1 4 2 3 8 3 2 4 3 3
6 0 6 6 5 1 4 7 3 4 9
7 2 0 6 9 9 9 3 9 1 7
8 1 6 5 8 3 8 9 8 3 4
9 0 8 7 9 5 4 0 7 0 3
Looking for 5 in 3x3 grid at 2,6
6 [5] 1
6 9 9
[5] 8 3
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.
He comes dressed for it and with his own toolkit.
You seem to be testing for proficiency in slow NIH-tendencies basically, but since discomfort is a requirement, maybe that works for you and for them too.