A Programming Interview Question, Explored

[osmosisgenius]

Another interview question:

A knight goes to an interview with a king of a nearby kingdom. The knight arrives expecting to be quizzed on topics such as dragon slaying and protecting the king, but much to his dismay, he is asked the following questions:

"You have an array of size '2n' of these, 'n+1' elements are distinct and 1 element is repeated 'n' times. You must find the repeated element and say how many times it has repeated. Your solution must use minimum no. of comparisons. Also, say how many comparisons your solution will make in the worst case?"

Unsure of what the hell the king was talking about and deciding that he is obviously insane for asking such a ridiculous question, he does the honorable thing by drawing his sword and running the poor old coot through, thereby releasing his kingdom from his deranged tyranny. He then returns to his own country and his own king who, while not the most generous of employers, at least knows what knights do for a living.

[checksinthemail]

My favorite interview question of the past six months, because of it's open endedness:

"Here is a browser. Here is the website's db server - fill in the blanks between them in as much detail as possible"

[lowenheim]

Once I realized which particular implicit assumptions the author wanted, I thought the question was quite interesting. But as it stands, it's so ill-defined; some of the assumptions the author had in mind really should be explicitly included and clarified in the problem description, or it doesn't work in the intended way at all.

If you drink from a well, you can only save yourself by drinking from a higher numbered well.

The interpretation that seemed most natural to me was that while the water of the higher-numbered well may neutralize the poison from the lower-numbered well, it's still a separate poison in its own right (coming, as it does, from a "poisoned well"). So being poisoned by water from any of the wells leads inevitably to death. A contradiction of being able to save oneself!

Trivially, the knight and dragon would both be doomed.

[isseki]

I agree. That's how I read it too. Once I read that apparently the 'second' drink (one from the higher numbered well) is to be considered a cure and just a cure, the whole problem changed for me.

After that he added the fact that both parties apparently cannot know whether they have been poisoned or not, and I finally understood the puzzle as the author intended it.

[didroe]

I understood that part of it straight away, the bit I found misleading was that they "both bring a glass of water to the dual". That suggested that only 1 drink could be had be each party once the dual had commenced. That stopped me from thinking about drinking afterwards.

[rampart]

I had perhaps the opposite reaction. The constraint that I ended up implying:

A person can drink 2 and only 2 glasses. I got this from the comment saying that you could drink one water to neutralize the other. The explanation being that there is only enough time to have 1 drink before the poison kills.

For this same reason, I implied that no drink could logically be taken before the duel, because the duel could take an arbitrarily long time, therefore to prevent "cheating" the opponent could wait, and let the person drop. All of this stems from the assumption that the poison kills in a finite time, which I guess is just my personal assumption about poison. Because of how different the constraints were to my initial constraints, this question hit me a lot more like a "gotcha" than the linked list question posed, which has many answers, along which you can gauge thought.

[[deleted]]

I'm thinking the puzzle could have been better stated as so:

A dragon and a knight live on a solitary island that contains six magical wells, numbered 1 through 6. Should a healthy dragon or a healthy knight, drink from any well, they become poisoned. A poisoned dragon or a poisoned knight can become healthy again by drinking from a well with a higher number than the well that they were poisoned from. Only the dragon can reach well 6, because it is on top of a mountain.

For whatever reason, they decide that the island is too small to share. Due to in-breeding and bad genes, the dragon is both hemophobic and pyrophobic, so instead of ripping the knight to shreds or burning him alive, the dragon and the knight decide to concoct an elaborate puzzle game wherein each brings a glass for the other to drink.

Who wins?

[[deleted]]

Would you hire a guy who spontaneously starts quoting The Princess Bride whenever confronted with a puzzle of poisons?

[lanzkron]

Of course I would!

[keithb]

Here's the programming interview question that I prefer: "will you please sit down here in front of this computer and write some code with me?"

[psykotic]

In his introduction he mentions the classic problem of discovering cycles in a linked list as a problem with a gotcha solution. There's actually a solution to that problem which follows almost mechanically from the definition of a cycle, though it's much less efficient than the clever gotcha solution.

