Coding problems, logic problems, and the joys of job hunting
by Evil Stick Man on Apr.13, 2009, under Randomness, Ravings, Technology
This morning I came up with an answer to a programming/logic question I was given during an interview back in early February. Before going into the rest of it, let me give the problem (and the solution I belatedly derived):
Problem: Given a dimension n, output an array that represents an n x n matrix of numbers beginning at (n*n)-1 and decreasing to 0. The numbers must be output in such a manner as to “wrap around” the resulting matrix, and must be output as a single array. For example, if the function is given the number ‘3′, the output will be as follows:
8, 7, 6, 1, 0, 5, 2, 3, 4
Which is a linear, row-major representation of the matrix
8, 7, 6
1, 0, 5
2, 3, 4
You may not pre-calculate the matrix and index into it, nor may you store an array of results and index them based on the dimension. In other words, you need to develop a function that, when given a position (i, j) and a dimension n, outputs the appropriate value for (i, j).
My solution:
int calc(int i, int j, int n)
{
if(i == 0 || j == (n-1))
{
return ((n*n) - 1 - i - j)
}
if(i == (n-1) || j == 0)
{
return (((n-1)*(n-1)) - ((n-1) - j) - ((n-1) - i))
}
if(n > 2)
{
return calc(i-1, j-1, n-2)
}
// should never get here
return 0
}
Explaining the solution:
I don’t claim that this solution is optimal, or that this solution is the “right” solution. All I can say for it is that when I worked out the “wrapped” matrices for several dimensions and then ran those resulting matrices cell-by-cell through the above algorithm the results matched, meaning that if nothing else the function above successfully takes a coordinate input and returns the “wrapped” value. Indeed, if anyone has a better solution to the problem, please let me know!
One of the first things that should be obvious in this solution is the recursion (when n > 2), and I figure that deserves some explanation. If you write out several examples, you start to notice a pattern. For example, take a look at the matrices for n = 3 and n = 5:
24, 23, 22, 21, 20
8, 7, 6, 9, 8, 7, 6, 19,
1, 0, 5, 10, 1, 0, 5, 18,
2, 3, 4 11, 2, 3, 4, 17,
12, 13, 14, 15, 16
The larger dimension, n = 5, actually contains the matrix for n = 3 verbatim. In fact, this is true of all odd and all even dimensions - the matrix for n = 6 contains n = 4, and the matrix for n = 7 contains both n = 5 and n = 3 (I’ll leave it to you to work out these matrices to see that this is true). So the recursion needs to occur on n -2 in each case, to move to the next odd or even dimension as applicable. A dimension of 1 outputs 0 in a single location, and a dimension of 2 outputs the matrix 3, 2, 0, 1 as expected given the above conditions, meaning that the guard against n > 2 is unnecessary, but I felt uncomfortable leaving it out.
Once you figure out the recursion, you then need a means to calculate the “border” values. The two equations you see above are the results of two or three hours of deliberations and testing by hand. There is a division between how you count each edge - the top and rightmost edge use one formula, while the bottom and leftmost edge use another. This is reflected in the two conditions above. (I originally wrote it out as four separate conditions, but condensed it into 2). The conditions check only for the edge cases - when i = 0 (top edge), when j = 0 (left edge), when i = n-1(right edge, or when j = n-1 (bottom edge).
OK, so what’s the big deal?
This problem has been bothering me for almost two months now. It was something I should have been able to do (and, indeed, I was eventually able to do it), and I’m pretty sure that my inability to provide the complete answer during the interview resulted directly in me not getting the job (especially considering I nailed the technical portion of the interview). More than that, though, it exposed a worry that I had that I was actually losing intelligence as I age. I felt strongly that I should have been able to solve it sooner, and indeed some anxiety as a result of this internal assertion probably led to my inability to provide the complete solution during the interview. That and the general stress of interviewing with a company whose phone screen was so technically intense that anyone who could make it into their offices for the in-person pretty much officially Knows Their Stuff (or so I’m told).
This problem bugged me so much that I spent time solving it while on vacation, sitting around with graph paper and a pen while my family socialized around me. For some reason I let this one problem, this one failed interview get to me in a very primal way, and I’ve been wracking my brains trying to figure out why I just couldn’t get over it. I tied my ability to solve problems (which, as a programmer, is pretty much my bread and butter) to my self-worth, and became slightly obsessed as a result. Indeed the obsession is still fading - half the reason for this post is the hope that someone out there in internet-land has a better solution, or at the very least can confirm my efforts!
One of the biggest problems any coder looking for work has is in proving themselves. Companies are looking for programmers who know what they claim to know, who aren’t bullshitting the interviewer into a job they’ll be forced out of in 6 months due to incompetence. Furthermore, many companies ascribe to the philosophy that a great programmer is many times more productive than a mediocre programmer (a philosophy I don’t necessarily disagree with, but more on that later) and thus orient their screening process towards ferretting out these artisans of ascii. This basically boils out into one of three interview patterns:
1 - The candidate is subjected to several intense hours of technical interviews covering topics ranging from mathematics to algorithms to data design
2 - The candidate is subjected to a programming or logic test designed to be unique enough so as not to be easily searchable on the web and to test the candidate’s ability to both work under pressure and produce excellent code
3 - The candidate is subjected to both pattern 1 and pattern 2.
The problem faced by the companies, of course, is that there are a lot of people out there who would attempt to subvert the interview process by learning a few buzzwords and faking their way through the process. As a result, these charlatans have caused the rest of us decent people trouble and made companies highly selective.
The problem faced by the job candidate, though, is more insidious. First off, some people (I am not one of them, but I can understand the mindset) take offense at having to take coding tests, thinking that their years of experience and stellar references should be adequate proof of their ability. Second, these kinds of problems can have a profound effect on the job candidate, and can affect the course of the interview. Sure, throwing a curve ball at someone is a good opportunity to judge how they react to adverse situations, but with programmers (and problem-solvers in general), if they get this kind of thing wrong, or even worse if they can’t solve it at that time, this problem will work itself into their psyche, DEMANDING that it be solved, and will take a measurable toll on the individual as they obsess about the problem while trying to continue to answer the interviewer’s questions as they move on to other areas, and in the end this kind of problem colors the company’s perception of the candidate in a manner disproportionate to the applicability of the skills involved to the job being applied for. Third, these kinds of problems have yet to demonstrably select the “best” candidate for the job. The skills used to solve logic puzzles are not necessarily those used to solve programming problems, and 95% of any programmer’s job is not going to require thought of that order at all. Take Microsoft, for example - they are notorious for using these kinds of interviewing tactics and as a result they do write some very good code, but they also make some of the most horrific blunders in code and application design known to man.
Probably the biggest problem with this kind of interviewing pattern, though, is that every worthwhile company has their own problem or three, and every worthwhile company thinks that pushing their candidates through the technical interview/logic/coding problem wringer results in getting the best of the best. Each and every company prides themselves on having the best and the brightest, evidenced by how well these individuals did on their tests. This calls into view a white lie that recruiters tell themselves - that there are more bright people than there are job openings. Any person of moderate intelligence can do the math and realize that the number of positions governed by hiring managers employing these tactics exceeds the statistically probable numbers of “best and brightest”. Not everyone gets to be an astronaut, and there are a lot more fry cooks than there are rocket scientists. But most importantly of all, these managers and these companies ignore one of the brutal truths of programming in general: 95% of coding is performing the equivalent of menial labor, the kind of tasks that you could train a monkey to perform if you had the time. No matter how intelligent your programmers are, their intelligence is largely wasted if all they do is implement specs. For every person developing an algorithm for an autonomous combat drone, there are dozens squirreled away in a cube farm updating corporate software for the next big product switch, changing enumerations occasionally throughout the code, or hunting down an elusive typo.
As a job seeker, there’s not much we can do except rail against the system quietly after we’ve already gone through the wringer and found that next employer. The only means to change this process come when you have power that is typically granted to people that don’t have Computer Science anywhere in their credentials, and even then a significant portion of technical manners swear by the “beat down” method of interviewing. For myself, all I can do is know that I am competent, that given enough time I can perform 95% of coding tasks in the business world, and that no matter what my inability to solve a problem is much more easily explained by stress than by a phantom loss of intelligence.
Note that this is not an indictment of my current employer. Yes, I had to take a coding test when I was interviewing with them, but they also had one of the least BS-laden interview processes I’ve ever been through. I only wish the rest of the companies I interviewed with had been as straightforward. All I’m really doing here is releasing some pent-up aggression from my job hunt in the form of an internet rant. Not really effective, but it does help me feel better 
Anyway, I’m done with the incoherent ramble.
Leave a Reply
-
Welcome
This blog is for my own rantings and ravings, in an attempt to keep many things out of my mind that would either fester unendingly or to simply say those things which need to be said. Feel free to leave comments, or subscribe to our feed to stay updated. You can also sign up to receive updates via e-mail below.
You can also subscribe by email by filling the field below:
-
E-mail Updates
-
Recent Posts
-
Browse by tags
-
Search this blog, and the web
-
Visit our friends!
A few highly recommended friends...
-
Archives
All entries, chronologically...
- View blog reactions
-
April 15th, 2009 on 5:51 am
but it’s not tricky at all
after you fill the first row, you snip it away and rotate the (now rectangular) (n-1) by n array 90 degrees counterclockwise
after you fill the first row of _that_ array, you repeat - and end up with the square (n-1) by (n-1) array, rotated 180 degrees
that is your basic recursion step - and after two such steps you’re back to the (n-2) by (n-2) core - that’s why 3×3 is repeated in 5×5
April 15th, 2009 on 6:15 am
so, Java code is like
static int calc(int i, int j, int m, int n) {
assert m > 0;
assert n > 0;
assert i >= 0 && m > i;
assert j >= 0 && n > j;
int start = m * n - 1;
if (j == 0) { // first line
return start - i;
}
return calc(j - 1, m - i - 1, n - 1, m);
}
static int calc(int i, int j, int n) {
return calc(i, j, n, n);
}
April 15th, 2009 on 6:40 am
@Hotgiraffe - I hadn’t thought of it that way. I’ll spend some time understanding your solution - thanks much for the insight!
April 15th, 2009 on 6:41 am
It’s a dreadful interview question, not because it’s too difficult or too easy or whatever, but because:
“You may not pre-calculate the matrix and index into it, nor may you store an array of results and index them based on the dimension.”
The whole point of these questions is to test the candidates ability to find a solution. _A_ solution, not necessarily _your_ solution. An elegant solution (like hotgiraffe’s) is great if that’s what comes out, but its a bit much to expect in an interview situation.
—–sharks
April 15th, 2009 on 7:05 am
@Hotgiraffe - but isn’t that a bit cheating? I mean, OK, now I take the obvious loop-based matrix filling solution (I’d probably write something involving “IntVector2 direction, position, topleft, bottomrigth”) and trivially patch it so that instead of actually going step-by-step in current direction decreasing a counter and writing it down until I hit a wall, I calculate the distance to the wall and either skip to it instantly if my counter allows or return “position + direction * counter”.
It is isomorphic to your (and to the original) recursive solution, maybe a bit more verbose, yet faster and easier to grasp. And when stripped of its recursive cover it doesn’t feel like it really conforms to the spirit of “not pre-calculate the matrix” restriction - sure, it’s quite optimised, performing only 4n steps (and using 4n stack frames in the non-tailrecursive variant) in the worst case, instead of naive n*n, and it even might be the best solution, but yet…
April 15th, 2009 on 7:22 am
Oh, I accidentally solved a symmetric problem, for the real one I should stop if I go through the target cell and return the counter.
April 15th, 2009 on 7:45 am
I’m guessing the interviewer wanted you to recognize this as a prime spiral, e.g.:
http://mathworld.wolfram.com/PrimeSpiral.html
Although prime spirals start at 1, not 0.
April 15th, 2009 on 8:04 am
I’ve railed against stupid interview questions before. Such a question has zero to do with programming ability, unless the job happens to be for some kind of math based company. Programming != Math.
April 15th, 2009 on 9:44 am
You can solve this with recursion and radial (polar) coordinates. Every point in the matrix has a polar coordinate (r, theta) based on the Archimedes spiral (see http://en.wikipedia.org/wiki/Archimedean_spiral and http://en.wikipedia.org/wiki/Polar_coordinates). The value of every point in the matrix is the value of the previous point on the spiral plus one. Start at theta=0 and go negative to wind the spiral clockwise. This is probably the mathematical insight the interview question was seeking, though the actual formulas you have to work out are annoying.
April 15th, 2009 on 10:26 am
@faceted_jacinth - well, I wouldn’t call it cheating, because I can show the interviewing person a couple of little doodles of rectangular arrays on a piece of paper that illustrate how I go more or less directly from the problem to the solution not using any matrix-filling algorithms, just basic notions of recursion and coordinate transformation on 90-degree rotations
April 15th, 2009 on 10:40 am
The topic of your post is fascinating, but the white text on a black background makes reading it very hard on the eyes. It’s a shame that the presentation of your content should detract from the content itself… may I suggest changing your site to a white background with black or dark gray text?
For reference: http://www.craftedweb.com/website-design/website-design-stay-away-from-white-text-on-black-backgrounds/
April 15th, 2009 on 10:44 am
My recursive step was to spot that each square was the same as the inverted previous square with a top and right column added.
My code was:
calc x 0 n = (n*n - 1) - x
calc x y n
| (x == maxcol) = n*n - n - y
| otherwise = calc (n - 2 - x) (n - 1 - y) (n - 1)
where
maxcol = n - 1
Hotgiraffes realisation that the recursive step is rotational and rectangular rather than square makes for even nicer code:
calc x y n = giraffe x y n n
giraffe x 0 width height = width * height - 1 - x
giraffe x y width height = giraffe (y - 1) (height - x - 1) height (width - 1)
April 15th, 2009 on 10:56 am
please, use a bigger and more readable font (verdana should do the trick). With this high contrast (white on black) I haven’t been able to finish the reading.
April 15th, 2009 on 11:24 am
unznown +1
Don’t specify a font size at all. Let your readers decide how big to make their default font. Your current font size is *way* too small. (I hit Ctrl+ three times before it was readable.)
April 15th, 2009 on 11:51 am
So, like has been mentioned before:
Look at it square by square:
- If you’re pulling off the top or the right side, it’s a simple calculation
- Else, you want to index into the nested (n-1) square in the bottom left corner (and reverse your indices).
Your row in the smaller square is just the opposite: (n-1) - i. Your column should be the same, but subtract another, since you exclude the rightmost column.
In OCaml:
let rec calc i j n =
if i = 0 then
(n*n - 1) - j
else if j = n-1 then
(n*n - n) - i
else calc (n-1-i) (n-2-j) (n-1)
April 15th, 2009 on 12:23 pm
Notice the main diagonal contains values x^2-1 to the upper left, and x^2 to the lower right, where x depends on which nested square you’re on.
First figure out if the point is to the NW or SE of the reverse diagonal, then find the corner square at (x,x) where x=min(i,j) (NW) or (n-x,n-x) (SE). Then test if i<j and add or compute accordingly. There’s probably some improvement to be had since the reverse diagonal corners are symmetrical, but I’ve got other things to do now. Here’s some ugly non-recursive Groovy code. S is the square root of the diagonal corner, c is the corner.
n=5
def foo(n,i,j) {
def NW = i+j-(n-1) =i)
v = c - (j-i)
else
v = (s-1)**2 - s + 1 - (n-1-sqnum-i)
} else {
def max = Math.max(i,j)
sqnum = n-max-1
s = n-2*(n-max)+1
c = s**2
v = c-(i-j)
}
return v
}
m=(0..
(0..
def v = foo(n,i,j)
String.format(”%2d”,v)
}
}
m.each{ println it }
April 15th, 2009 on 12:58 pm
Here’s how I solved it in javascript. It’s actually a bit more verbose but it returns the completed array when done. The idea is the same though.
var indexCalc = function(n) {
return function(i, j) {
return i + j * n;
};
};
var computeWrappingMatrix = function(n, x, y, xinc, yinc, index, acc) {
var xinrange = function(i) {
if (xinc > 0) {
return i x - n;
}
};
var yinrange = function(j) {
if (yinc > 0) {
return j y - n;
}
};
if (n === 1) {
acc[index(x, y)] = 0;
}
else {
var i;
var j;
var v = n * n - 1;
for (i = x, j = y; xinrange(i); i += xinc, v -= 1) {
acc[index(i, j)] = v;
}
for (i -= xinc, j += yinc; yinrange(j); j += yinc, v -= 1) {
acc[index(i, j)] = v;
}
computeWrappingMatrix(n - 1, i - xinc, j - yinc, -xinc, -yinc, index, acc);
}
return acc;
};
var computeMatrix = function(n) {
return computeWrappingMatrix(n, 0, 0, 1, 1, indexCalc(n), []);
};
April 15th, 2009 on 1:10 pm
In Scala:
def helper(n: Int, i: Int, j: Int): Int =
if (i == 1) n*n-j else
if (j == n) n*n - n + 1 - i else
helper(n-1, n-i+1, n-j)
def f(n: Int): List[Int] =
for (i <- List.range(1,n+1); j f(5)
res17: List[Int] = List(24, 23, 22, 21, 20, 9, 8, 7, 6, 19, 10, 1, 0, 5, 18, 11, 2, 3, 4, 17, 12, 13, 14, 15, 16)
helper(n,i,j) is tail-recursive, but it still takes O(n) steps to find each value of the array, making the algorithm O(n^3), whereas matrix pre-calculation gets you the result in O(n^2) time (which is optimal).
April 15th, 2009 on 1:13 pm
Part of my comment got eaten, sorry. Here’s f(n):
def f(n: Int): List[Int] =
for (i <- List.range(1,n+1); j <- List.range(1,n+1))
yield helper(n,i,j)
April 15th, 2009 on 1:23 pm
Your problem got me curious and without looking at your solution this is what I came up with, I tested this with various inputs and seems to work.
[Assumption: All valid inputs with n>0.]
n width/height (matrix size = n * n)
r = row
c = column
mn = n-1
rd = row distance
cd = column distance
d = effective distance
en = effective matrix size
er = effective row
ec = effective column
mn = n-1
rd = min(r-0, mn-r)
cd = min(c-0, mn-c)
d=min(rd, cd)
en=n-d*2
er=r-d
ec=c-d
if ((er == 0) || (ec == (en-1)))
{
value = (en*en-1) - (er+ec);
}
else
{
en_1 = en-2;
value = (en_1*en_1)+(er+ec-1);
}
Pankaj
April 15th, 2009 on 1:46 pm
Having been on the other side of the interview table quite a few times, I don’t have too much of a problem with this question. If I were to give it to a candidate, it would be to see how they think about it and whether they are able to (perhaps eventually and with a few hints and prodding) see that it’s recursive in nature. There are plenty of programmers (even ones with advanced CS degrees) out there that just somehow seem to have never encountered the concept and approach everything by throwing a bunch of nested loops at it and will dig themselves a big, messy hole.
That said, it isn’t the kind of question that I’d give them and leave them alone on. You sit with them and talk through the problem and if they don’t spot the recursive nature right away, you question and hint, and it does eventually give you an opportunity to really see how they think through things and where their background and education are solid or missing. Eg, if their resume claims that they have tons of Lisp experience and they don’t hit on recursion pretty quickly, it could be an indicator that something is up.
So it’s one data point in the process and should be weighted accordingly alongside their claimed experience, education, code samples, etc. Everyone’s allowed to choke up a bit in a high pressure interview and that should be taken into account. It’s actually one of the reasons to make interviews really long, so the candidate has a chance to relax a bit. On the other hand, if a programmer gets so nervous in an interview that they can’t think clearly at all, that’s not a real good sign. I want to know that if they are in a high pressure situation on the job (critical bug discovered an hour before the boss is about to do a big demo) they won’t become totally useless.
I will agree though, that from what I’ve seen, a lot of interview processes will give you these problems (or worse, “trick” questions that are trivial if you’ve encountered them before or otherwise know the trick, and nearly impossible otherwise) and just want to see a solution in isolation, and that’s pretty much useless. My suspicion with most of those is that the interviewers aren’t confident in their own abilities and want to give candidates (who might be smarter or better programmers than them) questions hard questions so they can feel superior.
April 15th, 2009 on 3:29 pm
I can judge how good a programmer is in 5 minutes without once asking a technical question. There is a certain mindset among good technical people that just stands out. A curiosity, a willingness to program even in their spare time.
April 15th, 2009 on 4:08 pm
# SOLUTION
# Examples:
# Matrix(n=1)
# 0
# Matrix(n=2)
# 3 2
# 0 1
# Matrix(n=3)
# 8 7 6
# 1 0 5
# 2 3 4
# Matrix(n=4)
# 15 14 13 12
# 4 3 2 11
# 5 0 1 10
# 6 7 8 9
# Observation:
# Matrix(n=4) contains Matrix(n=3) rotated clockwise by 180 degrees.
# Matrix(n=3) contains Matrix(n=2) rotated clockwise by 180 degrees.
# Based on this observation we think about aplying recursion.
def calc(i, j, n):
assert 0 <= i < n, “i out of range”
assert 0 <= j = 1, “n <= 0″
return calcRecursive(i, j, n)
def calcRecursive(i, j, n):
# end recursion
if n == 1:
return 0
# top edge or right edge
elif i == 0 or j == n - 1:
return n * n - 1 - i - j
else:
# adjust i, j, n for the inner matrix of dimension n - 1
i2 = i - 1
j2 = j
n2 = n - 1
# rotate (i2, j2) coordinates by 180 degrees clockwise
i2 = n2 - i2 - 1
j2 = n2 - j2 - 1
return calcRecursive(i2, j2, n2)
def printCalc(n):
print ‘\n’.join([''.join(['%3d' % calc(i, j, n) for j in range(0, n)])
for i in range(0, n)])
# This will print the matrices
for i in range(10): printCalc(i)
April 15th, 2009 on 4:47 pm
Don’t care about the problem. But wanted to say “been there done that”. I have been in software development for 25 years. I still code all of the time. I have forgotten more than most people know. I hate when i get those lame problems. How about a real world problem they are currently facing? Of course, that is no guarantee either. I have actually known how to fix a company’s issue, but know one in the company was smart enough to know it. Anyway, thanks for the article. Definitely touched a nerve.
April 15th, 2009 on 4:51 pm
I agree that this is a stupid interview question. Even the best and brightest may end up needing more time than the interview allows in order to solve it.
I also agree that you can tell good programmers without asking them any programming questions. All you need to do is ask them to describe their most interesting project to you. You will be able to tell how they delve into problems and make them their own that way. Get them to explain the problem domain and the journey towards a solution. If they dont have a good story to tell you, dont hire them. A good story should be entertaining and informative - you should feel like you have actually learned something new after they are done.
April 15th, 2009 on 5:23 pm
Super post, Need to mark it on Digg
April 15th, 2009 on 6:06 pm
Wow - Just wanted to say thanks, all, for the insightful responses and additional solutions! I’ve got a lot to digest
April 15th, 2009 on 6:07 pm
BTW - I’m sorry for all who have trouble with the site’s style and layout. Honestly I didn’t notice any issue as I prefer light text on darker backgrounds. I’ll see what I can do about a new theme, but given the customization I’ve already done on this one I can’t promise anything quick (or at all)
April 15th, 2009 on 7:18 pm
Here’s my solution (no recursion).
The for loops go around the outside edge of the matrix, filling in the edges. Once all 4 sides are done, it moves inward and fills those edges in the same way. (array base index is 0).
function calc(n) {
/*===Initialize===*/
matrix = new Array();
for(index = 0; index 1) {
for (colindex = startPoint; colindex < n; colindex++) {
matrix[startPoint][colindex] = number;
number–;
}
for (rowindex = startPoint + 1; rowindex = startPoint; colindex–) {
matrix[n-1][colindex] = number;
number–;
}
for (rowindex = n-1-1; rowindex >= startPoint+1; rowindex–) {
matrix[rowindex][startPoint] = number;
number–;
}
n–;
startPoint++;
}
return matrix;
}
April 15th, 2009 on 7:24 pm
Great. The html ruined my code. It even took out the minuses?? :/
How do you post code in here?
April 15th, 2009 on 8:48 pm
Interview questions like this are incredibly counterproductive. Self-selecting for the type of borderline-aspie programmer who excels at irrelevant math puzzles is a mistake. It leaves your company without anyone with right-brain skills. Things like ui design, usability and user friendliness are important as well. Incredibly important.
Microsoft is the perfect example of what happens when you incorporate these methods systematically throughout your hiring process, by the way. You get a bunch of morons who are unable to understand why they fail. Because they don’t hire anyone who could tell them.
April 15th, 2009 on 10:18 pm
Oops, to edit my previous comment, you do in fact need to know N. Everything else should be accurate.
April 15th, 2009 on 10:48 pm
Just to reiterate what a clever reddit guy said… You don’t need to use recursion or any sort of iteration to solve this problem. You just need to split the square into quadrants, find the formula for the lower-right quadrant’s diagonal, and then write down the formula for the i,j entry based on how far it is off that diagonal.
April 15th, 2009 on 10:56 pm
echo calc(2, 2, 6); // 2
function calc($x, $y, $n) {
if ($x > $n - 1 || $y > $n - 1) {
return ‘Invalid coordinates’;
} else {
if ($n % 2 == 0) {
if ($y == 0) {
// point exists on the y = 0 row of this level
return ($n * $n - 1) - ($n - 1 - $x);
} elseif ($x == 0) {
// point exists on the x = 0 column of this level
return ($n * $n - $n) - $y;
}
return calc($x - 1, $y - 1, $n - 1);
} else {
if ($y == $n - 1) {
// point exists on the y = $n - 1 row of this level
return ($n * $n - 1) - $x;
} elseif ($x == $n - 1) {
// point exists on the x = $n - 1 column of this level
return ($n * $n - $n) - ($n - 1 - $y);
}
return calc($x, $y, $n - 1);
}
}
}
April 15th, 2009 on 11:11 pm
My solution above took me about a little over an hour with the following observations:
If n is even, ending coordinates of the matrix will be (n-1, 0) or lower right corner
If n is odd, ending coordinates of the matrix will be (0, n-1) or upper left
Each recursive call can perform a search range from (n * n - 1) to (n * n - 1 - (n * 2 - 2))
This implies that for each call, we are searching these ranges:
For an even n, (n - 1, 0) - (0, 0) and (0, 0) - (0, n - 1)
For an odd n, (0, n - 1) - (n - 1, n - 1) and (n - 1, n - 1) - (n - 1, 0)
Finally, if there is no match:
For an even n, perform recursion with (x - 1, y - 1, n - 1)
For an odd n, perform recursion with (x, y, n - 1)
April 16th, 2009 on 12:05 am
If everything else went well and they made the decision based on this single question, you don’t want to work for those d-bags anyway.
April 16th, 2009 on 4:58 am
Hotgiraffes solution appeals to me as being the most elegant, being at once more general (solves for rectangular matricies), and simpler to code.
It’s certainly better than my solution, even though I’m quite pleased with it.
I like kyb’s Haskellisation of it too. Whole solution, easy to understand in two lines.
April 16th, 2009 on 8:10 am
Here’s a solution with no recursion
I assumed the i,j coordinates are 1,1 at the bottom left corner of the matrix.
public int calc(int n, int i, int j) {
int c = (n + 1) / 2;
int di = i - c;
int dj = j - c;
int absi = Math.abs(di);
int absj = Math.abs(dj);
// vertical/horizontal wall
if (absi > absj || di == dj) {
// left/right
if (di >= 0) {
int r = absi * 2 + 1;
return r * r - r + dj - (r - 1) / 2;
} else {
int r = absi * 2;
return r * r - r - dj - 1 - (r - 1) / 2;
}
} else {
// top/bottom
if (dj > 0) {
int r = absj * 2 + 1;
return r * r - di - 1 - (r - 1) / 2;
} else {
int r = absj * 2;
return r * r + di - 1 - (r - 1) / 2;
}
}
}
The basic algorithm is to calculate the distance to the centre and them depending if it is left/right, top/bottom change slightly the parameters.
April 16th, 2009 on 5:24 pm
A non recursive O(1) solution in C:
Maps i,j to somewhere in the upper triangle of and equivalent matrix, then jumps directly to the correct shell of the spiral.
int spiral(int n, int i, int j)
{
int k;
if (j < i) {
i = n - 1 - i;
j = n - 2 - j;
n = n - 1;
}
k = min(i, n-1-j);
n = n - 2*k;
i = i - k;
j = j - k;
return n*n - 1 - i - j;
}
April 16th, 2009 on 7:33 pm
static int square(int arg){return arg*arg;}
public static int min(int…args){
int rv = 0;
for(int i = 1; i < args.length; i++)if(args[i] < args[rv])rv = i;
return rv;
}
public static int foo(int x, int y, int d){
int yn = d - 1 - y, xn = d - 1 - x;
switch(min(y, xn, yn, x)){
case 0: d -= y << 1; return square(d) - 1 - x + y;
case 1: d -= xn << 1; return square(d) - d - y + xn;
case 2: d -= yn << 1; return square(d) - d - (d << 1) + x - yn + 2;
case 3: d -= x << 1; return square(d) - (d << 2) + y - x + 3;
}
throw new RuntimeException(”Something is wrong with the JRE”);
}
April 17th, 2009 on 2:44 am
Here is a two line solution :). Well it is two lines if you do not have to fit it into a tiny textbox. It is totally unreadable but hey at least we avoid some recursion :).
public int spiral(int x, int y, int n)
{
int k = Math.Min(Math.Min(x, y),
Math.Min(n - 1 - x, n - 1 - y));
return n*n - 1 - 4*k*(n - k) -
(x < y ? (4*n - 6*k - 4 - x - y)
: x + y - 2*k);
}
April 17th, 2009 on 3:30 am
O(1) solutions are good, but beyond that, there’s nothing specifically wrong
April 17th, 2009 on 3:33 am
with recursion.
Especially tail recursion.
Lionel, would you explain how you got to your solution? Obviously the O(1) ness (ignoring multiplications…) of it is good, but I don’t understand how it works at the moment. That was what I liked about hotgiraffes solution, even with the recursion.
April 17th, 2009 on 6:02 am
Sorry for the very messy code I didn’t make it very understandable. The line
int k = Math.Min(Math.Min(x, y), Math.Min((n - x) - 1, (n - y) - 1));
works out which spiral we are in so if you draw a plot of this function you get
0 0 0 0 0
0 1 1 1 0
0 1 2 1 0
0 1 1 1 0
0 0 0 0 0
Which is very similar to what other people have done. The next thing you need to do is work out how far round the outside of the square you are. If I plot the expression
(x < y ? ((2 * n - 2) + ((n - x) + (n - y) - 2)) : (x + y))
1 2 3 4
12 5
11 6
10 9 8 7
You work out how round the point (x, y) is round a n x n square. Now since we know what spiral we are in we can work out how to offset your points into that formula and get how far we are round that spiral. You basically take k away from x and y and reduce n by 2k. After simplification this gives us the expression
(x < y ? (4*n - 6*k - 4 - x - y) : x + y - 2*k)
Which if you plot it gives you:
0 1 2 3 4
15 0 1 2 5
14 7 0 3 6
13 6 5 4 7
12 11 10 9 8
Whic is very very close now you calculate the correct value for the top left hand corner which is:
n*n - 1 - 4*k*(n - k)
And take away the distance around the spiral you get:
n*n - 1 - 4*k*(n - k) - (x < y ? (4*n - 6*k - 4 - x - y) : x + y - 2*k);
Which gives us the answer you want! I have to say may way is really really naff and the recersive soultion is more elegant looking. I just tried to brute force a solution by trying to find a formula to solve it.
I originally thought that this was quite a good iterview question as it certainly makes you think and it should give you some insite as to how an interview candidate solves a problem. However having thought about it seems to need to many moments of inspiration (maybe I am just bitter that I did not spot the recursive solution). Also unless you spot the recursive solution you end up with lots of messy spagetti code. To get a solution it really seem to be necessary to plot lots of different rectangle with different formulas to gain some insight into the problem. It seems there are better things to do in interviews rather than drawing boxes with number on.
Lionel
April 17th, 2009 on 6:03 am
If that doesn’t make sense let me know and I can clarify :). I have never been very good at explaining stuff :).
April 17th, 2009 on 6:07 am
Sorry for spamming but my solution works that same way as Mike’s (I only just read his comment). I have just made it less readable and missed some of his optermisations :). but hey at least mine is short
Lionel
April 17th, 2009 on 8:48 am
Terrible interview question, simply because it works against established best practice: We are taught to use the best tools available, which obviously includes having the full feature set of the language and some recent hardware available at all times. Others (sorry, can’t find the link) have already written about the dangers of approaching programming as a puzzle; essentially, some programmers tend to complicate things to overcome boredom, and in the process add useless or incomprehensible things in the code base.
How about instead presenting the developer with real running code, and ask them what they would do to improve it?
May 14th, 2009 on 11:41 am
For my Scala take, click on my name. I didn’t want to make it super concise or extra efficient: I tried to show the intention. It’s a fun problem.
(Blog post is in Spanish)
May 20th, 2009 on 5:51 pm
Super website. will visit once more!
December 12th, 2009 on 8:30 am
Given M a matrix of NxN (s.t. N = 2k), we say that M is sorted if while dividing the matrix
to 4 sub-matrix’ of N/2 x N/2 (numbered as in the example below), each entry in the first
sub-matrix is smaller (or equals) than elements in the second sub-matrix, each element in
the second sub-matrix is smaller than all elements in the third sub-matrix and each element
in the third sub-matrix is smaller than all elements in the forth sub-matrix and this holds
recursively.
January 29th, 2010 on 12:03 pm
I did it this way: (In PHP)
function calc( $i, $j, $n ) {
if( $i == 0 ) return ( $n * $n ) - $j - 1;
if( $j == ( $n - 1 ) ) return ( $n * $n ) - $j - $i - 1;
return go( $n - $i - 1, $n - $j - 2, $n - 1 );
}
January 29th, 2010 on 12:04 pm
woops, let me correct that…
function calc( $i, $j, $n ) {
if( $i == 0 ) return ( $n * $n ) - $j - 1;
if( $j == ( $n - 1 ) ) return ( $n * $n ) - $j - $i - 1;
return calc( $n - $i - 1, $n - $j - 2, $n - 1 );
}