3 ms·

We deal with maps a lot, and I usually ask this one: assume a matrix. Fill the matrix with numbers, so that the outer 'ring' of numbers has the value 1, one 'ri

by roel_v 14y ago

We deal with maps a lot, and I usually ask this one: assume a matrix. Fill the matrix with numbers, so that the outer 'ring' of numbers has the value 1, one 'ring' more to the center has the value 2, and so on. To visualize this, imagine that this matrix represents a height map, where each number represents a cell in a surface, and the value of the number is the elevation of the area of that cell. The result should be a height map of a pyramid. To make things easier, assume that the number of rows and columns in the matrix is equal, and that that number is uneven. Followup-questions may go into the direction of what if some of the assumptions are loosened, or what are the performance implications of several possible solutions, or how to do it when iterating in whatever is the most optimal manner performance-wise considering the storage implementation of the matrix (avoiding cache misses or disk seeking etc.). I've only had a single person ever pass this test, out of 10 or so interviewees. Another one was where a colleague of mine drew a car on a piece of paper and asked the candidate to explain how he would design a class hierarchy if one were to model a car in OOP. His answer was to have a class 'rectangle' and two classes 'circle' (referring to the box and the two wheels my colleague drew on the paper). Seeing the incredulous looks on our faces, he then proceeded to an unintelligible story of 'has-a' vs 'is-a' as it related to the point in the middle of the circles, and how a 'point' somehow 'was-a' circle except that it had room in the middle. True story.