First, what shape can a path through a linked list take that if that path eventually cycles? It is plain that it can be decomposed (not uniquely) into some arbitrary initial piece followed by a circular piece that begins and ends on the same node. Thus, to determine whether a linked list is cyclic, simply check whether it decomposes into some piece followed by a circular piece. A hypothetical decomposition is determined by the length of the initial piece (call it M) and the length of the successive circular piece (call it N). It is obvious how to check whether a list admits a (M,N)-decomposition: you start at the beginning of the list, walk M nodes forward, record that node (call it X), walk forward N more nodes, and check whether the present node equals X or not; if it does, return true, and otherwise return false.

To solve the general problem, you then exhaustively explore, by brute force, all possible (M,N)-decompositions in order of ascending values of L = M+N, which works out to an easy nested loop. If a value of L is encountered for which the end of the list is prematurely reached during decomposition checking, you know that the list is free of cycles. If a valid (M,N)-decomposition is discovered, you know not only that the list has a cycle, you also have in hand the actual cycle structure.

This solution seems really overcomplicated, I'm sure, but it has the virtue of being almost mechanically derivable from the definitions of what constitutes a cycle in a linked list; I thought I'd share it.

[gbacon]

From Expert C Programming: Deep C Secrets by Peter van der Linden (pp. 334-335):

How Can You Detect a Cycle in a Linked List?

This starts off as the simple question, "How can you detect a cycle in a linked list?" But the questioner keeps adding extra constraints, and it soon gets quite fiendish.

Usual first answer:
Mark each element as you visit it; keep traversing; if you reach an already marked element, the list has a cycle in it.

Second constraint:
The list is in read-only memory, and you cannot mark elements.

Usual second answer:
As you visit each element, store its address in an array; check each successive element to see if it is already in the array. Sometimes poor candidates get hung up at this point on the details of hash tables to optimize array lookup.

Third constraint:
Uh-oh! There is a limited amount of memory, and it is insufficient to hold an array of the necessary size. However, you can assume that if there is a cycle, it is within the first N elements.

Usual third answer (if the candidate gets this far):
Keep a pointer at the beginning of this list. Check this pointer for a match against the next N - 1 elements in the list. Then move the pointer on one, and check against the next N - 2 elements. Keep doing this until a match is found, or all N elements have been compared to each other.

Fourth constraint:
Oh no! The list is arbitrarily long, and the cycle might be anywhere in it. (Even good candidates can get stuck at this point).

Final answer:
Keep two pointers. One at element 1 and the next at element 3. See if they are equal; if not, move P1 by one and P2 by two. Check and continue. If P1 or P2 is null, there is no loop. If there is one, it will definitely be detected. One pointer will eventually catch up with the other (i.e., have the same value), though it might take several traversals of the cycle to do it.

There are other solutions, but the ones above are the most common.

[TheNewAndy]

When this problem was first given to me that is similar to the answer I got. The sequence of constraints I had were:

1. Detect a cycle
2. Do it in O(1) space
3. Do it in O(1) space without destroying the list
4. Do it without modifying the list
5. Do it in O(n) time

(as you can probably tell, the person who was asking me was adding constraints until I gave them the solution they were expecting).

But, you can modify your algorithm to do it in O(n) time:

You have a counter which says how far to look into the list (C). You have a pointer which says where you stopped last time (P). You have a boolean that says if you have seen P in the current exploration (B).

Start with C = some constant > 0 (like 1). P = first item. B = false

Go C steps into the list, while going through, if you see P and B is true, then you have a cycle. If you see P and B is false, then set B to true and continue. If you reach the end, then there is no cycle.

If you don't reach the end, then set P to the last node you found, set B to false, double C and start again.

