Merry Christmas

gone for the holidays...new postings to come in January.

OK, one puzzle for the holidays:

3 housemates order pizzas by delivery. The pizzas cost $30. The delivery guy brings them their pizzas, and they each pay $10 (no tip!). Upon returning to the store, the manager discovers that there was an error and they should only have paid $25. So, he gives the delivery guy five $1 bills to return. Upset that he didn't get a tip and figuring 3 people cannot split five bills anyways, the delivery guy keeps $2, and returns $3 to housemates.

So, effectively, each housemate paid $9 for pizza.
3 x $9 = $27. + $2 the delivery guy kept = $29 ?? what happened to the last dollar?

Missing Integers Part 2

A set of unique integers 1..N are randomly placed in an array of length N-2. Determine which two integers are missing.

Try and come up with multiple solutions improving upon space/time complexity. You should be able to do this with constant space and a single pass. Can you solve it for N-3? 4?

this is a slightly modified version of a question asked in a Google interview

Missing Integers Part 1

A simple one today.

A set of unique integers 1..N are randomly placed in an array of length N-1. Determine which integer is missing.

Try and come up with multiple solutions improving upon space/time complexity. You should be able to do this with constant space and a single pass.

Greedy Pirates

You are the leader of 999 other pirates (making 1000 in total). You recently captured 1000 gold pieces and now need to divide the spoils between all your fellow pirates.

If a majority of the pirates agree with your scheme, then the gold will be distributed in that manner. If, however, majority disagree, then they will rebel and throw you overboard, leaving the next leader in line to propose a better plan which again will be voted upon. The leader will get the tie breaking vote.

You, like the rest of the pirates, are greedy and want the most for yourself. Your fellow pirates are all equally smart and will only vote for a scheme if they believe that is the most they will get. They will vote against you if they believe the next leader would propose a plan in their favour.

How much gold will you get to keep and how will you distribute the gold to the rest of your fellow pirates? Can you mathematically prove your solution is optimal?

Crossing a Dark Bridge Quickly

Four people are trying to cross a narrow broken bridge in the middle of the night. It is very dark, so they need a flashlight in order to see where all the broken planks are when crossing the bridge. Luckily, they have a flashlight, but only one. Unfortunately, the bridge can only support two people at a time, so they can at best cross in pairs.

The four people can walk across at different speeds: 1, 2, 5 and 10 minutes to cross the bridge. When two people cross, they cross the speed of the slower person.

What is the fastest time possible to get all 4 people safely across the bridge?

Hint: It is less than 19 minutes.

Shuffling a Deck of Cards

Represent a deck of cards in a data structure of your choice. Defend your choice. Write a method that will randomly shuffle the deck of cards. Prove that your shuffle algorithm has a uniform distribution.

Make the Robots Crash

Two robots drop down with parachutes and they drop their parachutes where they land. They are able to move along a 1D line. They can be programmed with the following instruction set:

MoveLeft
MoveRight
GotoLine
SkipNextInstructionIfDetectParachute

The robots do not have any other instructions or extra memory. The robots do not know which side or how far the other robot starts. The 1D line is infinite.

Program the robots to collide with each other.

Authentication Schemes

Two parties are trying to authenticate each other using a shared private key. Listed below are two possible schemes for authenticating.

Scheme 1:

1. A -> Establish Connection -> B
2. A -> Send Challenge (X) -> B
3. A <- Send Response Encrypted(X) <- B
4. A validates encryption
   
5. A <- Send Challenge (Y) <- B
6. A -> Send Response Encrypted(Y) -> B
7. B validates encryption
8. Authenticated!
   

Scheme 2:

1. A -> Establish Connection -> B
2. A <- Send Challenge (X) -<- B
3. A -> Send Response Encrypted(X) -> B
4. B validates encryption
   
5. A -> Send Challenge (Y) -> B
6. A <- Send Response Encrypted(Y) <-B
7. A validates encryption
8. Authenticated!
   

Can either or both be exploited? How? Are there multiple vulnerabilities?

Find the logic bug

the following is java code:

switch (num) {
case 13:
System.out.println("yay! num is thirteen!");
case 27:
System.out.println("num==twenty-seven!");
default:
System.out.println("what a boring number");
}

the syntax is correct. Given a proper program body, it will compile and run. However, there is still a bug in the code. What's the logic bug? Why would the java allow this to compile? What is a use case for this language feature?

Unrotating a Sorted Array

given a sorted array of length N, that is rotated by X spots. find X.

ie. original sorted array: 1-4-10-25-39-42-55-99
rotated by 3 gives: 25-39-42-55-99-1-4-10

this was given as a microsoft intern interview question

Line Segment in a Triangle

given 3 points that define a triangle and 2 points that define a line segment, write a function that returns true iff the line segment is contained within the triangle.

this was a microsoft intern interview question

23 Prisoners and 2 Switches

you are one of 23 prisoners who have been given an opportunity for release if you are able to complete the following challenge:

• all prisoners will be completely isolated into their own cells, with absolutely no communication with one another
• there is a room with two switches (think light switch)
  
• at a random time, a random prisoner is taken from their cell to the switch room, where they must flip one of the switches [and only one]. they are then led back to their cell.
  
• the prisoner selection is random and the same prisoner will likely visit the switch room numerous times
• if at any time a prisoner declares that they have all been to the switch room and he is correct, then they are all set free. if he is incorrect, they will all be executed.

you, as the leader, must devise a fool proof plan...
[ there is a solution to the problem as stated, you do not need to bend the rules or find a loop hole. ]