Fog Creek Software
Discussion Board




Poll

How long would it take you to write the code to reverse a link list?


Monday, August 16, 2004

given my choice of language, my choice of library and my choice of list, hmm, about two minutes, incl. testing.

And this answer is meaningful how?

i like i
Monday, August 16, 2004

list<int> L;
L.push_back(0);
L.push_back(1);
L.push_back(2);
L.push_back(3);
L.push_back(4);
L.reverse(L.begin(), L.end());

I don't know - I didn't time myself.

Yet another anon
Monday, August 16, 2004

>And this answer is meaningful how?

I asked myself the question and the answer I got was 20 min. I couldn't imagine writing the struct declarations and the reversal code in anything less than 20 min. I wanted to check if my answer was close to the average.

OP
Monday, August 16, 2004

The question verges on meaninglessness.

If the circumstances requiring this operation were foreseen the list should have been linked both forwards and backwards - a double ended queue where the reverse traversal is always available.

If it is an adhoc reversal, dump to cards, then put the topmost card face up on the table alongside the heap, the next topmost on top of that card and repeat until all the cards have bee transferred. Clear core and reload. Duration depends on operator availablilty.

trollop
Monday, August 16, 2004

>If the circumstances requiring this operation were foreseen the list should have been linked both forwards and backwards [snip/]

You're right. It is a typical question asked in Microsoft >HR< phone interviews for the SDE position, hence the question is open-ended, and so is the answer prone to volatilities of magnitude, I would guess.

OP
Monday, August 16, 2004

if it is a double linked list, why reverse it?  Why not just traverse it backwards?

i like i
Monday, August 16, 2004

You miss the point by asking *why* one would do this in a doubly-linked list, or by using libraries like the STL.
  The point of this question is to test whether an interview candidate can track the boundary conditions (test for null), and swap all the appropriate pointers/references in whatever language. True, he'd never do this by hand in the real world; but if he can't write this simple code in under 20 minutes, then he's almost certainly a no-hire.

Sexist
Monday, August 16, 2004

>if it is a double linked list, why reverse it?  Why not just traverse it backwards?

You're right. If I understood correctly, that was what trollop's first implied argument was.

From what I learnt, the question does not specify the type of linked list you're asked about. Hence, the interviewer may also expect outrageous computational differences in answers depending on the method followed.

OP
Monday, August 16, 2004

Why wouldn't an interviewer ask the candidate to write the kind of code they would actually write in their job?

For example when interviewing candidates for an ASP job a while back I asked candidates to write out on paper some ASP  to query a database and display the results on a web page. Since that's the kind of thing they will be doing everyday.

Matthew Lock
Monday, August 16, 2004

1. notepad
2. set font to arial 18, italic
3. enter the world ojojojojoj

Maytag Repairman
Monday, August 16, 2004

OP, you're not alone. If you mean C, singly linked list, I needed an hour, did it wrong, then 20 minutes to do it right.

So Joel wouldn't hire me either, if that's any consolation.

There was a post here a while ago from Ori Berger about this.

Alex
Monday, August 16, 2004

That depends, am I being paid by the hour?

Mr Jack
Monday, August 16, 2004

>Why wouldn't an interviewer ask the candidate to write the kind of code they would actually write in their job?

From what I read, it makes enormous sense to ask this question. You must reckon that this question has been asked by an HR representative during a phone interview. The interviewee blogged that the intent with the questions in the HR interview is to ascertain the political compatibility of a candidate within the organization.

Generally, the questions in this interview are of a psuedo-technical nature wherein the answers to them are short and not necessarily black-and-white. The answers are normally told before hand to the HR person, who may or may not understand the question himself/herself. The round is to weed out the applicants that fall below an acceptable level of IQ/aptitude.

The HR phone interview is followed by a technical phone interview where bits and bytes are exchanged on phone. There, it gets down to the brass on the tracks, and you can really work around the specifics.

OP
Monday, August 16, 2004

>OP, you're not alone. If you mean C, singly linked list, I needed an hour, did it wrong, then 20 minutes to do it right.

Hey, Alex! That was exactly what I had in mind. A singly linked list in C. I see we concur on many ideas in our previous posts (I am a regular on the forum, anonymous for this post).

