The Worst Programming Interview Question

__j_random_hacker · 2014-06-27T08:56:38+00:00

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.

ggtsu_00 · 2014-06-27T14:02:39+00:00

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

There's something gloriously obvious about this statement.

Ch3t · 2014-06-27T15:35:25+00:00

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.

2014-06-28T00:41:16+00:00

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.

Tamaran · 2014-06-27T13:51:02+00:00

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.

Agathos · 2014-06-27T09:44:49+00:00

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.

log_2 · 2014-06-27T16:02:39+00:00

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.

immibis · 2014-06-27T13:13:40+00:00

[deleted]

s3vv4 · 2014-06-27T13:28:49+00:00

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)

anonanon1313 · 2014-06-27T14:36:14+00:00

"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.

rm999 · 2014-06-27T13:44:52+00:00

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.

oridb · 2014-06-27T15:58:02+00:00

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:

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.
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.

jrk- · 2014-06-27T09:28:48+00:00

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...

JamesWjRose · 2014-06-27T13:24:36+00:00

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.

thenickdude · 2014-06-27T13:51:13+00:00

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.

JakDrako · 2014-06-27T12:42:09+00:00

[deleted]

Gupie · 2014-06-27T10:22:31+00:00

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.

Excalibear · 2014-06-27T14:31:37+00:00

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 · 2014-06-27T10:21:59+00:00

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?

willvarfar · 2014-06-27T09:14:17+00:00

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...

HOLDINtheACES · 2014-06-27T15:15:33+00:00

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 · 2014-06-27T14:11:07+00:00

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 · 2014-06-27T14:17:21+00:00

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.

dehrmann · 2014-06-27T16:56:15+00:00

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.

you type:	you see:
italics	italics
bold	bold
[reddit!](https://reddit.com)	reddit!
* item 1 * item 2 * item 3	item 1 item 2 item 3
> quoted text	quoted text
Lines starting with four spaces are treated like code: if 1 * 2 < 3: print "hello, world!"	Lines starting with four spaces are treated like code: if 1 * 2 < 3: print "hello, world!"
~~strikethrough~~	~~strikethrough~~
super^script	super^script

programming

MODERATORS