The Old New Thing

interview questions are really bad,

1. They must be VERY easy (this was too hard)

2. Without an IDE/compiler you dont come close to develop software in a real situation where you get inspiration & feedback from intellisense and compiler error messages.

640k you're wrong on at least three counts:

Firstly this is a very easy question

Secondly just asking easy questions isn't going to give me/the interviewer a view into how you tackle problems, your thought process or your character. *Hence what Raymond wrote.*

Thirdly how will an IDE with Intellisense help you actually visualise and compose an algorithm to solve a particular problem?

Uh oh - get ready for a deluge of buggy implementations to be posted in everything from FORTRAN to F# (ala FizzBuzz).

640k: eeeek. Was that sarcasm?

Inspiration from intellisense? To solve a problem? Ouch!

Did you read the story? The goal, at least after the initial admittance of incapacity, was to show that you can approach problems you initially don't know how to solve.

At least, the first part where he admits that he doesn't know the answer is admirable: too many people pretend to know everything.

Ian, I think 640k was being sarcastic (at least I hope he was).

Good lord.  Come on, it's a 4x4 matrix, you could hard-code it without doing anything fancy if you're that stuck for ideas!  That guy must truly have been lazy.

Im suprised the interview candidate didnt whip out some .net method in 2 seconds, then spend then next four days trying make sure the correct assemblies and versions of .net were installed correctly. (In other news, I just spent the weekend re-writing a new college grad's code that instead of making one SQL call and looping with the results 4000 times, he made a loop and called the SQL engine 4000 times).

This was a question reserved for intern candidates and fresh out of college hires.  I was usually the first one on the loop and used this as a warm-up question.  Once they got it, we'd move on to something more interesting.  This one guy just refused to believe it was even possible.

Also, I would phrase it as "rotate an N x N matrix where N >= 1, and you are given N along with the matrix A."  This makes it super easy.  If you allow an N x M matrix (i.e. non-square) the question gets much harder.

I don't ask this question as often anymore.  I get bored with asking the same questions over and over.  Furthermore, I think after about the 100th time you ask a question you have lost perspective on it.  Once you can write the answer on the whiteboard by heart without even thinking, you get annoyed by anyone who takes more than a few seconds thinking about it.  It may not be a conscious annoyance but it's there if you think about it, and I think it gives you a bit of a negative bias at times.  At least it does for me.  It's good to find new questions so you have to solve them yourself and you have that feeling of approaching the problem for the first time fresh in your memory.

Back in the 1980s, I decoded the structure of Xerox 9700 Laser Printer fonts, and decided to write a font-editor.

Rotating fonts from portrait to landscape was part of my design, each character became a two-dimensional matrix.

This was all "just for fun", to see if it could be done, but it did lead to some interesting work in printing University Graduation Diplomas.

Alas, the floppy disk with my source code has long since disappeared.   But it was fun!

In a non-square matrix, what do you even do with the non-square parts? What does it mean to rotate those? Do the values in those cells just disappear as they move into non-existent cells? Do they get replaced with 0s (or NaNs?) that "rotate in" from outside the matrix?

Or do you rotate the matrix itself, changing a 3x2 matrix to a 2x3? Can you do this? If the matrix is in the form of a 2-dimensional C array, you can't change what the caller thinks that array is. I mean, you can pretend it's a 2x3 and everything will work in your rotation function because they're both really just 1-dimensional arrays with syntactic sugar on top, but...ew. I guess this would work if the caller also used a new pointer-to-array-of-the-new-dimensions and cast their old array to it, but still ew.

Am I thinking about it wrong? I've been assuming it's an in-place rotation as that's what most interview questions are (e.g. reverse a string in-place). I guess for some languages that aren't as sloppy as C when it comes to allowing casts, you'd *have* to create a new matrix of the correct dimensions to rotate into. So are copy-and-rotates "allowed"?

Pick a Matrix calculation library, pass the matrix into the "rotation" method/function. Boom! you have the matrix rotated! Never ask the question of how it is done. You will be paid big bucks for focusing your energy on all the other  "really" import stuffs. Let other programmers who knows "how stuff works" do the dirty work for you.

Nothing in the question (as phrased above) says it has to be an in-place operation; you could easily just make a new array, write a couple loops to populate it, and you'd be done.

I agree, the fact that the candidate didn't even try this (or the hard-coding solution someone else brought up) shows they aren't going to be a very good employee.

Libraries have been known to have bugs before. The programmer needs the knowledge to implement the work in order to make sure the work of others is correct.

I have done the same forgetting everything at an interview before even though the question related to work I had done over the last few years. Interviews are stressful.

Direct3D have support for inverting matrices. Do you suggest it's buggy?

It's a great problem, I think I might use it. In my mind, it's not the solution that is important - it's how the candidate approaches the problem

Years ago, when I was hiring entry level, my favorite question was: What's the best programming language? Any response other than "What's the application?" resulted in, basically, "We'll call you". My favorite was the guy that said "RPG". I had to respond "II or III?" as I sent him packing.

I dislike predisposed solutions, always preferred free thinkers, problem solvers: Cabinetmakers, not carpenters.

I hardly think the question was too difficult. It needs to be complex enough to involve discussion, contemplation.

640k, you *do* realize that matrix inversion is totally different (and unrelated) to rotation?

Rotation is a geometric concept, inversion is an algebraic concept. Not even close.

If someone is interviewing for a job in the Windows division, isn't it obvious that they're going to have to do some of that "dirty work" application developers can't be bothered with?

I wonder if the word "matrix" threw off the interview candidate, making him think that some fancy math must be involved.  Of course, that's no excuse for giving up right away.

Well, at least this guy knows what his limitations are.  That should count for something :)

