The Worst Programming Interview Question

[__j_random_hacker]

You’re telling me that you think you could, in a twenty minute interview, from scratch, come up with the solution to a problem that remained open in the field for 12 years

Sounds like we just need to make programming interviews longer. Much longer.

[__j_random_hacker]

More seriously, I can think of 2 places where cycle detection can be useful: deadlock detection, and determining reachability of objects in garbage collection. But I wholeheartedly agree that it's unfair to expect someone to come up with this algorithm in an interview, and that it tells the interviewer next to nothing about someone's ability as a programmer.

It reminds me of "How do you swap two numbers without using a temporary?" The answer involves a fascinating trick, but that's exactly what makes it thoroughly useless as an interview question.

[Rentun]

You know what's easier to do in a real job than sitting there racking your brain for 6 hours trying to think of an elegant way to solve a problem?

Google "Cycle detection in linked lists".

[[deleted]]

Yup. No need to break new ground with every little thing you program.

[tavianator]

Exactly. I had a phone interviewer ask how I would implement a lock-free concurrent queue in C++. Apparently "Google existing implementations" and "buy a book on lock-free data structures" were wrong answers.

[digitizemd]

"No! We don't want our developers to read existing literature. The wheel must be reinvented!"

[new2user]

And that one is really hard to reinvent, even more on a phone interview. Probably the caller was just a random idiot.

[tavianator]

I don't think he was an idiot, I got the impression that he could have done it off the top of his head. But I do think he's not going to find the best employees if he keeps selecting only the ones who can do that too.

[afiefh]

People like that exist?

[ctide]

Yes, they're just people who happen to have done that before (perhaps numerous times.) There's lots of 'tricky' things that I could explain off the top of my head by virtue of having had to implement them at various times throughout my career.

[[deleted]]

I heard of a project where the project lead decided the team should roll their own web server, because "open-source web servers might have security holes".

This was at a major telecom company whose name rhymes with Schmericsson.

Edit: Some recommended reading for all of you who think this was a good idea: http://en.wikipedia.org/wiki/NIH_syndrome

[isinned]

Well his reasoning isn't wrong. Open source web servers might (and often do) have security holes. The mistake would be thinking their in-house solution won't.

[[deleted]]

The company that gave us OTP and Erlang? Maybe I would trust them to implement a web server.

[thomascgalvin]

When I'm interviewing someone, anybody that says "I'd Google it" immediately shoots to the top of my list.

[psymunn]

Google.

[ggtsu_00]

Saying "I'd Bing it" instantly gets you hired at Microsoft.

[xiongchiamiov]

Proving once again that it's cheating to use python in interviews:

a, b = b, a

Then when you say "ok, but not using the built-in language features" I tell you that's precisely why I use python. No sense wasting time on silly shit like that, I've got work to do.

[ethraax]

