jliszka's New Writeups

Six toothpicks solution (idea)

2003-08-15T21:53:12Z

This is a solution to problem 33 on the hard interview questions node:

The problem basically asks you to create four equilateral triangles of the same size with six toothpicks. A bit of analysis will tell us that four triangles require twelve toothpicks, and since we only have six to work with, that means each toothpick must appear in two triangles. So every triangle has to border three other triangles (one on each side).

Think outside of the plane. It's a tetrahedron (a three-sided pyramid).

Spinning disc solution (idea)

2003-05-29T23:42:04Z

This is a solution to problem 32 on the hard interview questions node. If you have not read the question, the following will make no sense to you:

Well, you can do it with two cameras:

If you fix the two cameras on two points on the disc right next to each other (but at the same distance from the center of the disc), then as the disc spins, one camera will observe the color changing just before the other. From this you can easily deduce which direction the disc is spinning.

But, you really only need one camera:

Start by fixing the camera on any point on the disc. As the disc spins, the camera will observe the color alternating between black and white. Now, move the camera around to allow the point the camera is observing to move clockwise with respect to the center of the disc, and note the rate the color changes. Move the camera in the other direction, and again note the rate the color changes. The slower rate indicates the direction the disc is spinning.

I didn't say you stole my watch (idea)

2003-05-23T22:24:24Z

A good illustration of how inflection or emphasis can significantly alter the meaning of a sentence. Read aloud:

I didn't say you stole my watch.
I didn't say you stole my watch.
I didn't say you stole my watch.
I didn't say you stole my watch.
I didn't say you stole my watch.
I didn't say you stole my watch.
I didn't say you stole my watch.

Array mode solution (idea)

2003-02-13T21:48:07Z

This is a solution to problem 31 on the hard interview questions node. If you have not read the question, the following will make no sense to you:

Starting at the beginning of the array, test consecutive pairs for equality. If, for example, a(j) == a(j+1), continue by testing a(j+1) == a(j+2), etc. As soon as a(j) != a(j+1), remove those two elements from the array (suppose it's a linked list) and continue by testing a(j-1) == a(j) (which used to be a(j+2)). Note that removing the two elements maintains the invariant that more than half of the elements have the same value. Once j is greater than half of the length of the remaining list, the element aj is the element we're looking for, since a(0) == a(1) == ... == a(j). This runs in O(n) since no element appears on the right hand side of an equality test more than once.

This problem is similar to problem 30 on the hard interview questions node, and so is the solution.

Good and bad processors solution (idea)

2003-02-13T21:23:30Z

This is a solution to problem 30 on the hard interview questions node. If you have not read the question, the following will make no sense to you:

Let the processors be numbered 1...n. Begin by asking processor 1 if processor 2 is good. If the answer is "no", remove these two processors from the list and start over. Note that you removed one good processor and one bad processor from the list, so more than half of the remaining processors are still good.

If processor 1 says processor 2 is good, continue by asking processor 2 about processor 3, 3 about 4, etc., until you get a "no" answer. Suppose it is processor j that says processor j+1 is bad. Remove both processors j and j+1 from the list (as before, more than half of the remaining processors are still good, since one of the two you removed was good and one was bad), and continue by asking processor j-1 about processor j (the processor that was after j+1 before you removed it and the…

Pythagorean triples solution (idea)

2003-02-12T18:54:34Z

This is a solution to problem 29 on the hard interview questions node. If you have not read the question, the following will make no sense to you:

First, square each element of the array. Then insert every pair of elements in the array into a hash table, using their sum as the hash code. This step is O(n²). Now, we can easily (O(n) time) test if any element in the array is the sum of a pair of elements by looking up that element in the hash table. These three elements form a Pythagorean triple.