The dirty work is already done. And it's already included in windows.

http://msdn.microsoft.com/en-us/library/aa327415(VS.71).aspx

Hmm, Matrix.Rotate. Very interesting.

Thanks for coming out here 640k, and good luck in your job search.

640K, I only have one thing to say: bravo! *appluading*

I feel sorry for Raymond.  He wanted to create a blog for all things Win32 and, well, programming in general.  But, what he has instead is a blog perfect for analysis by psychologists, teachers, or analysists in general.

I think we have achieved complete communication breakdown.  It's to the point that nobody reads the article anymore.  Just a couple keywords from a glance and we're ready to provide our "expert" opinion.

Are we (Eric and I) the only ones who realize that the question doesn't involve a geometric rotation, but a transposition? Or is everybody being sarcastic?

Because I'm beginning to worry...

> Are we (Eric and I) the only ones who realize that the question doesn't involve a geometric rotation, but a transposition?

Well actually, the problem is not about matrix transposition either (see http://en.wikipedia.org/wiki/Transpose).

The fact is, the operation posed by this question is really not something mathematically significant as far as I can tell. Thus the use of the word "matrix" is not necessary for this problem, so once again, I wonder if the interview outcome would be different if the question referred simply to a "2-dimensional array" rather than a "matrix"?

Come on people, think outside the box.  You could draw the matrix to a bitmap, rotate the bitmap 90 degress, split the bitmap into 16 sections (since we are only worried about 4x4 in this case), rotate each section -90 degrees (i.e. back to vertical), then run each rectangle through OCR software to get the final result.  Was that so hard?

If you rotate it by 10 degrees, it will actually become tricky. You'll have to bitwise-OR those overlapping bits into the bytes surrounding the array ;)

Karellen said:

> In a non-square matrix, what do you even do with the non-square parts? What does it mean to rotate those? Do the values in those cells just disappear as they move into non-existent cells? Do they get replaced with 0s (or NaNs?) that "rotate in" from outside the matrix?

The article at

http://en.wikipedia.org/wiki/In-place_matrix_transposition

should help answer your question (note however that the article talks about transposition, which is not the same operation as the problem above, but conceptually similar).

Basically we take a C++ interpretation of multi-dimensional arrays.

So for example, for a[3][2] in C++, the elements are stored continguously in memory as follows:

a[0][0], a[0][1], a[1][0], a[1][1], a[2][0], a[2][1]

After a 90-degree in-place rotation we interpret the same memory as b[2][3], which stores its elements in the same amount of memory as follows:

b[0][0], b[0][1], b[0][2], b[1][0], b[1][1], b[1][2].

> Well actually, the problem is not about matrix transposition either

No...it is, however, about transposition of elements within a matrix.

I'm wondering if the interviewee misunderstood the question. I've done just enough 3d graphics work to know that geometrical rotations can be done using matrix multiplication, and that I have no idea how to do it. I understand the general concept, but I wouldn't be able to produce the code to do it without some research.

That's no excuse for a flat-out "I can't do it", though. If that was, indeed, the problem, the interviewee should explain why he can't do it, and that should be enough for the interviewer to realize the misunderstanding and clarify the question.

@reader:

As far as I understand, the problem is equivalent to a transposition + a "vertical flip".

I think it must be fairly easy to have the same result with a single algorithm.

However, absolutely nothing to do with methods like "Matrix.Rotate".

Given the confusion, it appears that the best way to start answering the question would be to ask the interviewer what their definition of "rotate" was in this instance.

You have to ensure that you're speaking the same language as the customer, or the customer is not going to get what they want.  That leaves both you and the customer frustrated.

> Are we (Eric and I) the only ones who realize that the question doesn't involve a geometric rotation, but a transposition? Or is everybody being sarcastic?

I'm fairly sure (well I hope anyway) Raymond's being sarcastic when he commented about the 10-degree rotation (which wouldn't make sense in the context of the problem) in response to 640k's Matrix.Rotate in .NET.  To clear that up for everyone else, if they bother to actually look up Matrix.Rotate or try it out, they'll quickly find that it has nothing to do with the operation posed by the interview question.  Once again illustrating the use of tools with no understanding.

One problem with this question is it doesn't specify which subscript goes with x and which goes with y.

Another problem is that it doesn't specify whether the x coordinate increases from left to right (natural) or from right to left (unnatural), nor whether the y coordinate increases from top to bottom or from bottom to top (both of which are natural for different people.)

Otherwise this is a very reasonable problem.  Try solving it with O(1) additional memory over and above the source array (which also serves as the destination array.)

I don't see why the N x M case is any harder than the N x N case, though.

Since the projection of this 1D blob of memory onto a 2D matrix is arbitrary anyway, it'd presumably be easier to instead mess around with the "coordinates" used to index it than to actually move anything around in memory. Doesn't really answer the question as posed, but there we go.

You bunch of wise posteriors sure crack me up.

I have a slightly related pet peeve as well: You shouldn't be a software programmer if you can't un-jam a paper-jammed copy machine.

For Pete's sake the cutting edge copy machine actually shows the step by step instructions to remove the jammed paper, on a pretty LCD display!

And the instructions even include pretty drawings showing which door to open, which button/lever to push etc. A 5 years old could have fixed it...

Here's an idea, get a candidate to un-jam a jammed copy machine.

Eric > I think that's a little harsh. It's possible to have an opinion on what you think the abstractly best programming language is (lisp), while being perfectly aware that it may not always be the best choice for any given application.

You didn't ask what the interviewee thought was best language was for application X, you asked them what they thought the best language was.

Say the interviewee did ask what the application was, you told them, and they then gave an answer - by the same logic you could still fail them for not asking how many people you would be working with on the application and where their expertise lay. It doesn't matter if I think the best language for application X is C++ if I'm going to be working with a team that has all its best skills in Java, and Java is adequate for the task.

Giving someone a trick question like that and then walking them out if they don't give you the magic answer you want is (IMO) just stupid. If I was given a question like that, I'd be expecting that almost any answer would do but that I would then be asked to defend my choice with clear reasons, and - more importantly - to point out deficiencies that I was aware of in my language of choice.

It is slightly ironic that the guy whose blog post Raymond links to got the wrong answer to a counterclockwise rotation. (Instead he does a mere transposition, or mirror reflection about the diagonal). But at least he tried ...

It is slightly ironic that the guy whose blog post Raymond links to got the wrong answer to a counterclockwise rotation. (Instead he does a mere transposition, or mirror reflection about the diagonal). But at least he tried ...

Karellen: It is entirely possible to think there is such a thing as "the abstractly best programming language". It is also, however, entirely reasonable to prefer not to employ people who think so.

(Oops, sorry for the doublet above).

Wow, 640k and Raymond ('s comment)... thank you for the best laugh I've had all day.

For extra credit, do it without using ANY additional memory (requires knowledge of the XOR swap trick.)

Honestly, I'm worried about the people trying to be programmers who can't solve this...

(Solving it without additional memory however would get me thinking too :-P)

That's a HORRIBLE interview question.  Matrix rotation has a clear and common meaning that is not what JeffDav was looking for with this question.  The wording given by JeffDav in the followup is very vague and anyone who has actually dealt with matrices would assume he met, you know, matrix rotation.  The fact that the candidate mentioned matrix multiplication demonstrates that the candidate actually understood the question better than the interviewer!  The punch line for people who actually know matrix algebra is that you accomplish matrix rotation by multiplying by a rotation matrix.

Er, make that no additional memory, apart from the loop indices.

@SomeBody: "Matrix rotation" and "rotate the matrix" sound different enough for someone familiar with rotation matrices to ask "Rotate a vector? Create a rotation matrix? What do you mean?" That's not what the interviewee did; he refused to do any work.

The only thing I would have to criticize is that "All right, well how would you start working that out?" does not help much. I think I would have asked "Well, how would you copy this N x N matrix into another N x N matrix?" and point out the direction you process the elements. But perhaps I'm too much of an educator.

And in Raymond's description, the details of the operation were very clear.

I'm not a fan of programming questions at interviews. Let's face it, it's hardly a simulation of how you'd be doing the job for real - sat facing someone, nervous as hell, when in reality when you come across a problem like that you go and make a coffee, have a ponder, scribble some bits down on a pad, have another ponder and then "ding!" you have the answer. You code it and test it.

Still, anything is better that "What is your greatest weakness?" - that just says to me this person's just finished reading "Employing people - For Dummies"

Since no one else has posted code yet, here is a first attempt to do it in C:

void rotate(int *m, int n)

{

 for (int a=0; a<n/2; a++) {

   for (int j=a; j<n-1-a; j++) {

     int x=a, y=j, val=*(m + n*x + y);

     for (int i=0; i<3; i++) {

       int z=x;

       *(m + n*x + y) = *(m + n*(n - y - 1) + x);

       x = n - y - 1;

       y = z;

     }

     *(m + n*x + y) = val;

   }

 }

}

Please feel free to ridicule it/me and point out what I did wrong... :-)

Let's assume the question was vague, confusing, and completely unjustified.

The candidate can repeat "I can't do it" over and over until they get sent away, or they can ask for clarification.

Being able to ask for clarification is about a thousand times more important than the ability to perform math in your head. Therefore the candidate failed completely.

Also, an interview isn't a "job simulator" and if you think that it is then you're never going to be very good at hiring people. Curiously, writing code is a skill and hiring people is also a skill, ane people with one skill often tend to discount the value of the skills they don't have. I know we're morally obliged to hate "HR drones", but a competent HR person is a wonderful thing, and they're also busy hating "code monkeys" who look good on paper but can't do the job and thus make life misery for the HR department. Life is interesting when you actually respect people who aren't exactly like yourself.

Jonas, what you did wrong was to decide to post code in the first place. The STARTING point of the posting was that the question is NOT HARD and that every reader of the blog is expected to be able to code it one-handed while whistling a samba. (A few test runs are allowed and expected; only a fool thinks he can catch all his fencepost errors simply by staring at the code). Demonstrating that you can do it only proves that you're not an total, utter nitwit -- which was never in doubt. Or at least wasn't before your implicit suggestion that it might be a fact in want of proof.

Oh, and the other thing you did wrong was to spurn the perfectly serviceable array indexing operator that C provides. It is nice and good to KNOW that a[i] is the same as *(a+i), but to write it the latter way just makes the code more difficult to read for a maintenance programmer.

Third, from a readability viewpoint: (1) your choice of names for loop variables do not support the structure of your algorithm well - a and j have similar roles but i is completely different; (2) The name z is misleading; how about nextY?; (3) nextX should be computed early instead of having its expression duplicated; (4) the right-hand side of the main assignment in the inner loop should then be expressed in terms of nextX and nextY.

I *know* the point of the post is that the candidate made no effort (yikes. just yikes.), but...

I am just being dumb but can't you just iterate through the matrix and move [i, j] -> [n - j - 1, i]? No need for any fancy stuff... I know it is probably suboptimal but for the purposes of an interview question seems fine enough to me.

In C#:-

   double[,] rotateMatrix(double[,] matrix, int n) {

     double[,] ret = new double[n, n];

     for (int i = 0; i < n; ++i) {

       for (int j = 0; j < n; ++j) {

         ret[i, j] = matrix[n - j - 1, i];

       }

     }

     return ret;

   }

Bob, it's true that asking for clarification is the right thing to do but we're talking about a kid in his senior year of college.  He was probably super nervous and not very experienced at interviews.  

It takes guts for someone to say "I can't do it" in an interview rather than trying to fake it.  The fact that he started talking about matrix multiplication should've immediately led the interviewer to see that the question was phrased poorly and that the candidate was interpreting it as being about matrix rotation -- after all, it's the interviewer who knows what his intentions are for asking the question.  My interpretation is that the candidate thought, justifiably so, that the question was about matrix rotation, offered up his limited knowledge about matrix rotation (that it involves matrix multiplication), and then honestly stated that that was the limit of his knowledge.  

Of course, I'm basing this judgment off of a few paragraphs in a blog post so this may not represent the reality of the situation.  

oops typo - *am I* just being dumb, not *I am*...!

Actually, I know of a few people that only can do what they've "recited" before. If you change the question a bit (other than the parameters), they cannot do it.

It's kind of frustrating, but people who act like computer DOES exist. And they'll get a job at other companies if those companies are lazy enough to just ask "the common questions", as these people will "answer" (I intentionally don't use the word "solve") the questions perfectly.

you could rotate it using math if you use ^ i'd've thought.

The original question by jeffdav is a very misleading question. It is really about arrays, and yet it uses the totally unrelated word "matrix". You shouldn't expect the interviewee to ask clarification questions because the question is not *ambiguous*, but it is *misleading*. To "rotate the matrix" has a clear definition in matrix theory which is totally unrelated to that intended by the question. So while "I can't do it" is a bad answer anyway, it shows the interviewee has the proper knowledge in matrices - but the interviewer doesn't.

void rotate90(size_t n, double **a)

{

 return a ^ 90; // Use math

}

I remember in old job descriptions, about level 63, it said something along the lines "[developer] can determine that the problem is too hard and unsolvable by him, and seek help from more senior developers". So by this logic, a junior developer could do (or try to do) anything :). But if one says "I can't do it", he is an experienced developer who knows his limitations :)

If just read the story (and if the story is told "as is"), it's the candidate suggest that this is a matrix operation. Both the question itself and the replies of the interviewer doesn't supply the word "matrix" to the interviewee.

Of course, this could be due to the effect of Raymand's auto-correction.

@Cheong: According to jeffdav's comment:

> I would phrase it as "rotate an N x N matrix where N >= 1..."

That is obviously wrong. When you say rotating a matrix it clearly indicates matrix rotation (i.e. matrix multiplication with some rotation matrix). For the purpose of that specific question he should have asked "rotate an N x N 2-dimensional array...".

It's surprising how, when a typically unsuccessful interview is being discussed, commenters always feel the need to solve the problem by posting code.

People, please read all of the comments before you post. A *rotation matrix* not the same thing as *rotating a matrix*. Rotation matrices are for rotating vectors, not other matrices -- it doesn't even make sense.

The linked article (http://geekswithblogs.net/cwilliams/archive/2008/06/16/122906.aspx) shows this example for a left turn:

' For LEFT turns

For Y = 0 to 3

   For X = 0 to 3

       Destination(Y,X) = Source(X,Y)

   Next

Next

This looks more like a rotation to me!  Should probably be Destination(Y,3-X)...

Interesting blog post :)

Actually, a set of eigenvectors forms a matrix, typically square. And rotating them makes perfect sense. It's not what this question is about, though. I can see how the interviewee got confused.

The Matrix.Rotate function mentioned above (http://msdn.microsoft.com/en-us/library/aa327415(VS.71).aspx) is rotating aorund the origin, not the center of the matrix.

@Maurits

Too easy. For extra, extra credit. Solve it without actually moving any of the array elements at all.

I actually introduced a bug in a graphics lib of mine(a bimap is just a big matrix) that did just this. I mistakenly switched the y and x in a function so the images came out turned 90 degrees (puzzeling my co-workers).

Maurits:

I had to look up Wikipedia's definition for that - I'd never thought to use XOR that way. Handy!

I'm still figuring out how to apply that technique to this problem; in a discrete set of values changing positions (say, the corners), I understand how to apply it, but not in a manner that's loop-friendly (and while I could hard-code it, I want to try for the <I>n</I>-size solution)...

A working relationship is not really a competition. Perhaps it can be, but I just think it leads to high class garbage.

I don't think it matters what questions you ask at an interview, but if you make it like a competition, you're not going to find out what the person is like when they're most productive.

Perhaps the mistake that this person in the spotlight made, was not to simply stand and walk away.

FWIW, I can understand that this person could have answered the question but thought they could not.

Use the force.

:))

