# Puzzles

# Riddles

- given two ropes that burn in 60m (non-uniformly), measure 15m
- with 2 eggs, what’s min # steps to find the floor in a 100-fl bldg at which dropping eggs breaks the eggs?
- what’s smallest # yes/no questions to ask to determine a birthday if you have to prepare all the questions up-front (can’t ask dynamically)? what are those questions?
- min # weighings to find fake (lighter/heavier) coin out of 12
- hat puzzle: n prisoners given black/white hat. can’t see own hat but can see others’. no communication. at least one must correctly say own hat color, else all executed. given prep planning time before test begins/hats given.
- num points on earth where going 1mi south, east, north goes back to origin
- (optimal stopping) given a sequence of n ppl to date, where ppl are totally-ordered in how good a match they are for you, how many to reject/skip to maximize prob of accepting the best person?
- 25 racehorses, 5 tracks, fewest # races to find top 3
- num ways to climb n steps if you take 1-2 steps at a time?
- min # balance weighings to find heavier ball of 8? of 13? of n?
- 3 black hats, 2 white hats, 3 men in a line facing forward (can’t see behind), each wearing a hat. they guess at their own hats. man in back says “i don’t know,” middle says “i don’t know,” front says “i know” - how does he know?
- how many ways are there to walk up s steps if you can take 1 or 2 at a time?
- A princess lives in a row of 17 rooms. Each day, she moves to adjacent room. Prince has 30 days to find her and can check one room per day. Does he have enough time?
- http://www.tanyakhovanova.com/Puzzles/
- http://www.ocf.berkeley.edu/~wwu/riddles/intro.shtml
A pile of 1,000 coins is split into two piles x and y. Multiply those together to get a number x*y.

Subdivide each of the two piles further and get a number for each pile. (Say you divide x to get the number x1

*x2, and y to get the number y1*y2)Repeat the process until there are 1,000 piles, each with 1 coin.

Add all of the numbers together. What is the sum??

Does the answer change depending on how you split the pile?

Bonus question: You have a line segment of length 1. You divide it into two pieces x and y to get the number xy. Divide each smaller piece and repeat the process. If you add up all the numbers, what is the limit?

Every man in a village of 100 married couples has cheated on his wife. Every wife in the village instantly knows when a man other than her husband has cheated, but does not know when her own husband has. The village has a law that does not allow for adultery. Any wife who can prove that her husband is unfaithful must kill him that very day. The women of the village would never disobey this law. One day, the queen of the village visits and announces that at least one husband has been unfaithful. What happens?

if prob of seeing car on highway in 30m is .95, prob of seeing car in 10m?

Fitch Cheney’s 5-card trick:

The question concerns a “magic trick” involving playing cards, a standard 52-card deck. There are two magicians, and they are working together.

The first magician finds a member of the audience and asks them to pick out 5 cards from the deck and hand them back to him. The magician takes a look at the 5 cards, chooses one of them, and hands it back to the audience member, asking him to look at it and hold on to it. This is the secret card.

The first magician then takes the remaining four cards, arranges them in some order and hands them to the second magician, who upon receiving the four cards is able to magically tell everyone what the secret card is! ** Tada! **

# Game theory

dividing pizza: I’ll slice, and we’ll take turns picking in a circle (only adj pieces), you pick first; better to have me odd or even num slices?

cannibals:

A traveler gets lost on a deserted island and finds himself surrounded by a group of n cannibals.

Each cannibal wants to eat the traveler but, as each knows, there is a risk. A cannibal that attacks and eats the traveler would become tired and defenseless. After he eats, he would become an easy target for another cannibal (who would also become tired and defenseless after eating).

The cannibals are all hungry, but they cannot trust each other to cooperate. The cannibals happen to be well versed in game theory, so they will think before making a move.

Does the nearest cannibal, or any cannibal in the group, devour the lost traveler?

# Number theory

