Cracking the coding interview--Q6.1~Q6.6

Hawstein | January 5, 2013

题目6.1

Add arithmetic operators (plus, minus, times, divide) to make the following expression true: 3 1 3 6 = 8. You can use any parentheses you’d like.

题目6.2

There is an 8x8 chess board in which two diagonally opposite corners have been cut off. You are given 31 dominos, and a single domino can cover exactly two squares.Can you use the 31 dominos to cover the entire board? Prove your answer (by providing an example, or showing why it’s impossible).

题目6.3

You have a five quart jug and a three quart jug, and an unlimited supply of water(but no measuring cups). How would you come up with exactly four quarts of water? NOTE: The jugs are oddly shaped, such that filling up exactly ‘half’ of the jug would be impossible.

题目6.4

A bunch of men are on an island. A genie comes down and gathers everyone together and places a magical hat on some people’s heads ( i.e., at least one person has a hat). The hat is magical: it can be seen by other people, but not by the wearer of the hat himself. To remove the hat, those (and only those who have a hat) must dunk themselves underwater at exactly midnight. If there are n people and c hats, how long does it take the men to remove the hats? The men cannot tell each other (in any way) that they have a hat.

Prove that your solution is correct.

题目6.5

There is a building of 100 floors. If an egg drops from the Nth floor or above it will break. If it’s dropped from any floor below, it will not break. You’re given 2 eggs. Find N, while minimizing the number of drops for the worst case.

解答6.5

1
2
x + (x-1) + (x-2) + ... + 1 >= 100
(x+1)*x/2 >= 100


1
14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100


The puzzle of eggs and floors

题目6.6

There are one hundred closed lockers in a hallway. A man begins by opening all one hundred lockers. Next, he closes every second locker. Then he goes to every third locker and closes it if it is open or opens it if it is closed (e.g., he toggles every third locker). After his one hundredth pass in the hallway, in which he toggles only locker number one hundred, how many lockers are open?

解答6.6

1
1, 4, 9, 16, 25, 36, 49, 64, 81, 100


Cracking the coding interview–问题与解答

https://github.com/Hawstein/cracking-the-coding-interview