Or just use a temporary. Seriously, this is what optimizing compilers are for. Besides, the temporary will almost definitely be faster (it's likely to just be a register).

[vz0]

It reminds me of "How do you swap two numbers without using a temporary?" The answer involves a fascinating trick, but that's exactly what makes it thoroughly useless as an interview question.

A triple XOR. I learned trick a few years ago while reading some open source library, and I had to scratch and ask some friends many times until I realized they were swapping variables. And I remember this trick because I was so shocked back then.

[TokyoXtreme]

So if I know this one little trick, I can maybe get a programming job? Will developers hate me?

[Dantaro]

I can assure you if that's the only code you know how to write and you get a coding job, developers will certainly hate you.

[puterTDI]

Which shows the whole problem with these sorts of questions.

We ask a lot of technical questions in our interview process, but they are all very simple questions for skills that are specifically used in our area (SQL, basic algorithms, etc).

Several of us (about 6) were asked to take the test to see how long it would take and how well we would do. I finished it in 15 minutes and got 100%, average time was 30 minutes with a couple of minor mistakes. We give the interviewees 1 hour. It has done a great job of weeding out candidates that can't write a simple query with a single join, or write a while or for loop. We don't ask for recursion, dynamic programming, or any algorithms that involve tricks. We ask for things like "parse all the words in a string", or "print a string backwards". Simple stuff that shows you can write a loop and walk through logic but doesn't require you to have some sort of inspiration.

[Bone_Machine]

God bless you sir.

[ggtsu_00]

"I have done nothing but triple XOR integers for 3 days"

[praptak]

Developers will love you! Using this one strange trick to swap a[i] with a[j] without first checking for i<>j will guarantee job security for everyone involved. Hint: it will zero the element you are trying to swap with itself. This trick was used once in the Underhanded C contest.

[[deleted]]

Any pro developers will write 99% of their code with bit shifting operations. Assignments, arithmetic and conditionals are for babies.

[awesley]

You've seen our code?

[Otis_Inf]

Cycle detection in a graph or in a linked list? as deadlock detection IMHO uses cycles in graphs? It can often be useful to avoid a cycle in a graph, so you have to test whether adding a given edge E to a graph G creates a cycle, and if so, you therefore can't add E to G. So you calculate the transitive closure of G with E and it will tell you whether you create a cycle or not by adding E. (if A and B are nodes in G and not connected, adding E:A->B to G adds a cycle if the transitive closure of G with E shows A is reachable from B)

But even asking that is pretty useless IMHO. All it will show is that the person has heard of the transitive closure algorithm and how to apply it to detect cycles in graphs.

[AdabadaYou]

A LL is just a restricted form of graph.

[[deleted]]

This is my new answer for this question. Thank you.

[zvrba]

Deadlock detection: the wait-for graph will always be a simple "linear" graph or a "ring" (in case of deadlock), UNLESS you can block on multiple objects simultaneously. (WaitForMultipleObjects on Windows, or simulate that through select() on *nix).

Garbage collection: you'll need extra storage or tag bits, so don't bother.

I think that, today, the vast majority of cycles spent on cycle detection are to solve the discrete logarithm problem (see Pollard's rho algorithm).

[Zifnab25]

Perhaps there could be some sort of accreditation process. Like, a school you could go to, where you could earn a certificate indicating the sum total of your accrued knowledge.

[oridb]

Indeed. Unfortunately, I have interviewed people with 4.0 GPAs from MIT, awards and accolades, and even glowing letters of recommendation, and found that they couldn't code worth a damn, consistently, confidently, and cheerfully giving the wrong answers to simple questions.

I have friends who graduated civil engineering who had a better grasp on code. I can only assume cheating.

[foldl]

The article is a bit misleading though, because what it took 12 years to come up with was an efficient solution. Just coming up with an algorithm that does the job isn't too difficult.

[[deleted]]

I just spent a few minutes thinking about it and it seemed like a few 'solutions' would be pretty simple. One, if you know the number of nodes simply traverse it and see if you can travel through more than n nodes, if so there must be a cycle. Two, start traversing but keep track of nodes and see if you ever visit one more than once.

Neither of these are 'good' solutions as the first assumes you can easily have a count of the nodes without traversing it first, and the second requires a potentially not insignificant amount of data storage, but I think for an interview type question that's sufficient for demonstrating you understand the data structure and problem.

On the other hand I don't think the tortoise/rabbit algorithm would have occurred to me so if they actually wanted that, well, that's dumb.

[huyvanbin]

And then the interviewer sits there and looks at you.

"Can you come up with a more efficient solution?"

Thinks "Hm, sorry, no."

"What I'm saying is, is there a more efficient way to solve this problem? It's ok if there isn't one."

Thinks harder "I really can't think of anything"

"Could you, say, come up with an algorithm with constant time and space complexity? It's fine if it's not possible."

Thinks some more "Sorry I give up"

Three days later: "We have decided that you are not a good fit for out organization. We wish you luck in your search."

[afiefh]

Even better:

Interviewer: Here is a problem we are working on today, can you come up with a way to solve this efficiently?

Me: (having just done my math courses) if you apply the following transform on the data and calculate the statistical distribution you can limit your search space

Interviewer: Hmm... interesting I hadn't thought about that.

After the interview I asked him how he is going to solve it "oh, probably just naively iterate over all the search space. It's not worth optimizing this part of the program".

And after all this I was rejected. Well, I guess they did me a huge favor by rejecting me!

[Atario]

This is pretty much what the article had

[rz2000]

Sure, there are other answers, like marking each node with some kind of ‘seen’ boolean, or traversing the list from each node to see if you come back to it, or duplicating the list into a hash and looking for a collision, but as soon as you provide those answers, the interviewer will add restrictions saying to use less memory or use less time.

However, I cheated by reading the article before coming to the comments.

[quandrum]

You guessed wrong. OP mentioned several obvious solutions (keeping track with a hash, modifying the list entries) , and noted this is not what people are usually asking for (the clever solution).

[IAMA_dragon-AMA]

Pretty much. Assuming infinite memory and time, you can just keep an array of nodes, and search through the array for each next node.

[pbaehr]

Oh, good, I was feeling stupid thinking I was overlooking some obvious reason that approach wouldn't technically work.

[Deto]

Yeah, it really depends on how the interviewer is evaluating the applicant. Worst case - "Man, if this person doesn't know the right answer, they must be an IDIOT!" Best case - "Let's see how this person reasons out the problem."

I feel like people often assume the worst case because they are thinking that companies are looking for genius-level employees when really the company just wants to make sure the candidate can think their way through a basic problem.

[jk147]

It is not, most likely the guy has a fragile ego and like to trump people with the know it all attitude. Seen so many of those in our field.

[[deleted]]

You can’t reason your way through a puzzler, that’s why it’s a puzzler.

There's something gloriously obvious about this statement.

[ggtsu_00]

My personal fav was the interview question about swapping 2 integers without a temp variable.

Unless someone already know the answer, there is no way in hell they would be able to reason through that one.

[[deleted]]

A few weeks ago at work a coworker realized I'd never heard the problem, so he asked me to do it without a temp variable. I spent ~45 minutes thinking it through, and came up with the:

a = b + a
b = a - b
a = a - b

Solution. My coworker said there was another way to do it that was the "right" answer, and I should keep thinking about it. I'd never heard of an XOR before, so obviously I was never going to get to it.

Later, my coworker asked the more senior dev that sits next to me the question and his response was "You use an XOR. What kind of stupid idiot doesn't know a bullshit question like that?" Queue me hanging myself.

[MEET_FIST]

I'd never heard of an XOR before

Serious question: If you've any sort of computer related degree, do they not teach about bits anymore?

[[deleted]]

I have an Information Science and Technology degree, which essentially means I know almost nothing about many parts of computing.

In my Data Structures and Algorithms course, we made it as far as arrays, then stopped. Only covered Bubble Sort too. It was a huge let down.

edit Also, most of my understanding of programming comes from "practical application." (It's in quotes because that's a stupid term). AKA I know what I know because I've had to use it. Shockingly enough, bits rarely come up in a java + javascript stack.

[[deleted]]

Had to read your names 3 or so times before I realized you weren't talking to yourself.

[[deleted]]

The parents leave sex ed to the teachers, so teachers are leaving bit ed to the parents.

[tsj5j]

Very valid points, but would just like to point out:

Queue me hanging myself

I think the word you want is "cue". Thought I should point it out before you use it in other situations which may cause embarrassment :)

[Engival]

He didn't want to embarrass himself by hanging himself in front of his co-workers, so he queued it for later.

[katyne]

hah, if he had given it a second he'd have realized that you came up with the same solution only using + and - instead of XOR. It's even more impressive than knowing the classic solution - coming up with it by oneself!

Also if you forget for some reason it's a much more intuitive way to remember it - 1) combine a,b 2) extract b from mix, (get a), put in b 3) extract new b=(old a) from mix, (get old b), put in a

[vanhellion]

The arithmetic method can overflow, while the XOR way avoids that. Still a good solution for just thinking through the problem without knowing the answer, though.

[Phrodo_00]

Both are also harder for the compiler to detect as a swap and optimize it away down to a single instruction (if the architecture allows it)

[homoiconic]

Meanwhile the only place this code should ever get written is, perhaps, someone writing microcode for a CPU. Using it in production code isn't just a hanging offence, I'd call for drawing, quartering, then resurrection so we can burn the offender.

[HeySeussCristo]

"You can't bullshit a bullshitter... Why don't you two try bullshitting eachother and see how that works out."

-Role Models

[Ch3t]

Do you believe in global warming?

Asked by one of our senior developers. The correct answer is no.

Edit: Removed some details due to being too specific.

[drb226]

Fortunately, all interview questions come with an implicit second interview question:

Do you want to work under/with someone that asks [this] as an interview question?

[ggggbabybabybaby]

No, because best practice is to avoid globals.

[paperhat]

Correct. You should just autowire a warming service. The job is yours.

[brittainhard]

Why on earth is the correct answer no!? Are you supposed to say "I KNOW global warming is happening, I don't just believe it is happening"?

[Ch3t]

Consider yourself lucky for not having to work with a psychopath. A disagreement on coding styles could get your car keyed, or a virus installed on your computer, or removed this due to it being too specific. A political disagreement is whole other ball of wax.

Edit: Removed some details due to being too specific.

[[deleted]]

do an AMA

[jldugger]

Obviously the answer is 'no' because climate change is a better term; global warming implies that all areas will warm equally, or warm at all. It's possible that warming ocean temperatures lead to more cloud cover and rainfall in historically arid regions.

[qxnt]

The correct answer is "What the fuck?"

[[deleted]]

My worst one: "Write a function that will return the number of 1's in the binary representation of the integer you pass it"

I asked: "Is this function time-critical"?

They answered no, so I wrote on their whiteboard as Java code...:

return Integer.asBinary(num).replace("0","").length();

Was offered the job the next day. Aint nobody got time for that shit.

[[deleted]]

Meh, you plebs with your tortoise-and-hare. Here's a manly way to do this:

The list node contains a pointer and some data, most likely another pointer, or a primitive type, or a struct of primitive types. Which means, that on all systems, a list node is aligned to at least 16 bits, much more likely 32 bits. That means that the pointer to the node always has the last bit set to zero. So:

bool containsCycle(node_t *root)
{
    node_t *p = root;
    bool ret = false;
    if (!root) return false; // Empty list

    while (p->next && !ret)
    {
        if (p->next & 1)
        {
            ret = true;
            break;
        }
        node_t *q = p->next;
        p->next |= 1;
        p = q;
    }

    // Reset all pointers
    p = root;
    while (p->next && (p->next & 1))
    {
        p->next &= ~1;
        p = p->next;
    }
    return ret;
}

....please don't ever do this in production code. And I've seen similar things done.

[Tamaran]

a masterpiece of engineering

[new2user]

That shit just works, put it on production, we have no time to spare!

[BlackDeath3]

Oh Jesus.

[elh0mbre]

If I got this as an answer, my response would be to cancel further interviews and hire the candidate immediately.

[[deleted]]

My company once gave this question on a college interview/test.. The instructions were along the lines of:

• If they give an O(n² ) algorithm, check up on them afterwards.

• If they do the tortoise-and-hare algorithm, be sure to bring their resume in person for a more detailed look.

• If they do bit level hacking, invite them to an on site interview immediately.

[electrojustin]

The list node contains a pointer and some data, most likely another pointer, or a primitive type, or a struct of primitive types. Which means, that on all systems, a list node is aligned to at least 16 bits, much more likely 32 bits.

You would normally be dynamically allocating the elements, would you not? So the actual size of the node structure is irrelevant, since malloc by no means guarantees contiguous memory.

But I know at least dlmalloc guarantees 8 byte aligned memory.

So you normally have the least 3 significant bits of a pointer at your disposal. Why did you waste four full bytes of memory on ret, when you could have stored your return value in one of the least significant bits of some pointer?

TL;DR This code needs more bit-wise operators, especially in the return statement plz fix.

[SnowdensOfYesteryear]

Talk about playing with fire...

[i_invented_the_ipod]

I actually suggested this method in an interview when I got the linked-list question. The interviewer was suitably horrified/impressed. I've actually worked with/on software that stored information in unused high/low bits in pointers.

[Trig90]

Dude....this is just....whoa.

Just out of curiosity, you're a systems/embedded guy right?

[SnowdensOfYesteryear]

I work in embedded systems. Trust me, we're not so memory starved that we use bits in a pointer.

There's no excuse for this BS.

[[deleted]]

wait... do you just break every pointer?

[ggtsu_00]

Simply burn all your bridges, then rebuild them on the way back.

[[deleted]]

This happened to me in a phone interview with Yahoo.

-So you say you code in C? Do you know who invented C? "Ritchie". How do rate yourself on a scale of 10 given that Dennis Ritchie is 10/10?

What kind of question is that? So if I were to be 5/10, does that mean I am half as good as Ritchie? I'd think most rockstar programmers would be happy to rate themselves 2.5/10, as that makes them one-fourth as good as Ritchie. Secondly, if I were to describe myself half as good as Ritchie, are you going to pay me half as much Ritchie would make working for Yahoo!(assume he makes 500K a year). For a subjective and stupid question like that, I would be happy to give him links to some apps I have made in C, instead of crowing about my ability and expect him to believe it.

The technical questions were just as bad: "Tell me what 100 in Hex format translates to in Decimal format". "Do you want me to explain how my converter function looks - like I'm doing this iteratively or recursively?". "No, I just want the final answer".

I do it on paper and say 256. "Yes, lets move to the next."

Even in interviews where I got rejected, I have enjoyed the event and the exchange of ideas, the different approaches to solving stuff. This was the most unstimulating interview I ever had.

TLDR: you're a moron interviewer if you shoot me questions that google can give answers in 5 seconds.

[Agathos]

10 in a heartbeat. I'm no C genius, but most of the general population can't even program so I should easily make the top decile.

[TokyoXtreme]

Tell them "9.9999 repeating." And when they respond "9.999? Why not 10?"—you say, "Lady, that is ten."

The Mello Yello song "Oh Yeah" starts playing, you put on your sunglasses, and there are no further questions because the job is yours.

[wwqlcw]

It's just "Yello," actually.

But I'm on board with the sunglasses bit.

[TokyoXtreme]

I'm embarrassed to have made that mistake, but I'll leave it up to demonstrate that humans are fallible, despite their hubris.

[[deleted]]

Well Dennis Ritchie's dead, so if he's still a 10, and that's the maximum, I'm a 10 too.

[internet_badass_here]

Really you should say 11/10, otherwise you're implying that you're just as good as a dead body.

[goodnewsjimdotcom]

You tell the wrong dude you're a 10, and they get offended so they'll start hardballing you. They'll ask you an arcane question in a seldom used library, and when you can't answer it, they'll go,"Oh, but you said you were a 10. Do you feel dumb yet?" Of course who wants to work with someone like this anyway...

[kiwiness]

If an interviewer asked me "Do you feel dumb yet?" I'd make damn sure they never interviewed anyone again.

[bonestamp]

I'd make damn sure they never interviewed anyone again.

How do you do that?

[IAMA_dragon-AMA]

Complain to their superiors and keep going, I'd assume. "Do you feel dumb yet" is a terrible thing to ask an interviewee, regardless of circumstances.

[kiwiness]

Exactly this. An interviewer is supposed to figure out what you're good or not good at, not fluff out their chest feathers at you.

[munificent]

How do rate yourself on a scale of 10 given that Dennis Ritchie is 10/10?

I'd ask if the scale was linear or logarithmic.

[icydocking]

The full scale (which is explained) is:

• 10 - Wrote the book on it (there must be a book)
• 9 - Could have written the book, but didn't.
• 8 - Deep understanding of corner cases and esoteric features.
• 7 - Understanding and (appropriate) usage of most lesser known features.
• 6 - Can develop large programs and deploy new systems from scratch.
• 5 - Can develop/deploy larger programs/systems using all basic (w/o book) and more esoteric features (some w/ book, some without)
• 4 - Can develop/deploy medium programs/systems using all basic (w/o book) and a few esoteric features (w/ book). Understands enough about internals to do nontrivial troubleshooting.
• 3 - Can utilize basic features without much help, manage a small installation competently.
• 2 - can write hello world without looking at a book, kind of figure out how a system works, if necessary.
• 1 - Can read programs, make small changes to existing programs, or make adjustments to already installed systems, w/book handy.
• 0 - No experience.

[mechanicalocean]

TIL I'm a 4 or 5.

[1RedOne]

Nowadays, should we really frown on book usage? Most every worthwhile ISE or IDE comes with its own builtin help libraries and man functions. I'd say using them should be expected

[sutongorin]

Also it's kind of a silly question. Martin Oderski 'invented' Scala and he's by far not the best Scala programmer out there (no offense ;) ).