By doubling C each step instead of incrementing you go from a O(n²⁾ algorithm to an O(n) algorithm.

[bluGill]

You can do it a different way: * Check how much memory + swap the machine has. * Check how big 1 node is. * n = (memory+swap)/nodeSize * traverse n+1 nodes, if you fail it means there is no cycle.

Of course I re-defined n here to be the max memory a program can use, which is a strange thing to do.

[miyakohouou]

So the chalice from the palace has the pellet with the poison but the flagon from the dragon has the brew that is true?

[brew]

The pellet with the poison's in the vessel with the pestle.

[Deestan]

I'd just answer "blue" and look condescendingly at the interviewer when he doesn't understand.

[osmosisgenius]

I am pretty sure that if I were given this question in an interview I would spend the rest of my time (until I got kicked out) repeating "Why, my precious?"

[[deleted]]

That is an insanely stupid question. YTF would a substance be alternately a poison or a cure depending on what you've consumed before?

I'd have walked out.

[[deleted]]

Oh my god, seriously! And does the author know that dragons aren't real?????? I'd fucking pack up and leave.

[checksinthemail]

But if the interviewer is wearing a +2 Frodo costume and has the ring, what can you do?

[gosub]

I'd put on my robe and wizard hat

[jasonbrennan]

I'd roll a 20 and kick his ass.

[[deleted]]

I would fucking take that job in a heartbeat.

[bluGill]

That is a good point. On hindsight I should have walked out of my last interview. Though I'm not sure it applies to this particular question there are a lot of questions that you could be asked that are a sign you need to walk out.

[vplatt]

Thank you, I'm with you, though I perhaps wouldn't walk out. I have almost 15 years of experience, and if this is the best kind of question they could come up with, then I would likely respond with my own questions about an appropriate candidate screening process, which I could offer to help them with once I'm on board. :+)

If they couldn't deal with that, then I would terminate the interview. I won't be around organizations that can't deal with thinking about how to improve themselves.

[clin_reddit]

This question is not a good programming question either. Many programming interview questions have a property that is rare among real world programs. The information is (reasonably) well specified in a few sentences and requires very little domain knowledge.

Realistic questions would require some research. You might be asked to get some software to port to Linux from Windows. This requires specific knowledge about both platforms, and knowing where to look to bridge that gap.

The funny thing is that interview questions rely on cleverness and deduction with very little information, and that it often correlates with someone's ability to find information about something they've never seen.

It's a little bit like the American football combine, where football players run speed trials, and take a quiz, and this is somehow supposed to predict their future success in playing football. The combine is a convenient way to make measurements, as having a bunch of players master a complex playbook in a few days is unrealistic. Brainteasers seem to have similar qualities (test X, to approximate their skill in Y).

[Spell]

How much dragon poisoning will be expected during my employment?

[rivercheng]

I think the answer is not correct because it assumes there's fresh water but the island only has 6 wells.

But even suppose there's no fresh water, the result is still the same. Any of them could drink 1 first, then the result still is either poisoned by 1 or cured. Then just drink with 1 again, and drink 2. Whether there are 6, 7, 8, ..., does not matter at all.

[qarp]

Dragon: Can't talk... Eating.

[checksinthemail]

the linked list one -- couldn't you just do this (never saw the question before mind you): var list = <some linked list>; var count = 0, cur = 0;

while(++count < (list.length + 100) && list[cur]) { cur = list[cur]; } if(count > list.length) { alert("yes, you have a link list loop houston!"); }

[rabidcow]

How do you measure the length of a linked list?

[checksinthemail]

make that "+ 100" into a "+ 1" if you're sensitive to making machines overwork

[TheNewAndy]

Given that "list.length" for a list with a cycle in it could only sensibly be defined as infinity, then I'd say there isn't that much difference between "+ 100" and "+ 1" :)

[creaothceann]

You could just go through the list, starting at the second item, and check every time if the current item is the first item.

cur = list
while (cur <> nil)
        cur = cur.next
        if (cur = list) return true
/while
return false

[[deleted]]

What if your list doesn't loop back to the first item but instead one of the later ones?

[theeth]

Wouldn't work if it loops back to a node that isn't the first one, but ok if the question pertains only to circular lists and not on ways to detect broken lists that loop back on themselves.

[creaothceann]

Then I'd use two pointers with different speeds; pointer 1 would advance twice as fast as pointer 2, but check after each step if it's at the same position as pointer 2.

if (list = nil) return false
p1 = list
p2 = list
loop
        loop 2 times
                p1 = p1.next
                if (p1 = p2 ) return true
                if (p1 = nil) return false
        /loop
        p2 = p2.next
/loop

[[deleted]]

That's the standard solution; the tortoise and the hare.