@Some Guy

Not really all that handy.  If you read the "Reasons for avoidance in practice" section, you realize that this trick is not so great afterall.

It's only handy in very specific environments like those with insanely restricted memory allowances.

Even in extremely memory constrained environments (or strange pure architectures), you only need to know it if you code in assembly because every sane compiler will use a register for the temporary variable. And beside this if you're thinking at this level you'd better have a reason or you're prioritizing useless micro-optimization over other issues.

Beside that you can also do that with subtraction/addition:

SWAP(A, B):

A = A - B

B = B + A

A = B - A

with the disadvantage of a less "guru" feeling but the great advantage of being applicable also to floating points (where the temporary variable is preferrable anyway).

Xor trick for floating point with subtraction and addition? No, no, no, no! If the two numbers have dissimilar magnitudes, the smaller one will be lost in rounding noise.

I have trouble imagining that the advantage of saving a register can reasonably outweigh the cost of documenting the requirement that the magnitudes must be similar, plus the cost to future programmers of reading and internalizing that documentation, plus the cost of future bugs that arise when maintenance programmers inevitably fail to read and understand it.

In fact, I have written "(where the temporary variable is preferrable anyway)" exactly for that reason.

Sub/Add trick is "applicable" for floats.. where XOR cannot (without casting which brings anything to its knees). From this to go to say it's a good way to swap it is a far jump. I'm strongly opposite to it as well as to the XOR trick. I can see a reason to use it in some contexts like shaders but probably shaders support some sort of fast swap anyway.