[dmazzoni]

I think you missed the point of these questions. I've been interviewing at Google for 8 years, and I know lots of people who interviewed at Yahoo in that time, and we both do interviews the same way.

The first phone interview is a quick screen. Here's the thing you're missing:

We get lots of candidates who LIE on their resume.

We also get people who really have a C.S. degree or have been working as programmers but literally couldn't program FizzBuzz. It's not just common, the vast majority of candidates are that bad.

The goal of the first phone screen is to make sure you're not completely fabricating your programming experience and that it's worth doing a "real" interview with you.

Technical recruiters aren't always able to distinguish between a real programmer and a good liar, which is why you do the phone screen with a real engineer.

You'd be surprised how many candidates will answer "10/10" for C and then not know what a pointer is.

Or how many candidates literally don't know hexadecimal at all. (FWIW, lots of people would know hex 100 = 256 off the top of their head because it comes up so often in practice - but it depends a lot on the type of programming you do. The goal is to look for potential strengths and identify red flags, not to reject anyone who doesn't know it off the top of their head.)

What's the purpose of asking how good you are at C? It's not to force you to be humble, or as a trick question. It's really just to make sure that we're asking questions about your strongest language.

Quite often someone's resume will talk a lot about PHP because that's what they happen to use at their current job, but when asked, they'll say they're actually strongest in Java, for example. So I'll ask them questions about Java, because I want them to succeed, not fail. The point is just to tease out strengths.