OP
Monday, August 16, 2004

why the blip ...

trollop
Monday, August 16, 2004

>why the blip ...

That's because the purpose of posting anonymously was to garner serious responses. When I post in my name, the post is either deleted, or is hijacked, or gets only lukewarm response. This has been observed lately. Earlier, it wasn't that way. Otherwise, I don't see reason for staying anonymous.

OP
Monday, August 16, 2004

1. Write items in list to tape, with item number.
2. Run Tape Merge Sort (Descending) on the item numbers.
3. Read items from tape, building the list in reverse order.

Murg
Monday, August 16, 2004

Sathyaish, it IS you!

muppet
Monday, August 16, 2004

Yeah!

Sathyaish Chakravarthy
Monday, August 16, 2004

I think when HR asks your questions like this, it isn't to find out how competent you are, it’s to see if you lied on your resume.  Some people read that you need C++ experience for a job.  They remember that while they were programming in BASIC 15 years, they saw a book on C, so they put C++ down as something they know.

So, HR asks you to reverse a linked list; then they sit there waiting to hear the word "pointer".  They have no other way of knowing how good you are, but if you say "Umm, I would undo each link, turn it around, and put it back" then they know to throw out your resume, otherwise they can pass it on to someone who might be able to judge your abilities.  Given the number of people who "tailor" their resumes to fit a job description, it’s not unreasonable.

Steamrolla
Monday, August 16, 2004

I can't conceive of this practice.  I mean, I pad my resume a bit (everybody does, you have to, in order to compete), but I do so by overstating experience here and there by perhaps 20% or less.  I'd never dare put on a resume that I have experience with XYZ unless I was confident that I could answer questions about it in an interview.  At an actual interview, I make liberal use of the phrases "I don't have first hand experience with that, but I know where to find the information."  or "I've only used that technology in bits and pieces, so I wouldn't say I'm an expert."  I've had no trouble landing jobs, being honest.  Most employers seem to appreciate my frankness.

What good will it do you to BS your way into a position?  Are you looking for a week's pay?  Maybe two?  Before they discover you and you're out on your ass, possibly with a civil or criminal case on your back for fraud?  Why bother?  If I tell an employer that I'm a C++ guru (I'm not, when you people talk about linked lists my eyes glaze over, even though I know what they are), and then I can't cut the mustard once they put my ass in a desk, what's the point?

muppet
Monday, August 16, 2004

" I mean, I pad my resume a bit (everybody does, you have to, in order to compete), but I do so by overstating experience here and there by perhaps 20% or less."

Is it true that everyone does this?  I never have personally, but if most everyone else is, then that may explain a few things.

I will admit to converting projects into buzzwords to make it through HR filters though.

Steve Barbour
Monday, August 16, 2004

"I pad my resume a bit (everybody does, you have to, in order to compete)..."

Strange.  I've had more success by communicating the value I place on integrity.  Prospective employers seem to like that quality -- go figure.

YMMV
Monday, August 16, 2004

i ask a similar well-known simple programming question during interviews. amazing how many people just cannot do something simple like this.

mb
Monday, August 16, 2004

"I will admit to converting projects into buzzwords to make it through HR filters though. "

This is essentially what I meant by "padding."  That and rounding off experience to whole years.

muppet
Monday, August 16, 2004

Why do you ask?

TheGeezer
Monday, August 16, 2004

Well, here's my 2 cents. I was curious how long this would take me, since I'm more than a little rusty with C (I haven't written a significant C program in probably 3-4 years).

It took me 15 minutes from start to finish, including some basic testing. I made a couple of really stupid typos in the first draft (I had a * where I wanted an &), but once I fixed that, the code compiled and ran on the second try.

This seems like a pretty good bozo test to me. I probably would have given myself a passing grade if I'd done this in an interview. The incorrect use of "*" was a pretty dumb mistake, but I did catch it pretty quickly (besides, the compiler gives warnings for a reason).

-Mark

Mark Bessey
Monday, August 16, 2004

All of 5 seconds.

List.rev theList

that is all.

/smug fp weenie

alricb
Tuesday, August 17, 2004

10 minutes.

.
Sunday, August 22, 2004

*  Recent Topics

*  Fog Creek Home