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:
Post a Comment