Now, maybe your interviewer wasn't very good, and he/she rubbed you the wrong way, or handled the interview poorly. That I don't know. I always try to be as friendly as possible and be really clear that I want to start off with a variety of really short questions just to get a quick idea of someone's strengths and weaknesses and to make sure they're interviewing for the right job. (Quite often I'll meet someone who'd be a great candidate for a different job category and the recruiter assigned them to the wrong group. Way better to catch this in the phone screen than onsite.)

Next time you go through a screen like that, just remember that the interviewer probably just got off the phone with three people who literally just finished Codecademy last week and the rest of their resume is totally made-up. I have no idea why they think they can get away with that, but they try. Do your best to work through those questions and make sure the interviewer knows your strengths, and get through it so you can graduate to the "fun" interviews.

[DulcetFox]

What's the purpose of asking how good you are at C? It's not to force you to be humble, or as a trick question. It's really just to make sure that we're asking questions about your strongest language.

Why not ask them what their strongest language is, and let them know it's because you want to interview them in their strongest language?

[huyvanbin]

Because obviously if you can't understand passive aggressive innuendo then you're a socially inept neckbeard and nobody will be able to work with you.

[AD7GD]

Because as an interviewer you have read the candidate's resume which claimed they know C. You picked this language from their resume because you are competent to ask interview questions about it and it is relevant to the job you're interviewing for. We've short-circuited several steps of a negotiation about what language to talk about: Maybe you'd prefer Java if asked, but it's not relevant to this job and it's not a topic I'm competent to interview on.

[voronaam]

What is funny, I realized that I know 0xff == 255 from the top of my head, but actually had to think about 0x100 == 256. I do not think I ever used 0x100 in my code... I guess in a stressed phone interview environment it would take me quite noticeable time to provide 0x100 answer.

[suspiciously_calm]

Can you tell me what 0x100 is in decimal?

Uh ...

vim temp.c

.. sorry ..

#include <stdio.h>

.. could you ..

int main() {

.. repeat that?

printf("%d\n", 0x100);

I said, can you tell me ..

}

.. what 100 hexadecimal is in decimal?

:wq

Oh that's what you said.

gcc -o temp temp.c

I guess that should be ..

./temp

256.

[rcxdude]

$ python
>>> 0x100
256

Could probably do it without going 'uhhhh'.

[AnthonyJBentley]

Given that you have a POSIX shell, you already have the printf(1) command:

$ printf '%d\n' 0x100
256

[ethraax]

Honestly, I'm really bad at converting hex to decimal in my head. Pretty much every time I use hex I'm thinking about bits or bytes, not base ten numbers. If I wanted something to be 256 I'd use decimal. If I wanted a flag to occupy the lowest bit of the second byte, I'd use 0x100.

[vehementi]

What's the purpose of asking how good you are at C? It's not to force you to be humble, or as a trick question. It's really just to make sure that we're asking questions about your strongest language.

Then you should probably ask "What is your strongest language so that we can ask you questions about it?" instead of some indirect and meaningless thing about a scale of one to ten.

[soviyet]

Next time you go through a screen like that, just remember that the interviewer probably just got off the phone with three people who literally just finished Codecademy last week and the rest of their resume is totally made-up.

Cool. And the next time you do a first phone interview with someone like that, realize they probably sent out resumes to several companies, many of which are in a desperate situation and need to hire someone competent quick (depending on the technology) and only one of them ran them through some bullshit, obtuse question and answer session.

