Puzzles.page

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>
- 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
- $n$ary 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<A_j$ (harder: in $O(n)$!)
- 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?

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?

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

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

General math
============

- 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))`