gXa's blog

Interview Question

By gXa, history, 8 years ago, In English

You are given a lot of cuboid boxes with different length, breadth and height. You need to find the maximum subset which can fit into each other (length, breadth and height of first block greater than length, breadth and height of second block).

For example:

If Box A has LBH as 7 8 9

If Box B has LBH as 5 6 8

If Box C has LBH as 5 8 7

If Box D has LBH as 4 4 4

then answer is A,B,D

Now, algorithm is first sort in terms of length, then find MIS of breadth and from previous result find MIS of height, however order can play a role here.

So, it is requested if someone can give a proper algorithm for this.

  • Vote: I like it
  • +4
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You can solve it using 2D-Fenwick Tree.
Here is my code

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it -18 Vote: I do not like it

    It is requested if you can provide answer in terms of longest increasing sequence rather than using advance data structures?

    → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Think about solving this problem for squares, not cubes.

Try to solve this problem by sorting and using a Fenwick-tree. Any k-dimensional instance of this problem will be solvable using the same ideas.

It can be helpful to try to solve MIS using a Fenwick-tree.

→ Reply