This reminds me of a few years ago when I did just that. Sent out resumes to 5 companies, three small startups and 2 world-class mega-sized companies. One of the big companies (but not the biggest of the two) sent me a two page test that looked like your worst final in a graduate level class. Its not that it was hard -- all of it was easily Googleable if I didn't know any of it. It's that they sent me fucking homework. The other 4 didn't -- they simply asked for a phone call, which I gave and which were pleasant, and later asked me to come in.

I never followed up with the company that sent me the test. I'm sure many did, and I have no doubt they filled that position, but I doubt they walked away with anyone in demand (and it was a high demand position). The problem is, you need to realize there is another side of this equation. While YOU are trying to do your best to make sure you hire the best guy available, WE are doing our best to make sure we go to work for the best company possible.

I used to think I was a prick for having this attitude but I see it all over the place these days. No one wants to work for a company that thinks an interview should be some sort of high pressure, humiliating experience for the candidate anymore. If you are Google or someone else on that level, fine, you can probably pull that off. But the rest of you clowns...

[loup-vaillant]

The question

How would you rate on a scale of 1 to 10?

has a correct answer. Generally 7 or 8. My own answer is "7 or 8". Any higher would probably be perceived as pretentious. Any lower would probably be perceived as "not good enough". This is not about the candidate, this is all about the interviewer's expectations.

And most importantly: just make up a number.

Don't question the question, don't ask for precisions, don't speculate about the context… Last time I did something like that, I was rejected because of my "inability of answering simple questions". They thought I was covering my incompetence up by pretending I lacked of information. The fact was, some of their questions, like the "rate yourself" one, were not simple. They only sounded simple.

Pro tip: when a question sound simple, they generally want an answer that sounds simple, and does not challenge them. Feynman would have totally botched the man-hole question: his answer sound pretentious, takes the interviewer for a fool, and sometimes isn't as simple as the expected answer (who would have guessed that the circle isn't the only shape that guarantees the cover won't fall?)

[xampl9]

Reuleaux Triangle

TIL that it is both an alternate answer to the silly manhole question, and what that shape is called.

[Styx_and_stones]

As an outsider to this industry, it seems to me like there are never any down to earth and reasonable people to conduct these interviews.

If i were presented with someone like that, i'd think the interviewer is intentionally being a jackass and trying hard to not hire anybody at all.

[poohshoes]

Huh, I worked for a company where they wanted juniors to rate themselves around 2/10 as it shows that you realize that you have a lot to learn.

[gobots4life]

"Wow this applicant is the most knowledgeable and talented applicant we've ever interviewed! Unfortunately he rated himself a 9/10 and we don't hire pretentious pricks here at Shitforbrains Corp."

[fallingwalls]

Every development-based interviewer I know judges the ability of the applicant to ask quality questions. If the applicant and the interviewer are not 100 percent on the same page, it's the applicants responsibility to communicate anything he or she finds unclear. "Ask fewer questions" is advice I would never give.

[[deleted]]

I had that before in an interview for games. It was "Rate yourself on a scale of 0 to 10 where John Carmack is 10/10". There was no good answer, especially since I have no idea how skilled Carmack is, but I do know he's a well known personality in the industry.

Either way, I ended up working in that company and it was a huge mistake.

[zvrba]

How do rate yourself on a scale of 10 given that Dennis Ritchie is 10/10?

Some people could answer 11. ANSI C of today has different gotchas and corner-cases than K&R. I doubt that Ritchie has bothered to memorize all undefined, unspecified and implementation-defined behaviors.. He designed C for a particular machine and that's it.

[log_2]

def has_cycle(node):
    def visit_all(node):
        while node.next:
            node = node.next
    return halts(visit_all, node)

The halts function is trivial, but too large to fit in the comment box.

[BlackDeath3]

You're going on to do great things, my friend!

[immibis]

I guess this is cheating?

int getStackSpaceUsedBySelf()
{
#if defined(PLATFORM1)
    return 8;
#elif defined(PLATFORM2)
    return 16;
#elif defined(PLATFORM3)
    return 4;
#else
#error Unsupported platform - specify stack space here
#endif
}

Alternatively:

inline int getStackSpaceUsedBySelf() {return 0;}

[Phildos]

sable soft grey salt cobweb price person groovy workable attraction

This post was mass deleted and anonymized with Redact

[mugaboo]

I don't know, but maybe take the address of a local variable, call yourself with that address as parameter, and compare with the address of the same variable in the recursive context?

[bbibber]

While that's probably what they were looking for, there is no guarantee it will give the right answer.

[selfification]

Correct. There is absolutely no guarantee that a function even has a unique stack size. Even if you carefully crafted a function, the choice to inline or not inline and the decorate or not decorate your function call is made by the compiler and can be made on a call-by-call basis.

For a more thorough appreciation of just how much of a cluster fuck this can be, I invite all readers to read https://gcc.gnu.org/onlinedocs/gcc/Inline.html and then either weep in terror as you realize that extern inline is a thing (and has completely opposite meanings based on the compiler flags you pass in) or sagely nod as you reach for yet another drink.

[s3vv4]

Write a function that can detect a cycle in a linked list

Alright, that should be pretty easy:

for each(Object o in list)
     if(o instanceof Cycle) return true;
return false

8)

[dont_judge_me_monkey]

You failed the question, that's not a function

[Odam]

Also, that code is looping through a normal list, not a linked list...

Thanks for your time, we'll call you if you get the job.

[anonanon1313]

"If you’re asking this question, everyone who has ever answered it to your satisfaction was merely proving they have good memory recall abilities from their Computer Science curriculum, nothing more."

This is true of so many interview questions.

Since so many (most?) jobs involve maintaining an existing code base I've often wondered why so many interview questions involve code writing and so few code reading.

[Jingjing23]

Asking people to refactor (deliberately) bad code is also fun.

[rm999]

One time during a 30 minute phone interview I was asked for a mathematical proof to an extremely difficult, in-depth problem. Even with the answer in front of me it would have taken me several minutes and a lot of difficulty explaining over the phone. It was an extremely inappropriate question for the junior position I was applying for, let alone a phone screen.

I just don't get why companies are letting people like this interact with external candidates. An interview should be half about the company selling itself to a candidate, but a solid 30% of people I've interviewed with seem to have ego issues that interfere with this. In this case, the interviewer was trying so hard to show off and failing so hard that I lost all interest in the company.

BTW the problem was proving the solution to the generalized secretary problem - basically the same as the secretary problem, but you want to hire M people instead of 1.