Readability issues arise both for that and the XOR one and those are mostly programmers trying to outsmart themselves.

Unless your job specifically requires so, using it is something something programmers with not much self-esteem do to show others they greatness [just in a different way from teenagers going on the rear wheel only without helmet on their motorbikes to show they have the "courage"].

Have anyone actually read the definition of matrix rotation?

http://en.wikipedia.org/wiki/Rotation_matrix

It's not that simple after all. Please read it before trying to solve completely unrealated problems.

This story is a bit unbelievable, the probability is that Raymond has removed some vital dialogue to make the story more funny on the expense of the interviewee, it was after all "two years ago" and Raymond "got some details wrong".

The interviewee asked for clarification, suggested it was about "matrix multiplication".

Which actually CAN solve matrix rotation. To demand an interviewee to answer such complex question without time to prepare and studying is niether nice or good for the company.

If I had found out HR on my company used this kind of trick questions the interviewer would probably have to answer for his behaviour.

One swap instruction would be both cheaper and clearer than 3 xor instructions.

Why read something that has no relevance to the problem at hand?

Anyway, good luck delivering a product with a team of "I can't do it"s. Heaven forbid that interviewers draw any connection between what a candidate does in an interview and what he might do on the job.

It's a typical problem, the question is truly misphrased but that does happen.

