Evil Stick Blog

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.