Fog Creek Software
Discussion Board




YAIQ

(Yet Another Interview Question)

Given that code is read more than it is written I wonder whether that shouldn't be tested as well or even instead of writing code, which is a pretty hard thing to do in the pressure of an interview. What I'm thinking of is "Here's a function, please comment it."

You could even give everyone different functions to comment and so get your codebase fully commented :©}


Tuesday, February 24, 2004

I had an interview one time where I had to find mistakes in source code.  Stuff like:

if ( x = 42 ) {
//whatever
}

// Return the value 5
void f( int i ) {
i = 5;
}

It was pretty simple but definitely tested my knowledge of the C language.

Bathmophobic skier
Tuesday, February 24, 2004

In my last interview, in additiion to writing code, I was given code and asked what it does.  Sure, it's completely valid.   

Immature programmer
Tuesday, February 24, 2004

As I pointed out in another thread recently, it is important to test for broad skills, not specific trivia. 

I often put completely broken code up on my whiteboard and ask candidates to critique it.  But the code never is broken because of trivialities that a good "lint" program would catch.  Rather, the program I write has a host of security, portability, maintainability and usability design flaws in about five lines of code. 

Anyone can tell you that scoping your variables poorly, or putting expensive checks in loop conditions, or using = instead of == is bad.  I need to hire people who can look at syntactically perfect code, determine that it is poorly designed, and know how to fix it. 

I need people who can say "this cast isn't portable to 64 bit systems, that counter is going to overflow if the server runs more than 30 days without a reboot, a hostile client could corrupt another client's record here -- but we can solve these problems by implementing a hash table in the following manner..."

Another thing that I like doing is getting the candidate to write some code and then I say "make it better".  Bad candidates immediately start tweaking the code.  Good candidates ask me what I mean by "better" -- faster, more portable, more readable, smaller object code, more testable, more usable, more easily localized?  Good candidates realize that we write code that will be used in different ways by the compiler, developers, testers, localizers, educators, and most important, the end user.

Eric Lippert
Tuesday, February 24, 2004

I'm with Eric here, but I _also_ want people to demonstrate their ability to decode cryptic code. E.g., what does the following function do?

int f(int a) {
. int b;
. for (b = 0; a; ++b) a&=~-a;
. return b;
}

It's "concentrated"; It actually does something useful, somewhat efficiently, in a short piece of code, that requires coding talent to decode (but only "common knowledge", or rather, knowledge that _should_ be common).

It isn't characterstic of real systems - usually, the cryptic innards are spread over pagefulls of code. But I feel it is representative of the effort required to understand existing systems.

When I give this question, I want to see the person reasoning about it if he doesn't decode it quickly - it's not a pass/fail question.

And of course, it is just one of many.

Ori Berger
Tuesday, February 24, 2004

s/if he doesn't/if they don't/

Of course.

Ori Berger
Tuesday, February 24, 2004

It counts the "1" bits in a.

It's really quite amazing - it knocks off "1" bits one after another, and doesn't even loop through every bit.

I.e., if it gets an argument with only 3 bits set, it will only loop 3 times. Did you come up with this? I could never do that in a million years.

Beautiful.

Alex.ro
Tuesday, February 24, 2004

Alex.ro it is similar to Brian Kernighan's method:

for (b = 0; a; b++)
{
  b &= b - 1;
}


Wednesday, February 25, 2004

Ori - that was exactly the kind of thing I was thinking of.


Wednesday, February 25, 2004

Ori, what do the dots mean?

eg  . int b;

[Its been 15 years since I used C professionally. I know I *should* look it up, but I'm supposed to be working]

Justin
Wednesday, February 25, 2004

Dots are a habbit from the days that the JOS forum software stripped the spaces in the beginning of the line; In those days, it was impossible to post indented code.

    These days seem to be gone now :)