This is also a typical old-style Microsoft problem, where the interviewer has it in their head but can't explain it.

So a smart candidate figures it out. That's the goal of these questions.

Things like XOR-swap are just useless in my opinion, as are most 'puzzle' questions.

You can idiot-savant these types of problems and their applicability is very low.

I tended to do well at them, if you hit one you know then you don't jump to answer but instead play out the 'discovery' long enough to get by

The interviewer's built in expectation of time (bs filter).  They are a good waste of interview time.

Fools! You laugh at what you do not understand!

And as usual Reymond try to redefine a well defined concept (matrix rotation in this case).

"For example, the entry in the upper left corner of the array goes to the upper right corner."

Isn't the biggest clue the fact that we start to talk about 'corners' going from upper left to upper right?  As far as I remember, a matrix does not have 'corners' - we are talking about something general and non-mathematical.  That should be obvious.  We are not talking about using a matrix to rotate something else or finding a matrix that satisfies a particular obscure mathematical property.  It's something simple.  

What makes some people naturally assume the most complicated scenario they can construct...?

"And as usual Reymond try to redefine a well defined concept (matrix rotation in this case)."

And as usual you tried to be the king of the trolls, but ended up being the laughing stock.

(your Matrix.rotate() post was comedy gold, however)

A C# solution that recursively swap the array, moreover you can just change the angle to other angles 180, 270, by writing the function GetTargetPosition

