2
\$\begingroup\$

This code is meant to compute the height for the tallest stack of boxes out of a given collection of boxes. A box has width, height, and depth dimensions. The height of a stack of boxes is the sum of all of the heights of the boxes in the stack. The boxes cannot be rotated. A box can only be stacked on top of another box if its width, height, and depth are strictly smaller.

I'm doing this to improve my style and to improve my knowledge of fundamental algorithms/data structures for an upcoming coding interview.

from operator import attrgetter

class Box:
    def __init__(self, width, height, depth):
        self.width = width
        self.height = height
        self.depth = depth

    def smaller_than(self, other_box):
        return (self.width < other_box.width and
                self.height < other_box.height and
                self.depth < other_box.depth) 

def tallest(boxes):
    boxes = sorted(boxes, reverse=True, key=attrgetter('height'))
    largest_height = 0
    for i in range(len(boxes)):
        bottom_box = boxes[i]
        total_height = bottom_box.height
        cur_top_box = bottom_box
        for j in range(i+1,len(boxes)):
            if boxes[j].smaller_than(cur_top_box):
                total_height += boxes[j].height
                cur_top_box = boxes[j]
        if total_height > largest_height:
            largest_height = total_height
    return largest_height

The question wasn't clear about how the boxes were represented or inputted. I just made them into a Box class and assumed that they were passed as a list to tallest(). If there are any better ways of representing the boxes or inputting them (especially in an interview environment) I would be happy to hear it.

I think this code has time complexity O(n^2) and space complexity O(n). Please correct me if I'm wrong. Any suggestions about how I can improve these complexities are welcome.

\$\endgroup\$
5
\$\begingroup\$

The code implements a greedy approach (to be exact, n greedy attempts): as soon as a box can be placed, it is placed. It does not necessarily give an optimal solution. For example, with the set of boxes ((height, width)):

    5, 5
    4, 1
    3, 4
    2, 3

the algorithm will only consider towers

    (5,5) (4,1)
    (4,1)
    (3,4) (2,3)
    (2,3)

but not an optimal tower

    (5,5), (3,4), (2,3)

You are right about the complexity of the algorithm, but I am afraid it is not relevant if the algorithm itself is not correct.

\$\endgroup\$
  • \$\begingroup\$ Thanks for pointing that out. I was originally going to do a dynamic programming approach of calculating the tallest stack I could make for each possible bottom box and then return the maximum. To me it seemed that it's time complexity would be large. That's why I tried something like this. Although maybe it seems that I should have done it that way instead of my 'supposedly' faster way. \$\endgroup\$ – cycloidistic Nov 26 '16 at 23:54
3
\$\begingroup\$

I feel that the Box class represent more an immutable state than a mutable one. As such, I suggest using collections.namedtuple as a base:

>>> Box = namedtuple('Box', 'width height depth')
>>> b = Box(1, 2, 3)
>>> b
Box(width=1, height=2, depth=3)

Now if you want to add method to that, just subclass it. You can also take advantage of the fact that the underlying data is indeed a tuple, hence iterable:

class Box(namedtuple('Box', 'width height depth')):
    def smaller_than(self, other):
        return all(dim < other_dim for dim, other_dim in zip(self, other))

And voilà.

>>> b = Box(1, 2, 3)
>>> bb = Box(2, 3, 4)
>>> b.smaller_than(bb)
True
>>> bb = Box(2, 3, 3)
>>> b.smaller_than(bb)
False
\$\endgroup\$
  • \$\begingroup\$ Thanks for the answer. Since the boxes are immutable I guess it does make sense to make them namedtuples. I also like how you used zip in smaller_than. That's particularly nice :) \$\endgroup\$ – cycloidistic Nov 26 '16 at 23:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.