- prove: for all ints A,B, there exist ints C,D such that 2(A^2+B^2)=C^2+D^2
- eg, 2(4^2+7^2)=3^2+11^2

# Algorithms

- how do you incrementally extend a hashtable?
- how to reverse the words in a string?
- binary search for circularly sorted array
- nary search in 2D matrix where rows/cols are ordered
- given an array of n positive numbers A, return array of n numbers where element i is the product of all numbers in A except for element A_i. now do it when you have no division. now do it when you have no multiplication.
- given a set of strings xs and a string y, return subset of xs that are substrings of y
- come up with a O(n \log n) algo for computing kendall-tau
- distance-maximizing problem: given an array A of integers, find the maximum j-i where A_i (harder: in O(n)!)
- find max-sum sub-array
- find the
*majority*element in a stream - longest palindromic substring: brute force, then in O(n^2) time/space, then in O(1) space, then in O(n) time/space (hard)
- how to reverse bits in an int? (hint: use xor to swap pair of bits)
- Out of a thousand identical buckets of water, exactly one contains a poison that will kill a pig in exactly 30 minutes. What’s the minimum number of pigs you need to determine which bucket is poisoned in 30m? an hour?
- how to sample non-uniform discrete dist in const time? (may need handholding)
- find # pairs of isomorphic words given set of words
- how to find sliding window max over list? (harder: in O(n)!)
- with a dict, segment a string without spaces into words (http://thenoisychannel.com/2011/08/08/retiring-a-great-interview-problem/)
- (similar to above) given a phone number, a function from digits to characters, and a function from dict words to scores, what’s the max-score word it spells? what’s the max-score phrase it spells?
- shuffle an array
- given axis-aligned rects, find overlapping pairs
- given unsorted array of ints where each int appears twice, except for one int that appears once. find this int. O(n) time & O(1) space!
- how many ints in [x,y] are palindrome & square of palindrome? (up to 10^100)
- given array of length n containing ints in [1,n-1], find the duplicate in O(n) time and O(\log n) space

# Probability

- toss m balls into n bins; how many bins will be non-empty?
- m bins; how many balls to toss so that k of them are non-empty?
- Say companies have to give a holiday to everyone whenever one employee has a birthday. Other than those holidays, employees work every day. If a company wants to maximize the expected total number of man-hours worked per year, how many employees should it hire?
- birthday problem: computable
- hat problem/matching problem
- setup: 1000 ppl pile their hats, then each takes one.
- how many ppl get their hat back on avg?
- prob k ppl get hat back?
- harder versions: no two people get each other’s hats either

- poisson approximation can solve the above and others (prob of drunken walker ending at start location): http://heroofourtime.blogspot.com/2010/11/birthday-problem.html
- 5 men form a circle; prob that they’re youngest-to-oldest (either dir)?
- prob of not rolling a 2 in 55 tosses of a 20-sided die is .95^55. prob of this for any of the 20 numbers?
- russian roulette: load 2 adjacent chambers. spin barrel. click. before pulling again, want to spin?
- newsvendor model: if goods are $3 to buy and $4 to sell, and you have uniform prob of selling any number 0 \le n \le 100, how many should you buy?
- holding second-price auction. a bidder costs $10 to find. bids uniform in $500-$1K. how many bidders to find?
- newton-peppys: which is more likely, at least one 6 in 6 rolls, at least two 6s in 12 rolls, or at least three 6s in 18 rolls?
- what is the avg # local maxima of a permutation of {1, \dots, n}, over all perms? maxima at ends also count. (putnam problem) http://ubpdqnmathematica.wordpress.com/2012/02/26/how-many-bumps/
One hundred people board a 100-seat airplane. The first one has lost his boarding pass, so he sits in a random seat. Each subsequent passenger sits in his own seat if it’s available or takes a random unoccupied seat if it’s not.

What’s the probability that the 100th passenger finds his seat occupied?

http://www.futilitycloset.com/2012/02/29/all-aboard-5/- If a particle starts at position n and at each time t=0,1,2,\dots it moves up/down with prob .5 then what’s prob of reaching 0 before t=1000?
drawing 2 cards at a time from deck. if both red, you keep pair; if both black, i keep pair. if mixed, discard. you win $10 if you end w more pairs. what’s a fair game entry price? http://mindyourdecisions.com/blog/2012/04/23/monday-puzzle-pairs-of-cards/

# Geometry

You are in a boat exactly at the center of a perfectly circular lake. On the shore, there is a thief who wants to take you hostage.

You can run faster than the thief, if you make it to shore. But the thief can run 4 times as fast as you can row. The thief cannot swim and doesn’t have a boat.

Can you escape the thief?

http://mindyourdecisions.com/blog/2011/05/25/puzzle-escaping-a-thief/

can you draw a curve that crosses each border once?

`+------+------+ | | | +----+-+-+----+ | | | | +----+---+----+`

http://mindyourdecisions.com/blog/2011/06/15/a-fun-graph-theory-puzzle/

moat-crossing problem: in rect castle/moat where moat is 20ft wide, how to cross moat w 2 19ft planks? http://mindyourdecisions.com/blog/2012/03/05/monday-puzzle-the-moat-crossing-problem/

a perfectly round grapefruit has 5 stickers. prove it can be cut in 2 equal halves where one has 4 of the stickers. (a sticker along the boundary is considered to be on both halves.) http://mindyourdecisions.com/blog/2012/04/02/monday-puzzle-fruit-label-stickers/

divvy up equilateral triangle by letting A then B pick points; they’re given all area closer to their point; who has advantage? http://mindyourdecisions.com/blog/2012/04/17/a-location-game-on-a-triangle/

A group of 10 people sits down at a wedding table. Only after sitting do they realize the seats had name tags, and no one was sitting in the correct seat. Prove that there is a way to rotate the seating order so that at least 2 people will be in their correct seats. http://mindyourdecisions.com/blog/2012/10/29/monday-puzzle-wedding-seating-arrangement/

# Practical

- 3 switches in room A, 3 bulbs in room B. how to tell which switches go to which bulbs if you’re in room A, can move to room B, but can’t go back to room A? http://blogs.msdn.com/b/ericlippert/archive/2011/02/14/what-would-feynman-do.aspx
which is the correct answer on this test question?

- 今天是个女日子，因为我在可逻辑学。
- 今天是个好日子，因为我在学逻辑学。
- 今天八个好日子，因为令在学逻辑学。

http://mindyourdecisions.com/blog/2011/05/30/using-logic-to-solve-a-test-question/

# General math

- in evenland, only even numbers exist. primes are numbers that cannot be represented as a product of two smaller numbers. in our world, numbers have a unique prime factorization; in evenland, numbers can have multiple prime factorizations. what’s the smallest such number?
- find x if x^{x^{x^\dots}} = 2
- find all real/complex roots of x^6 = 64
- hour/minute hands of clock meet at 12:00; when will they first meet again?
- 3 points randomly drawn on circle; prob of them being on same semi-circle?
- unit length broken off into 3 pieces; prob of forming triangle?
- \sqrt{2 + \sqrt{2 + \sqrt{2 + \dots}}}
- You have 5 unknown numbers. There are 10 options in selecting two out of these five. Sum each of those two together, thus you have 10 numbers. You’re given these, find the original 5 numbers.
Given two vectors x,y of N elements where first M are numbers and remaining are letters from an alphabet, want to find:

`distance(x,y) = l1_distance(x[1..M], y[1..M]) + hamming_distance(x[M+1..N], y[M+1..N])`

E.g.,

`hamming_distance([a,b,c], [a,a,c]) = 1`

What f will let us compute this using just L1 distance?

`distance(x,y) = l1_distance(f(x), f(y))`

how many 0s are there in 100!?