static void RotateMat(int[,] arr, int n)

       {

           for (int i = 0; i < n / 2; i++)

           {

               for (int j = i; j < n - 1 - i; j++)

               {

                   int newi = i;

                   int newj = j;

                   GetTargetPosition(ref newi, ref newj, n);

                   SwapRecursive(newi, newj, i, j, arr, n);

               }

           }

       }

       static void SwapRecursive(int i, int j, int starti, int startj, int[,] arr, int n)

       {

           if (i == starti && j == startj)

           {

               return;

           }

           int newi = i;

           int newj = j;

           GetTargetPosition(ref newi, ref newj, n);

           SwapRecursive(newi, newj, starti, startj, arr, n);

           int tmp = arr[newi, newj];

           arr[newi, newj] = arr[i, j];

           arr[i, j] = tmp;

       }

       static void GetTargetPosition(ref int i, ref int j, int n)

       {

           int tmp = j;

           j = n - 1 - i;

           i = tmp;

       }

@lorenzo your soultion is not workable

I will use this question in every interview from now on!

Reading from the answers of this post you are quite sure to kill:

- nitpickers

- closed minded people

- people going panic under pressure/stress

- idiot savants

- prima-donnas

- people with very small problem solving abilities

- people with no self esteem

- people with too much self esteem