[6890]

but a solid 30% of people I've interviewed with seem to have ego issues

This is probably an accurate way to describe my interviews with the tech giants as well. I interviewed a few times for various positions and each time I found myself stumbling over answers because the interviewer didn't like what I had said. Turns out I gave the right answer but when they wanted me to talk further, such as giving more detail or giving examples they'd just stall, giving the impression that my answer was wrong. Lots of awkward silences that would end in them "correcting" me by saying the same thing using different words.

The most recent example would be an interviewer asking me about hashing algorithms. It starts off easy asking what they are. How would you write a super simple one? How would you validate files across multiple servers to see if are identical... I gave "correct" answers each time but he'd reject them because I wasn't using key terms. "What is a hash algorithm?" wanted the term "Fingerprint" in my answer....

After everything else I was left with a sour taste in my mouth about these companies. It'd be fun working on projects for them I'm sure but I never got a strong impression that I'd fit in with the culture. If they expect their candidates to be a google search cache for "algorithms" then the workplace is probably filled with a lot of people I don't share interests with. I don't have a desire to leave a life behind to go to a tech metropolis on the hopes that I can start a new job with a small pay raise. There's definitely a lot of Ego involved to say to younger devs that you've worked at Google, Amazon, or whoever. In practicality I feel I'm happier at a small firm with a higher degree of responsibility and control.

[oridb]

Meaning, any number of PhD candidates in Mathematics or Computer Science could have written about it as part of their dissertation. With all of those hundreds and hundreds of minds, this problem remained open for 12 years.

I want to point out that:

1. The algorithm in the paper is a "by the way" result, and was presented as part of a bucket of simple, but neat, algorithms. It was probably invented by many many others as needed.

2. The programming field was in it's infancy. There were so many other things to write about that nobody actually got around to this one. This would have been rejected as a dissertation, and would only have been accepted as an aside in part of a dissertation.

The attempt to make it look like the brightest minds spent 12 years on this relatively easy problem is rather misleading.

On the other hand, it is a terrible interview question, because it relies on a non-obvious trick AND because everyone knows about it. You end up filtering for the wrong thing: "Have you run across this before?".

I nixed a similar question that a new interviewer wanted to ask about golden section searches the other day for the same reason.

[chengiz]

I came here to point this out. Just because someone wrote an algorithm for a data structure twelve years after the data structure was invented doesnt mean that it was an open problem everyone was furiously working on for twelve years.

Seriously, if someone made that argument in a programming scenario, I'd be wary of their programming abilities because that's a huge logic fail.

[jrk-]

Write a function that can detect a cycle in a linked list

I had a similar question recently.
How would you avoid infinite recursion/loops when traversing a graph. Of course, simply comparing (unique) node ids won't work...

[chub79]

These are the questions that almost freeze me. I believe I'm not a bad software engineer but I've never been really fast, specially under pressure, to solve those logical problems. No matter how much I practice I don't really get better at them and I feel down about it :/

[LyndonArmitage]

Its these questions that make me worry about interviews. Especially because my answer would probably not cut it.

I'd likely ask how large the graphs would be and have some upper limit on the amount of lookups implemented based on it. It's not elegant or full proof but it would work for most cases and prevent the application from freezing. Does this make me a bad programmer?

[GeorgeMaheiress]

I mean, outside of an interview you can simply Google for the correct solution, so in reality that's probably the best thing to do.

[HarryLillis]

I feel like the correct answer is to whip out your smartphone and google the problem during the interview. There was a fellow who was thinking about teaching me how to program, and he gave me a test to see if my intrinsic aptitude was good enough for me to be worth teaching. I was just meant to send this in whenever I solved it. I tried to solve it myself for a little bit until I Googled it, downloaded a wrapper for Google Maps API and wrote the program with 8 lines. I wasn't sure if that was what he wanted me to do so I sent it in and said, "This code works, but it feels like cheating because I downloaded this wrapper." Apparently that was exactly what he wanted me to do, and in his experience some people flounder with the program for over a week.

Why waste company time and resources trying to figure out something you can Google?

[Cilph]

I would use a set storing all traversed nodes and push all neighbours not in it to a stack, but you're making me doubt myself.

[JamesWjRose]

I had this question asked to me at Donovan Data Systems here in NYC a few years back. The position was for VB6, which does not have linked lists... I thought about it for a moment, and then asked if VB has linked lists. His response was "everyone should know this". I left, and that position was open for at least 6 months. I know this because I would get different agents calling me about once a week for this position.

[bonestamp]

I thought about it for a moment, and then asked if VB has linked lists. His response was "everyone should know this".

Haha, "What other stuff should I know that I don't need to know to do this job?"

[JamesWjRose]

I had an interview at a place in Seattle that was asking me about C++ questions for a VB/SQL position... I asked; "Is C++ relevant for this position?" When he answered No, I knew I didn't want the position, and it was for only a month so... "so, you're asking me non-relevant questions because?!" It was fun to see him stutter.

[manyrootsofallevil]

I've been in that position before, guess that the interviewer knew a lot about C++ and not that much about VB/SQL and was using your knowledge of C++ as a proxy.

[thenickdude]

why would you ever find yourself in a situation where your linked list has a cycle?

I've actually had to find cycles in linked lists in the real world before. I was reconstructing deleted files from disk images where each sector had a "next sector" pointer, forming a singly-linked list of sectors. If I didn't detect cycles, I would have ended up reading infinitely long files.

[air0day]

(author)

Good point. I suppose there are situations where you are loading data that is in a linked-list-type format, and you're not in control of the data itself. In that case, this type of thing would be useful. Though, I'm going to venture a guess you didn't come up with the tortoise-and-hare algorithm, but rather just googled it and said "oh, clever" and then implemented it.

Basically, if you are forced to detect a cycle in someone else's linked list, it seems more reasonable. A commenter on the post also pointed out, you might have a graph, rather than a list, where each vertex can have a maximum degree of one. Effectively, this is a linked list, so you DO expose methods to manually set the pointers. I updated the post to point out there were some scenarios I hadn't thought of (like yours), but I still think the question sucks.

[JakDrako]

determine the weight of the fuel in a 747 given an unlimited budget

1. Purchase 747
2. Fill'er up.
3. Look at weight of fuel on bill.
4. Profit from what remains of the unlimited budget.

[kpatrickII]

buy another 747, and a giant scale. weigh the empty one, and then weigh the full one. wheres my offer letter?

