Saturday, December 11, 2010

Longest sequence of d-dimensional boxes fitting into each other

Interview question :
You have 'n' d-dimensional boxes.
You have to find out the longest sequence
of boxes which fit into each other.

Hints :
1. How do you say that whether a 3-d box
fits into another?
2. Extend it to d-dimensions.
3. It's possible to do a bfs on a directed-acyclic-graph
without keeping a 'visited' lookup table, since it will
never go in an infinite loop.
4. Finding longest path in a graph is NP-complete.

No comments:

Blog Archive