Tha would make it the ideal interview question!

The problem statement is not complete; you need to specify what corner is (0,0). If it is the top left, rotating clockwise means moving (x, y) to (max_y - y, x); if it is the bottom left, rotating clockwise means moving (x, y) to (y, max_x - x).

You can also see how to solve it without extra memory if you look at it this way, a rotation is a flip over the horizontal middle (or in the second case the vertical middle) and a diagonal flip combined.

>> The problem statement is not complete

This is even better!

When a someone asks you something it's up to you to dig further details if you think you need them to solve the problem.

With the possible exception of Bob, I would not hire any other poster here...

The case, as stated, is ambiguous. I couldn't tell the you the last time (if ever) I received an unambiguous requirements document (or use case).

I *want* anybody I hire to have the guts and smarts to push back, ask questions, clarify and gain as much insight as possible on the problem before proposing solutions.

Everybody here has tossed their solution, based on *their assumptions* about what the problem really was to begin with.

Was it "matrix" or "array" manipulation? ASK THE USER AND CLARIFY the request. That's what I want to see in a candidate.

That's what makes this such a good question: It's not the solution proposed - it's how the candidate approaches the problem.

I can get 1000's of idiots to code a detailed design spec (assuming I ever write a perfect one). But the basis of problem solving is problem definition and that can't really be taught. I'd take 1 really good analyst who can code over 100 good coders that can't analyze.