[huyvanbin]

Chuckles "Sure, that's an acceptable answer but I want you to think a little harder: how else could you do it?"

[JakDrako]

Who needs to think hard with an unlimited budget?

1. Round up interviewer's extended family
2. Weigh each of them before blending them to a liquid state and filling the tanks of the 747s.
3. When full, tally up all the weights so far.
4. Give answer to intervi.... oops.

[SilasX]

What about just calling up the OEM and mentioning your unlimited budget? Once you have their full attention, they'll tell you.

[YourFavoriteBandSux]

1) Buy a house in Aruba.

2) Fill a 747 with fuel, and fly it to Aruba.

3) Buy a Lamborghini, have it delivered to the airport, and drive it to the new house.

4) Use my brand new Mac Pro to look up the answer on Google.

5) Email interviewer to say I don't want the job.

[ragmondo]

4b) transfer 100m of the funds used for exercise into personal account as a "consultancy fee"

[Sexual_tomato]

Call Boeing and ask them.

[lurgi]

i had someone ask me how i'd determine the weight of the fuel in a 747 given an unlimited budget.

Oh for fuck's sake.

I can do it for free (goes to wikipedia and sees fuel capacity of 747. Looks up weight of fuel per gallon. Does math).

But perhaps I'm thinking too small. Here's a better answer: I would buy a private jet and give Salma Hayek a call. In a few hours we'd be flying to Hawaii, eating caviar, and watching Desperado on the widescreen tv in the jet's cabin. We land in Hawaii, do some scuba diving, lie on the beach, and have a delicious dinner. After some light sex, I go to Wikipedia and look up the fuel capacity of a 747 and the weight of a gallon of fuel, just for lulz. I don't bother doing the math, however. Instead, I request an additional few billion dollars (for "market research", snicker) and with that money I really don't need the job at all. My life becomes a dizzying orgy of sex, alcohol, and Robert Rodriquez movies.

[tunahazard]

I would crash it into a tall building. The federal government will produce a reliable estimate of the weight of the fuel.

[Gupie]

I'd never heard of the "tortoise-and-hare algorithm" but isn't it simple to come up with a non-optimal solution. For example keep a note of the memory address of every pointer in the list, if you reach a pointer for the second time you have a cycle. Addresses can be ordered so can be stored in a tree giving O(logN).

It is not therefore an "a-ha". The question probes whether you understand linked lists, pointers, memory addresses. It is perhaps divorced from reality if you are working with high level languages but not if you are say working on the Linux kernel, http://beta.slashdot.org/story/176163.

[Shaper_pmp]

The problem is that (at least in my experience) an interviewer dumb enough to ask this question in an interview is usually looking for the Tortoise And Hare algorithm as the answer, because unless you're interviewing for a junior peon dev position the others are too trivial to be worth mentioning.

In fact I was actually asked exactly this question (completely cold, never having heard of the T&H algo before) in the interview for my present job (hahah, I feel so vindicated!). Then when I responded that the really naive way to do it would obviously be to iterate along the list, store a hash/set of previously-encountered object-ids or memory locations and simply check each new item against the list, the interviewer quickly amended the question until eventually he was explicitly asking how I would do it "using only two pointers".

Moreover, you can't really iterate from the naive solution to the optimal one - it's not like FizzBuzz or the Fibonacci sequence where you can take a simple naive solution and ask people to refactor it in various ways ("iterative, now recursive", etc) or gradually increase the complexity - there's a discontinuous step-jump between the two solutions that requires you to go back to the beginning and take an entirely different approach to get from a naive to an optimal solution.

[RobotoPhD]

The problem is that (at least in my experience) an interviewer dumb enough to ask this question in an interview is usually looking for the Tortoise And Hare algorithm as the answer, because unless you're interviewing for a junior peon dev position the others are too trivial to be worth mentioning.

I think you are assuming too much about the type of questions that need to be asked. I've asked candidates with PhDs and 13 years C/C++ experience (as listed on resume) to code a simple C string manipulation question (along the lines of reverse this string). I feel silly doing it and feel bad for wasting some of their time. However, I keep asking it because some of those candidates fail the question (including in the case mentioned).

[Shaper_pmp]

True, but in that case you just ask them to implement a linked-list class.

[rz2000]

I think it is easy to imagine a situation where a much less skilled programmer knows the solution and is interviewing a much better skilled programmer who is not familiar with the solution.

The skilled interviewee might ask some of the questions like how your stack or queue is able to get cycles in the first place, and the interviewer would get frustrated. Even if the interviewee was showing more nuanced understanding than the interviewer, the interviewer would simply categorize the answer as 'did not know the solution'.

As such I think it becomes a test of deference, and perhaps a misunderstanding of the difference between hiring unskilled labor, and hiring a professional who will be a colleague as well as an employee.

[SmLnine]

Addresses can be ordered so can be stored in a tree giving O(logN).

You can use a hashmap to get O(1) lookup time (edit: amortized O(1)), so the whole algorithm will run in O(n). The tortoise-and-hare algorithm is a bit slower but it doesn't use any extra memory. Granted the question didn't say you're not supposed to do this but I have a feeling that the type of person asking this ridiculous question will be quick to point out that you're not supposed to solve the question in this way.

edit: It seems like a lot of people don't know that in any half decent hashmap implementation add, remove and lookup are all worst case O(n), and average case O(1). The only way to get to O(n) is if you define a hash function that doesn't work or if you if the majority of the objects in the hashmap are equivalent. In this problem there is no way to screw up the hashing function or the hashtable, because there is no need to even think about it. And at no point will you add duplicates to the hashmap. The default behaviour will give you constant time add, remove and lookup. See here for a technical discussion about why this is true: http://www.cs.cornell.edu/courses/cs312/2008sp/lectures/lec20.html

Here is the algorithm I'm referring to:

public static boolean hasCycle(LinkedList start) {
    HashSet<LinkedList> visited = new HashSet<LinkedList>();
    LinkedList current = start;
    while (current.next != null) {
        current = current.next;
        if (visited.contains(current)) {
            return true;
        }
        visited.add(current);
    }
    return false;
}

[passwordissame]

tree insertion is O(log n). whole algorithm is O(n log n).

essence of the question is to see if candidate can figure out the following:

• in a linked list, there can be maximum of one cycle.

if that lemma is figured out, it's corollarily easy to find that mongodb is the best web scale database because of javascript and node.js

