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.