Riddles, Brain Teasers, and more...

[Tony]

Here is another Riddle/Interview question.  You have a sheet cake and there is a rectangle missing from somewhere in the cake.  The location and size of the rectangle is arbitrary.  How can you divide the cake with only one cut where the cake will be divided into two exactly equal pieces.  You cannot cut the cake horizontally.  In other words, you make a cut on the top of the cake.

I am sure a lot of people have heard this one, but it is pretty kewl.  Don't cheat and Google it.

[blacklee]

Does the cut have to be a straight line?
Are the sides of the missing rectangle parallel to the sides of the cake?

[Tony]

Does the cut have to be a straight line?
Are the sides of the missing rectangle parallel to the sides of the cake?

The cut has to be one done by a knife.  One single cut.  The rectangle can be anywhere on the cake, in any arrangement.

[Tony]

No answers?  It is a lot easier than you think.  I will give it one more day and I will post the answer.

[Justin Camerer]

You find the center of the cake (P1) and the center of the piece that had been cut out of the cake (P2). You then cut along the line from P1 to P2.

[Tony]

You find the center of the cake (P1) and the center of the piece that had been cut out of the cake (P2). You then cut along the line from P1 to P2.

Yup.  I figured either you or Grim would get it. 

[Tony]

Got another one. 

Interview Question: You have 8 balls. One of them is defective and weighs less than others. You have a balance to measure balls against each other. In 2 weighings how do you find the defective one?

[Justin Camerer]

You weigh 3 balls on each side, leaving 2 off.

If one side weighs less than the other, discard all balls except those that were on the side that weighed less. Take the remaining 3 and weigh 1 on both sides, leaving the last one off. If one side weighs less, this is the defective ball. Else, the ball you didnt weigh is the defective one.

Else, weigh the 2 balls that you didnt weigh to find the defective one..

w00t!

[Tangent Orchard]

^
Shoot, I knew that one; too late! =P

Good job on the cake one though, I couldn't figure it out.

[William Grim]

Given a set of numbers from 1 to 2^N, they are randomly ordered, and one is missing.  Find me the missing number using only one variable other than the input array and your loop counter.

Next, assume you have a set of 1 to N (note: this is not the same condition as above) unsigned numbers, and they are randomly ordered.  Assume your computer registers are of infinite size.  Find me the K missing numbers using no variables other than the input array, your loop counter, and the output array (which is write-once per cell only).

In both cases, you know what N is.

[Tony]

Given a set of numbers from 1 to 2^N, they are randomly ordered, and one is missing.  Find me the missing number using only one variable other than the input array and your loop counter.

Next, assume you have a set of 1 to N (note: this is not the same condition as above) unsigned numbers, and they are randomly ordered.  Assume your computer registers are of infinite size.  Find me the K missing numbers using no variables other than the input array, your loop counter, and the output array (which is write-once per cell only).

In both cases, you know what N is.

In the second one, k missing numbers.  So, that means there can be multiple missing numbers and we have to give them all to you inside an output array which is write-once only per cell?

[Tony]

For the first part can you just set up a loop as follows?
int sum = 0;
for(int i = 1; i <= N; i++)
{
     sum += i;
}

Then
for(int i = 0; i < inputArraySize; i++)
{
     sum -= inputArray[ i];
}

sum will be what number is missing and you only used one variable. 

I am still working on the other one.

[William Grim]

In the second one, k missing numbers.  So, that means there can be multiple missing numbers and we have to give them all to you inside an output array which is write-once only per cell?

Yes, there are K numbers, such that K is a non-negative integer.  Yes, the output array is write-once per cell, meaning once A_i is set, it cannot be changed.

[William Grim]

For the first part can you just set up a loop as follows?
int sum = 0;
for(int i = 1; i <= N; i++)
{
     sum += i;
}

Then
for(int i = 0; i < inputArraySize; i++)
{
     sum -= inputArray[ i];
}

sum will be what number is missing and you only used one variable. 

I am still working on the other one.

Yeah, that's a correct and reasonable answer.  However, can you do it in just a single loop?

[William Grim]

For a hint at solving the one with K missing numbers, maybe I should make it more clear that you can do whatever you want to the input array.