(It won't compile with the dots).

Ori Berger
Wednesday, February 25, 2004

Alex.ro: I don't recall exactly. I think I saw Kernighan's b&(b-1) method, and added the ~- obfuscation myself. (I'm not too sure of that either - it was 12 years ago or so).

And if you like that, what is the following function supposed to do:

int f(int a, b) {
  while (a %= b ^= a^= b ^= a);
  return b;
}

What's wrong with it? What condition is required for it to work?

Ori Berger
Wednesday, February 25, 2004

Does it return the original value of a? The XORs are just a cryptic swap(). The loop doesn't.

As to what's wrong with it, although assignment groups right to left for precedence purposes, the order of evaluation of sub-expressions is not guaranteed. So (treating the compiler as a black-box) you can't know at what stage the assignments will take effect.


The code examples in this thread trouble me. It's very rare you want someone who habitually parses this sort of code (unless perhaps you are writing a compiler).

I've worked on 1MLOC embedded systems and never seen anything this "bad". You might even put off good candidates who are more interested in understanding requirements and solving real problems than playing with the boundaries of the C standard(s).

MugsGame
Wednesday, February 25, 2004

On compilers that actually compute side effects by grouping, this will return the greatest common divisor of a and b. However, as you mentioned, the standard states that the order of side effects is undefined, and therefore so is the value of this function. (Not even the swap is guaranteed to work)

I go to great length to make sure that interviewee understands this is NOT how our real work looks like.

However, I've yet to find a good test, short enough t do in an interview, that would indicate how a candidate will chase problems in a 1MLoc system. Both questions I posted above require "common knowledge" I expect of a competent programmer with C / C++ experience, and the ability to understand what a program is doing. It's different when the program is longer, but not much different - after you work on a system for a while, fopen() or winograd_fft_17() become as indivisable as "&" or "~" are; And their composition conceptually similar to this kind of composition, with interactions, undefined boundary conditions, etc.

That said, I keep looking for ways to improve my interview process - if you have suggestions, I'll be glad to hear them.

Another interview question I use (one which I do not plan to solve publicly here - if no one solves this in the forum, and you want the answer, email me and I'll reply):

In [a simplified version of] the game of MasterMind, one player chooses a number made of the four digits 1-9, all the digits being different; The second player guesses a 4 digit number of the same form.

For every guess of the second player, the first player answers with the number of Direct Hits ("Bullseye"), which means the right digit at the right place, and the number of Indirect Hits, which means the right digit, but not at the right place. The objective of the second player is to guess the first player's number - that is, achieve 4 Direct Hits.

E.g., if first player chooses 3145, the second player guesses 4567 then the first player reports 2 indirect hits (4 and 5, both in the wrong place). The second player might guess 2345, which results in 1 indirect hit (3) and two direct hits (4,5) -- and so on.

Your mission, should you choose to accept it, is to describe an algorithm for playing the part of the second player (the one that makes the guesses); it should come with an estimate for the program length (in lines of code) and how long it would take to code (just the algorithmic part, no GUI needed).
This message will self destruct in ..... .!@#!% ^ NO CARRIER

Ori Berger
Wednesday, February 25, 2004

Hi Ori,

Isn't the MasterMind algorithm widely available? I founds a few immediately with Google.

Or are you counting on the 'element of surprise' during the interview?

The thing is, if I was asked that an interview, I would slip into a thinking trance for about 15 minutes -- is this an acceptable interview 'scenario'?

I never tried to solve the Mastermind problem myself, although I played the game as a child. We had numbers (9 digits, not 6 colors), but the principle was the same.

Oh, and for your amusement, the game was called "Bulls and Cows" (Bulls having been, presumably, derived from Bullseye, and Cows probably seemed a natural complement :)

Alex.ro
Wednesday, February 25, 2004

I wasn't aware it was _that_ widely known; Last I searched (a few years ago, admittedly), there weren't many references.

15 minutes are reasonable. I also offer to leave the room if I feel that will ease the interviewee.

And -- the first question I ask is "please write on the blackboard a routine to reverse a singly linked list". About one in ten _prescreened by resume_ candidates gets this one right, and not all the get it right get it right the first time. If my candidate knows the mastermind algorithm in advance (and can really explain the implementation, not just quote something), it'll work in his favor. So far, and I have interviewed tens (perhaps more than one hundred, all prescreened) - and no one has.

And about reversing a linked list, those of you who pass it off as "too easy", you may be right - but unless you're 100% certain, do the following experiment:

Write it down on a piece of paper, say

struct link {
    int data;
    struct link *next;
};

struct link * reverse (struct link *head) {
...
}

(feel the ....)

Stop reading here, and come back when you've done that.










I mean it. Stop reading here, and come back when you've  done that.







Take your time, don't rush it ....







Ok, now -  test it live. Does it work on a 5 element list? Does it work on a 1 element list? Does it work on empty lists?

Supposing everything works, what is the time complexity of your solution? If it's more than O(n), rewrite it. What is the space complexity? If it's in-place and more than O(1), rewrite it. (e.g., if you wrote it recursively, you shouldn't have - unless you (as a candidate) can explain how you verify that the compiler eliminates tail recursion, and mention yourself that you would have done that). If lit's longer than 6 lines, rewrite it (it's probably wrong too - there are several "philosophical" explanations about how the solution works, but down to the metal they are all the same, and none is longer than 6 statements).

Once you're done, ask your colleagues. You may be in for a big surprise. I was.

Ori Berger
Wednesday, February 25, 2004

s/feel the/fill the/g

(Another vote for editable posts!)

Ori Berger
Wednesday, February 25, 2004

I am leaving this company for a new job elsewhere.

People are in near-tears to see my go.  I am well regarded in this community on my skills to provide a solution (programatically).

But I will FLUNK an interview that is like what you are proposing.  Why?  I hate tests.  I HATE HATE HATE HATE HATE HATE tests.

But I can solve any business problems that baffles most people.  I solve problems.  I do not solve test questions.

The reason I'm working for my current company is because they're not dumb enough to ask me what polymorphism means.  I walked out of interviews when I get asked questions like that.

T.J.
Thursday, February 26, 2004

T.J: How would you select one of 50 candidates? You have to apply some method of ranking the alternatives, whether you call it a test or not.

And just to remove doubt - When I interview, it usually takes close to 2 hours; I try to evaluate experience and general coding skills/knowledge in the first hour, and insight and problem solving in the second. The first part has much less weight - but the interviewee is expected to demonstrate reasonable competence. I also adapt the test as I go, choosing my questions, examples and terminology to those that should make the candidate feel "at home", in the hope of reducing the stress factor.

Ori Berger
Thursday, February 26, 2004

*  Recent Topics

*  Fog Creek Home