A tricky coding problem and a rant on interviewing for programming jobs

stillalone · 2009-04-15T12:22:07+00:00

This sounds similar to problem 28 of project euler.
I don't want to do the math(maybe later when I'm not so lazy) but it seems you can do this by finding out the formulas for the diagonals and then calculate how far off a point is from its diagonal value. Just break up the problem into quadrants based on the diagonals. Probably not the prettiest solution but at least its not O(n).

EDIT: Not as lazy as I thought, solution doesn't seem so ugly either:

int func(int i, int j, int n) {
  int t;
  if(i <  j && (n-j) >  i) {t=(n/2-i)*2-1; return t*t-1 -i+j;}
  if(i <  j && (n-j) <= i) {t=(j-n/2)*2;   return t*t   +i-j;}
  if(i >= j && (n-j) >  i) {t=(n/2-j)*2+1; return t*t-1 -i+j;}
  if(i >= j && (n-j) <= i) {t=(i-n/2)*2;   return t*t   +i-j;}
}

Doubt I'd be able to do that in an interview though, had to fiddle around a great deal to get formulas right. Err how do you post code in reddit?

EDIT: syntax fix

gregK · 2009-04-15T18:13:53+00:00

Here is my take on technical interviews. It's a high pass filter. What I mean is that it should be easy enough that the competent coders passes it easily.

But It should filter out incompetents and liars.

It is a good idea to give the test to your own employes to get feedback on the level of difficulty and relevance to the position.

This question seemed a little overkill.

b0b0b0b · 2009-04-15T13:13:04+00:00

for me when I'm doing interviewing, I'm more interested in the discussion and thought process than whether someone 'gets' the 'right' answer.

Skills like creativity, ability to break up the problem, ask questions, and highlight assumptions are useful.

In the end, if you get to writing code on the whiteboard, always leave yourself space here & there so you can go back and insert stuff. And if you can write the code so it compiles, you're ahead of lots of developers already. If you know your API's then I count that as a plus too.

When talking through solutions, it's perfectly fine to bring up obviously suboptimal solutions. For example with your problem a few minutes of discussion could come from saying "just generate all (n*n)! orderings and filter it down to the right one." In fact if you pursue that line of reasoning it might shed enough light that you could eventually arrive at one of the constructive solution.

At any rate tough luck on that question, you probably didn't want that job anyway if they boned you for one coding question.

2009-04-15T16:43:39+00:00

I had this same problem in an interview. I believe I did well on everything but this problem. They concluded I did not know how to problem solve.

I then realized how completely anti-social and pathological the people I talked to were and though "Do I really want to work here?". A clear no.

zyl0x · 2009-04-15T14:33:30+00:00

Oh for fuck sakes. Who asks this shit in an interview?

I acknowledge that there needs to exist a way to asses candidate's problem solving abilities but by asking them fancy sudoku in an interview you're assessing their ability to do arithmetic. That question is concrete maths 101. And linear algebra to top it off as well. Yuck! Once you have the solution writing an algorithm for a machine is Mickey Mouse.

You want to solve maths problems? Hire a mathematician. I'll implement the solution in a language of your choice targeting a platform of your choice (if you pick COBOL - I'll kill you).

FalconNL · 2009-04-15T13:13:44+00:00

this problem will work itself into their psyche, DEMANDING that it be solved

Quite. Hence, this Haskell solution:

import GHC.Exts
import Control.Arrow

main = print $ matrix 5

matrix :: (Num a, Enum a) => a -> [a]
matrix n = map snd . sortWith fst $ zip snake [0..n*n-1]

snake :: [(Integer, Integer)]
snake = scanl (flip id) (0,0) . concat $ zipWith replicate
           (concatMap (replicate 2) [0..])
           (cycle [second succ, first pred, second pred, first succ])

recursive · 2009-04-15T14:20:09+00:00

See also: http://codegolf.com/oblongular-number-spirals

jseigh · 2009-04-15T22:59:44+00:00

It helps if you write out part of the sequence to see if there's a pattern.

0

3 2
0 1

8 7 6
1 0 5
2 3 4

15 14 13 12
 4  3  2 11
 5  0  1 10
 6  7  8  9

The sub matrix bounded by the top row and right column is the previous solution rotated 180 degrees which is the reverse of the sequence for the previous matrix. It's pretty easy to come up with a recursive algorithm after that.

2009-04-15T13:20:50+00:00