PingBack from http://blogs.msdn.com/oldnewthing/archive/2008/09/03/8920995.aspx

"I *want* anybody I hire to have the guts and smarts to push back, ask questions, clarify and gain as much insight as possible on the problem before proposing solutions."

And while the guy you hired is still asking questions to clarify a simple problem, the guy I hired showed initiative and did the right thing, producing a working solution without me having to babysit him.

Eric: "The case, as stated, is ambiguous."

1. Write a function that takes a 4×4 two-dimensional array and rotates it clockwise by 90 degrees.

2.  For example, the entry in the upper left corner of the array goes to the upper right corner.

What, exactly, is ambiguous about these 2 statements?  I'm interested to know, since it's blindingly obvious what the guy wants.

There are some potential gotchas involved in the obvious solution, but you say that you cannot understand what is even required in the first place.  Why is that?

Funny story here. But why is everybody complaining about the choice of the word matrix instead of 2d array?

I work with rotation matrices a lot and didn't even think of them until reading the comments. IMO, it was perfectly clear from the problem description that the task is to rotate the matrix elements and not to build a rotation matrix.

After all, it is suppossed to be a programming problem. Knowing how a rotation matrix looks like clearly doesn't fall into that category.

This is an initial "warm up" question for college interns and out-of-college new hires?  To me, this question is the interview equivalent of meeting your blind date for the first time and going straight for the bra.

I'm not surprised if the guy was a little stunned by this "easy" question especially if it was presented to him with an attitude of "Let's start off with an easy one...".  It doesn't mean he was an idiot and I bet he could have answered the question if given the time and space but jeeze...  

How about a little "What is polymorphism" or "Write some code to do a deep copy of this class I will provide for you" to set the mood before jumping straight into matrix algorithms?

I was going to post something about this topic, since the ambiguity of the question offered some comic material, but then I read most of the comments, and decided not to.

Oh, why, hello, Dr. Gödel! No, no, I don't see anything wrong with the above statement...

Here's my version to rotate 90 degrees clockwise:

n = 4

input[n,n]

output[n,n]

Code:

for (int y = 0; y < n; y++) {

for (int x = 0; x < n; x++ {

output[n - y - 1,x] = input[x,y];

}

}

I think someone already posted this, however.  It sounds complicated, but as soon as you draw a quick diagram the simplicity of what you are doing becomes apparent.

The correct solution is to give the examiner the URL to your cute Rubik's cube demo!

I guess I would have failed the interview, sorry.

I just tried to resolve the problem now, and despite having succeeded, I guess that under stress, like for a job interview, with someone above my shoulder monitoring every breath I take, my mind could well go blank but for the "Why asking me some brainf*ck question?" thought mixed with "what was that math algorithm I guess I used in a similar problem 9 years ago when I was working at that image processing lab because I don't want to appear so dumb I can only produce some hack for a solution?".

Now, the whole "this is impossible" was silly, I agree: If you can do it with, say, a 3x3 example, then you can do it on a computer for NxN.

But still, I agree with Odie:

The easy, warm-up question would have been to test my knowledge of languages, and the languages patterns and idioms, how I handled personal projects, my experience of bugs, of good and bad habits in coding.

But I guess these questions were either already asked, or would have been after.

So, bad luck...

As for the "2D version of string reversing", I disagree: The 2D version of string reverse was the first solution I found, and this only resulted in a mirrored 2D matrix along its principal diagonal. I had to "hack around" this false solution to find the right one.

The XOR trick is pointless today.

No, seriously. You can do it without taking up any additional memory using swizzle instructions on vector registers these days, and you'll do it faster than doing it the XOR way.

I honestly can't think of any CPU that's floating point register starved enough to make it a good idea these days.

Memorize the URL of the hacker's delight website, and you've got all the ammo you need for bit fiddling - and please, promptly forget the XOR swap trick.

Actually, forget XOR entirely unless you're writing some kind of hash function, or a compiler.

PingBack from http://polymathprogrammer.com/2008/09/08/rotating-a-matrix-cannot-be-done-with-matrix-multiplication/