Hupo 14y ago
>We deal with maps a lot, and I usually ask this one: assume a matrix. Fill the matrix with numbers, so that the outer 'ring' of numbers has the value 1, one 'ring' more to the center has the value 2, and so on. To visualize this, imagine that this matrix represents a height map, where each number represents a cell in a surface, and the value of the number is the elevation of the area of that cell. The result should be a height map of a pyramid. To make things easier, assume that the number of rows and columns in the matrix is equal, and that that number is uneven. This sounded fun, so I thought about it for a couple minutes and came up with the following in JavaScript: var pyramatrix = function(a) { a += 1 - (a & 1); // increment a by one if even var b = [], // pyramid y-axis c = a-(a>>1), // get the "center" of the pyramid (eg. 7 -> 1234321 -> 4 is the center) d = function(x) { return Math.abs((x+1)-c) }, // calculate offset from center e, f, // values for storing current index offset g = ''; // initialize string for pretty output for(var i = 0; i < a; i++) { b[i] = []; // pyramid "x-axis" (current row) for (var j = 0; j < a; j++) { e = d(i); // get y offset f = d(j); // get x offset b[i][j] = c - (e > f ? e : f); // set current index to center minus larger offset g += '['+b[i][j]+']'; // add value to pretty output } g += '\n'; // add a line break after each row } console.log(g); // print pretty output } Example usage and output: pyramatrix(7) [1][1][1][1][1][1][1] [1][2][2][2][2][2][1] [1][2][3][3][3][2][1] [1][2][3][4][3][2][1] [1][2][3][3][3][2][1] [1][2][2][2][2][2][1] [1][1][1][1][1][1][1] I was pretty satisfied when it worked exactly as intended on the first try! EDIT: Now that I look at it, you could obviously move e = d(i); outside the second for loop, but for the sake of posterity I'm not going to change the solution from what I first came up with.
- roel_v 14y ago
  That looks like a nice solution to me, some of the Javascript idioms I'm not familiar with, but after looking at it for a while it seems you're using what I'd consider the 'best' method of generating it - looping over each cell and calculating the height based on the distance to the 'top' (or 'center', depending on how you look at it). Personally I consider the 'naive' version (as in: the first, easy to manually verify version one would bang out as a prototype) to be one where a matrix is pre-allocated and each ring is filled in from the outside inwards (so first assign all 1's, then all 2's, and so on), but funnily enough nobody ever went that route, not even my colleagues who did it.
  - Hupo 14y ago
    >Personally I consider the 'naive' version (as in: the first, easy to manually verify version one would bang out as a prototype) to be one where a matrix is pre-allocated and each ring is filled in from the outside inwards (so first assign all 1's, then all 2's, and so on) I'd consider the 'naive' version (and the first solution that popped to my mind pretty much instantly) to be where you first fill the grid with 1's, then then loop over the next level and add 1 and repeat until you're on the top. So like this for example: function(a) { a = a | 1; // add 1 to even numbers var b = new Array(a), i, y, x, s = 0; // initialize the array for(y = 0; y < a; y++) { b[y] = new Array(a); for(x = 0; x < a; x++) { b[y][x] = 0; } } // turn it into a pyramid heightmap for(i = a; i > 0; i--) { for(y = s; y < i; y++) { for(x = s; x < i; x++) { b[y][x]++; } } s++; } return b; } Though in JavaScript it's a bit more complex than it might otherwise be since you can't just declare a multi-dimensional int array in a single line. Anyway, I discarded this solution about as fast as I came up with it because I knew there'd be more clever ways to go about it, and came up with the offset calculation method a couple minutes after that. And amusingly enough I had to actually test and iterate this 'naive' version a bit before I got it running right, whereas my 'complex' solution worked on the first try. Funny how that goes.
droithomme 14y ago
Thanks for the pyramid example, that's a good one. As a calibration point, it took me from 16 minutes past the hour when I read your post to 26 past the hour to complete. And the ten minutes included two interruptions where I had to go to another office. And 3 more minutes to write this post. I did google "2d array python" when the array initialization I used at first didn't work. (I'm new to python and had not done a 2d array in it yet.) Works fine, dumps the result in formatted output, and accepts any positive number as an argument to pyramid size, odd or even.
- roel_v 14y ago
  Thank you, that's interesting. That's in the magnitude of time I myself estimated when I started asking this question, but I started wondering over time if my expectation was realistic.
bjourne 14y ago
> I've only had a single person ever pass this test, out of 10 or so interviewees. Did that person get the job? Lots of companies seem to administer those brain-bending tests and then does not use it as the deciding factor when hiring someone. I've personally been exposed to several quizzies like checking if a number is a prime, walking a directory tree and printing .txt files, implementing a variant of the soundex algorithm, a web server to interact with the twitter api... The worst (or best) was one in which the interviewer asked me to solve a Roman Square problem as a homework. Except instead of a 3x3 square it was a hexagon containing 64 numbers. Aced all the tests, even the Roman Square and the interviewer even told me I was the only one they had interviewed that solved the problem. It was freakishly hard and involved creating a pretty complicated constraint solver. I still didn't get the job. In fact, the common theme in my professional life, after dozens of interviews, is that if there is a programming test involved then I will not be offered the job, no matter how well I score. My conclusion is that companies do not use tests to determine whether to hire applicants or not. Interviewers make up their decisions regardless of test results and then use them purely to make their decision seem more objective they in reality are: "Bill scored low on or test, he is not a good candidate..." or "Bill did score well, BUT $blablabla" where $blablabla is some irrational stuff.
- roel_v 14y ago
  This particular one did, yes, but not just because she could solve this problem. I refuse to let my hire/no hire recommendations be boxed into binary thinking or autistically rigid 'if a then b' type of testing. I will try my best to interview in a way that will eliminate or suppress any biases I may have, but will still use judgement when interpreting the results of any tests/questions. Rigid algorithms are too easy to game.

by roel_v 14y ago

Hupo 14y ago

>We deal with maps a lot, and I usually ask this one: assume a matrix. Fill the matrix with numbers, so that the outer 'ring' of numbers has the value 1, one 'ring' more to the center has the value 2, and so on. To visualize this, imagine that this matrix represents a height map, where each number represents a cell in a surface, and the value of the number is the elevation of the area of that cell. The result should be a height map of a pyramid. To make things easier, assume that the number of rows and columns in the matrix is equal, and that that number is uneven. This sounded fun, so I thought about it for a couple minutes and came up with the following in JavaScript: var pyramatrix = function(a) { a += 1 - (a & 1); // increment a by one if even var b = [], // pyramid y-axis c = a-(a>>1), // get the "center" of the pyramid (eg. 7 -> 1234321 -> 4 is the center) d = function(x) { return Math.abs((x+1)-c) }, // calculate offset from center e, f, // values for storing current index offset g = ''; // initialize string for pretty output for(var i = 0; i < a; i++) { b[i] = []; // pyramid "x-axis" (current row) for (var j = 0; j < a; j++) { e = d(i); // get y offset f = d(j); // get x offset b[i][j] = c - (e > f ? e : f); // set current index to center minus larger offset g += '['+b[i][j]+']'; // add value to pretty output } g += '\n'; // add a line break after each row } console.log(g); // print pretty output } Example usage and output: pyramatrix(7) [1][1][1][1][1][1][1] [1][2][2][2][2][2][1] [1][2][3][3][3][2][1] [1][2][3][4][3][2][1] [1][2][3][3][3][2][1] [1][2][2][2][2][2][1] [1][1][1][1][1][1][1] I was pretty satisfied when it worked exactly as intended on the first try! EDIT: Now that I look at it, you could obviously move e = d(i); outside the second for loop, but for the sake of posterity I'm not going to change the solution from what I first came up with.

roel_v 14y ago
That looks like a nice solution to me, some of the Javascript idioms I'm not familiar with, but after looking at it for a while it seems you're using what I'd consider the 'best' method of generating it - looping over each cell and calculating the height based on the distance to the 'top' (or 'center', depending on how you look at it). Personally I consider the 'naive' version (as in: the first, easy to manually verify version one would bang out as a prototype) to be one where a matrix is pre-allocated and each ring is filled in from the outside inwards (so first assign all 1's, then all 2's, and so on), but funnily enough nobody ever went that route, not even my colleagues who did it.
- Hupo 14y ago
  >Personally I consider the 'naive' version (as in: the first, easy to manually verify version one would bang out as a prototype) to be one where a matrix is pre-allocated and each ring is filled in from the outside inwards (so first assign all 1's, then all 2's, and so on) I'd consider the 'naive' version (and the first solution that popped to my mind pretty much instantly) to be where you first fill the grid with 1's, then then loop over the next level and add 1 and repeat until you're on the top. So like this for example: function(a) { a = a | 1; // add 1 to even numbers var b = new Array(a), i, y, x, s = 0; // initialize the array for(y = 0; y < a; y++) { b[y] = new Array(a); for(x = 0; x < a; x++) { b[y][x] = 0; } } // turn it into a pyramid heightmap for(i = a; i > 0; i--) { for(y = s; y < i; y++) { for(x = s; x < i; x++) { b[y][x]++; } } s++; } return b; } Though in JavaScript it's a bit more complex than it might otherwise be since you can't just declare a multi-dimensional int array in a single line. Anyway, I discarded this solution about as fast as I came up with it because I knew there'd be more clever ways to go about it, and came up with the offset calculation method a couple minutes after that. And amusingly enough I had to actually test and iterate this 'naive' version a bit before I got it running right, whereas my 'complex' solution worked on the first try. Funny how that goes.

droithomme 14y ago

Thanks for the pyramid example, that's a good one. As a calibration point, it took me from 16 minutes past the hour when I read your post to 26 past the hour to complete. And the ten minutes included two interruptions where I had to go to another office. And 3 more minutes to write this post. I did google "2d array python" when the array initialization I used at first didn't work. (I'm new to python and had not done a 2d array in it yet.) Works fine, dumps the result in formatted output, and accepts any positive number as an argument to pyramid size, odd or even.

roel_v 14y ago
Thank you, that's interesting. That's in the magnitude of time I myself estimated when I started asking this question, but I started wondering over time if my expectation was realistic.

bjourne 14y ago

> I've only had a single person ever pass this test, out of 10 or so interviewees. Did that person get the job? Lots of companies seem to administer those brain-bending tests and then does not use it as the deciding factor when hiring someone. I've personally been exposed to several quizzies like checking if a number is a prime, walking a directory tree and printing .txt files, implementing a variant of the soundex algorithm, a web server to interact with the twitter api... The worst (or best) was one in which the interviewer asked me to solve a Roman Square problem as a homework. Except instead of a 3x3 square it was a hexagon containing 64 numbers. Aced all the tests, even the Roman Square and the interviewer even told me I was the only one they had interviewed that solved the problem. It was freakishly hard and involved creating a pretty complicated constraint solver. I still didn't get the job. In fact, the common theme in my professional life, after dozens of interviews, is that if there is a programming test involved then I will not be offered the job, no matter how well I score. My conclusion is that companies do not use tests to determine whether to hire applicants or not. Interviewers make up their decisions regardless of test results and then use them purely to make their decision seem more objective they in reality are: "Bill scored low on or test, he is not a good candidate..." or "Bill did score well, BUT $blablabla" where $blablabla is some irrational stuff.

roel_v 14y ago
This particular one did, yes, but not just because she could solve this problem. I refuse to let my hire/no hire recommendations be boxed into binary thinking or autistically rigid 'if a then b' type of testing. I will try my best to interview in a way that will eliminate or suppress any biases I may have, but will still use judgement when interpreting the results of any tests/questions. Rigid algorithms are too easy to game.