Katkat
Back

Find minimum racks for 2D bin packing

AccentureSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This question evaluates understanding of combinatorial optimization and multi-dimensional bin packing, assessing algorithmic design, resource-allocation reasoning, and computational complexity awareness.

You are given N machines. Machine i requires two types of resources: (x_i, y_i). Each rack has capacity (A, B) for the two resources, and a machine must be placed entirely within a single rack. Multiple machines can share a rack as long as the sum of their resource requirements in each dimension does not exceed the rack capacity.

Return the minimum number of racks needed to place all machines.

Notes:

  • All racks are identical.
  • You may assign machines to racks in any grouping/order.
  • The naive approach is brute force / bitmask DP over subsets. Can you design a more efficient algorithm (or improved DP) and analyze its time complexity under reasonable constraints (e.g., N up to ~20–25 for exact solutions, or larger if using approximation/heuristics)?