You are given a partially-ordered sequence of <i>n</i> computer science theor...
- 2013-01-04 00:41:09+0000 - Updated: 2013-01-04 00:41:09+0000
You are given a partially-ordered sequence of n computer science theory exercises, drawn from k books stacked randomly on your desk. Provide an algorithm to solve them all in O(k log n) time before your Google interview on Monday. In parallel your algorithm must entertain your five year old daughter (a rogue process who doesn't respect mutex locks on brain resource allocation) who has just come home with an adorable furry spider toy that she wants to scare you with.
Shared with: Public
- 2013-01-04 01:11:21+0000
All published problems have solutions on the internet, so a naive strategy would be to search for the answers.  This will be easier for later answers than earlier ones because it's likely that many of them will be found on the same sites.  I don't have a strong argument that this will be O(k log n) though.

The second part is a lot harder.  My best strategy there would be to use a Ouija board to summon the ghost of Richard Feynman or Martin Gardner, who could certainly explain the problems and solutions to your daughter in a playful way that incorporates the toy spider, thus freeing you to think in peace.
- 2013-01-04 01:23:08+0000
You made me laugh a lot.

I presume the expected answer is that I learn the associated computer science theory, such that my brain can group the exercises into nested categories and solve them in groups recursively. But it would be far more fun to gamify the problems as you suggest, maybe through an augmented-reality phone game, so that my daughter and I can run around and play and learn concurrently, removing the need for the exclusion locks at all. Brilliant!
- 2013-01-04 03:07:25+0000
Bring her to the interview on Monday and let her solve the problems.
- 2013-01-04 03:46:53+0000 - Updated: 2013-01-04 04:18:42+0000
Solution seems obvious: teach n - p, p <= n, problems to the daughter. Minimise p.
- 2013-01-04 10:11:28+0000
Oh, and good luck at your interview!

This post was originally on Google+