You are given a partially-ordered seque

Tim Hutton - 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

+1'd by: Gitesh Khodiyar, Taivo Lints, Jeremy Gomez, Nick Holder, Susanta Dutta, btxsqdr, Jochen Fromm, Paul Fisher, Hiroki Sayama, Ozymandias Haynes

Ozymandias Haynes - 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.

Tim Hutton - 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!

Hiroki Sayama - 2013-01-04 03:07:25+0000

Bring her to the interview on Monday and let her solve the problems.

Noon van der Silk - 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.

Ozymandias Haynes - 2013-01-04 10:11:28+0000

Oh, and good luck at your interview!

This post was originally on Google+