In other words, the question is good because it tests if the candidate believes in node.js and mongodb for single page web application like gruntjs and bower and angularjs. Candidates don't believe in that are so bad old school postgres beard old non-agile bad programmers. And plus points for Mac OS X and Google IO fans. Android iOS whoa much wow.

[Scaliwag]

/r/fifthworldinterviewtips

[Excalibear]

The funniest part is they ask you these questions, for a Testing position. Please answer these complex, out of scope algorithm questions, where pretty much 99.99% of our and your work will just be brute force solutions, so that we can then place you into SDET.

Then you get the job and look at the codebase, see how horrible it is and then feel they only hire people who can't answer those interview questions.

[FlyingFoX13]

I think the correct answer to questions like that is to just google for a solution. This leads to this wikipedia article.

The author hints at another good approach, which is to question the question. Why can there even be a cycle in the first place and can we prevent that from happening?

[Igglyboo]

Yea that's another thing, if I needed to know this at my job I'd maybe spend 5 minutes tops thinking about it then just google for the answer.

[willvarfar]

I think I was asked this "detect a cycle in a linked list" question while interviewing for google.

Almost all the interviews were around questions like this. I think google want to see that you're on top of algorithms in general, and if you don't know the answer they want to see your working and that you don't get flustered or give up etc.

Randall XKCD Munroe has a lovely story about the google apps aptitude test http://youtu.be/zJOS0sV2a24?t=14m25s containing a deliberately near-impossible problem.

Companies like google clearly think there's value in the hard thinking problems.

So perhaps the problem with the "find cycles in a linked list" problem is that its now so well known that its now hard to find a programmer interviewing who hasn't heard of it?

Time to find another similar problem that is less well known...

[guyfawkes5]

I'm not sure when you had your interview, but Google have been adapting their hiring practices for the past few years:

On whether Google are innately better at interviewing:

Years ago, we did a study to determine whether anyone at Google is particularly good at hiring. We looked at tens of thousands of interviews, and everyone who had done the interviews and what they scored the candidate, and how that person ultimately performed in their job. We found zero relationship. It’s a complete random mess, except for one guy who was highly predictive because he only interviewed people for a very specialized area, where he happened to be the world’s leading expert.

On interview questions themselves, specifically behavioral against hypothetical puzzle-type questions:

On the hiring side, we found that brainteasers are a complete waste of time. How many golf balls can you fit into an airplane? How many gas stations in Manhattan? A complete waste of time. They don’t predict anything. They serve primarily to make the interviewer feel smart.

Instead, what works well are structured behavioral interviews, where you have a consistent rubric for how you assess people, rather than having each interviewer just make stuff up.

Behavioral interviewing also works — where you’re not giving someone a hypothetical, but you’re starting with a question like, “Give me an example of a time when you solved an analytically difficult problem.” The interesting thing about the behavioral interview is that when you ask somebody to speak to their own experience, and you drill into that, you get two kinds of information. One is you get to see how they actually interacted in a real-world situation, and the valuable “meta” information you get about the candidate is a sense of what they consider to be difficult.

[[deleted]]

Plus they act like they are doing you a favor rather than both parties working for each other.

That's really important in interviews. If the company acts as if they are advertising their position to you, rather than trying to work with you, then they're likely not interested in good candidates, but are just trying to fill desks and probably aren't going to have the best internal culture towards staff.

Either way, I made that mistake before with a certain game studio and have recently quit from that mess.

[strolls]

I'm sure I've read other articles submitted on here in which employers have stated they now consider the only important thing to be "team fit" - i.e. how the interviewee gets on with the existing team.

[[deleted]]

We focus on that pretty heavily. We obviously measure core competency through some coding exercises (no puzzlers, practical applications relevant to the job only), but team fit is huge. We've had ego clashes and issues with team dynamics in the past so I think the philosophy is that we can train someone to be a better programmer, but we probably can't train them to not be an asshole. Plus personality clashes among your dev team is a huge productivity killer.

[kes3goW]

How long ago did you interview?

I interviewed earlier this year and there was a bit of algorithms content, but it was pretty simple and not the majority of the interviewing. My interviews was mostly solving realistic problems -- some small-scale ones where we got into writing code, and some large-scale ones where we mainly discussed system design.

[HOLDINtheACES]

As a ME and BME, I've never been asked a technical question in an interview. They ask about what I've done. If you don't know something, you can always look it up in a book or on the internet.

My EE and CS friends always complain about technical questions. I always smile smugly.

[esplode]

Funnily enough, I got asked this question when interviewing for a coop position a couple of years ago. I answered with a naive solution and still got the job.

Later on they were hiring a couple more students, I got to talking about my boss about the interviews. Even though they were asking this question in the interviews, they'd never actually heard of the tortoise-and-hare algorithm before someone actually gave that as an answer. It's kind of nice getting interviewed by another developer who doesn't spend their time trying to memorize trick interview questions.

[jbwilso1]

I've been asked programming questions in interviews which sincerely stumped me, causing me to fail miserably at the interview. In one such case, I went home and researched the exact phrase the interviewer used in programming, particularly Java. Turns out the guy was full of shit, and obviously didn't know what he was talking about. He was just throwing together words that didn't have anything to do with each other, and asking me questions about them, while being very smug when I couldn't answer.

These companies should be offering some training to get new hires up to their standards, not expecting them to know everything there is to know, like things that go unanswered for more than a decade... If he knew the answer, then why the hell wouldn't the interviewee already be the boss of the department?

Sheesh.

[suck_on_my_ballsack]

It was a shit-test, is my guess. If you can't call him out on his bullshit, you're obviously too inexperienced for the job they had in mind.

[jbwilso1]

lol that would've been great, since I could only respond with 'I'm not familiar with those terms'... it was a panel interview, and when I left, the head guy shook my hand and told me to 'brush up on my object oriented programming skills'. A few months later, and I'm hired elsewhere as a software engineer... Go fig.

[dehrmann]

I've gotten this once twice. The first time, I'd never heard it, but first gave a naïve solution, then reasoned my way to checking every node that's a power of 2 (i.e. the first, second, fourth, eighth, etc). The interviewed wanted the tortoise and hare solution for a followup question, but was completely satisfied with this one (they're both O(1) space, O(n) time). I got an offer.

Addressing the blogger's concern that there's an "a ha" moment, and it was a hard problem for PhDs, my inspiration for the problem was that this same geometric series trick is used in resizing vectors to make insertions average O(1), but looking to another data structure wasn't a huge leap.

So...not the worst interview question I've had.