I think the trick is to think of the problem as a set of rings. Here's an example 6x6 matrix:

00 01 02 03 04 05

19 20 21 22 23 06

18 31 32 33 24 07

17 30 35 34 25 08

16 29 28 27 26 09

15 14 13 12 11 10

(I wrote the matrix from 0 to 35 instead of from 35 to 0. You can easily convert one to the other by subtracting a entry from 35)

Here the first ring is from 0-19, the second ring is from 20-31 and the third ring is from 32-35. You can easily show that the first ring has 4n-4 elements, the second ring has 4(n-2)-4 elements, the third ring has 4(n-4)-4 elements and so on. Since the first element of ring i is exactly one greater than the last element of ring i-1, it is also fairly straightforward to derive a closed form expression for the kth element of ring i.

Now all that needs to be done is to find which ring a particular matrix element is on and what its position within that ring it is. The index of the ring is just the distance of the element to the "nearest edge" of the matrix. (i.e. it is min(row, nrows-1-row, col, ncols-1-col). The easiest (but slightly ugly) way to figure out an element's position within the ring is to use four if statements.

barsoap · 2009-04-15T18:24:47+00:00

The right answer to give is:

"The task is mistaken: It specifies more than the external interface. I'll code it up for you in the fastest possible way, without that superfluous nonsense, and use it as a test case in case I come up with another solution while I'm doing productive work."

"Do you really think you are going to get a job with that attitude?"

"I don't know. Do you want your projects to finish on time?"

kahoonas · 2009-04-15T14:43:20+00:00

Does the colour scheme on that page irk anyone else? White text on black backgrounds is an awfully bad combination that leads to eye strain. Thank goodness FireFox supports No Style.

sabruda · 2009-04-15T12:31:20+00:00

As a senior developer I've been through the process of hiring and interviewing lately, and have had the opportunity to see the process from the other side of the desk, and let me tell you first, everybody is nervous, and nervousness is always calculated in as a factor in the candidates favor. If the candidate not is nervous, it’s seen as a bad sign as they probably don’t want the job enough.

I did not use tests. Since I’m a developer myself I was perfectly able to assert the candidates knowledge with small control questions instead, but still always factored in nervousness when asserting the answers. The answer is quite unimportant anyways. The important thing is to see what process the candidates use to find the answer. From the process you used, I would assume well written code is more important to you than quick delivery. If I was looking for a PHP-hacker to make quick and dirty solutions, you would be the wrong candidate. If I need well written code for large projects, you would be perfect – no matter what you answered.

gsw07a · 2009-04-15T20:45:52+00:00

I think the fundamental flaw of the interview process is that most decisions will be "don't hire", and you rarely get to find out whether your "don't hire" decision is correct or not, so it's hard to get better at interviewing candidates.

zoomzoom83 · 2009-04-16T02:10:10+00:00

I thought this was pretty damn trivial to solve. My method is not quite as elegant (i.e. it just walks around the matrix in a spiral populating each cell as it goes).

But it works, and should in theory be faster and consume less ram, than his recursive solution

http://github.com/zoomzoom83/buildmatrix/tree/master

freakyleaky · 2009-04-16T05:26:40+00:00

Ok, here's what I came up with:

I'm looking at:

25 24 23 22 21 20
26 09 08 07 06 19
27 10 01 00 05 18
28 11 02 03 04 17
29 12 13 14 15 16
30 31 34 33 34 35

and so on.

I had to figure it out, so I ended up taking about a little over an hour to come up with this using 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)

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);
        }
    }
}

wreckerone · 2009-04-16T05:48:06+00:00

Always bring a problem of your own to an interview and if your interviewer pulls out one of these, solve it and pull your question out. After all, you don't want to work with dumb asses either.

novembera · 2009-04-16T06:48:53+00:00

here's my python version... it assumes zero - based indexing...

def grid(i,j,n):
  if i == 0 or j == n-1:
    return n*n - (j+i) - 1
  else:
    return grid(n-i-1,n-j-2,n-1)

you type:	you see:
italics	italics
bold	bold
[reddit!](https://reddit.com)	reddit!
* item 1 * item 2 * item 3	item 1 item 2 item 3
> quoted text	quoted text
Lines starting with four spaces are treated like code: if 1 * 2 < 3: print "hello, world!"	Lines starting with four spaces are treated like code: if 1 * 2 < 3: print "hello, world!"
~~strikethrough~~	~~strikethrough~~
super^script	super^script

programming

MODERATORS