How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Accenture.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Accenture during technical interviews.

Find minimum racks for 2D bin packing | Accenture Coding Question

Find minimum racks for 2D bin packing

Company: Accenture

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

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)?

Quick Answer: 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 a list of `machines`, where `machines[i] = [x_i, y_i]` is the amount of two resource types that machine `i` consumes. Every rack is identical with capacity `capacity = [A, B]` for the two resource types. A machine must be placed entirely within a single rack, and any set of machines may share a rack as long as, in EACH dimension, the sum of their requirements does not exceed the rack capacity (`sum(x) <= A` and `sum(y) <= B`). Return the minimum number of racks needed to place all machines. Assume every individual machine fits within a single empty rack. This is exact 2-dimensional bin packing, which is NP-hard, so for the constraints below an exact exponential algorithm is expected. Examples: - `machines = [[1,1],[1,1],[1,1]]`, `capacity = [2,2]` -> `2` (e.g. rack1 holds two machines = (2,2), rack2 holds one). - `machines = [[2,1],[1,2],[2,1],[1,2]]`, `capacity = [3,3]` -> `2` (pair complementary machines: (2,1)+(1,2)=(3,3) each rack). - `machines = []`, `capacity = [5,5]` -> `0`.

Constraints

1 <= N <= 20 (number of machines) for the exact bitmask DP
Each machine fits in an empty rack: x_i <= A and y_i <= B
0 <= x_i, y_i and 1 <= A, B
Resource requirements and capacities are non-negative integers

Examples

Input: ([[1, 1], [1, 1], [1, 1]], [2, 2])

Expected Output: 2

Explanation: Two identical (1,1) machines fit in one rack as (2,2); the third needs its own rack. Total 2.

Input: ([[3, 3]], [3, 3])

Expected Output: 1

Explanation: A single machine that exactly fills the rack capacity needs exactly one rack.

Input: ([], [5, 5])

Expected Output: 0

Explanation: No machines means zero racks are required.

Input: ([[2, 1], [1, 2], [2, 1], [1, 2]], [3, 3])

Expected Output: 2

Explanation: Pair complementary machines: (2,1)+(1,2) = (3,3) fits one rack; the other pair fills a second. Total 2.

Input: ([[5, 5], [5, 5], [5, 5]], [5, 5])

Expected Output: 3

Explanation: Each machine alone already saturates both dimensions, so no two can share a rack. Total 3.

Input: ([[1, 3], [3, 1], [2, 2], [2, 2]], [4, 4])

Expected Output: 2

Explanation: Rack 1: (1,3)+(3,1) = (4,4). Rack 2: (2,2)+(2,2) = (4,4). Both racks are exactly full. Total 2.

Input: ([[4, 4]], [4, 4])

Expected Output: 1

Explanation: One machine exactly matching the rack capacity uses a single rack.

Hints

The naive bound is at most N racks (one machine each). The lower bound is at least 1. You want the exact minimum, and exact 2D bin packing is NP-hard — so an exponential exact algorithm is acceptable here.
Represent any group of machines as a bitmask. Precompute feasible[mask] = whether all machines in that mask fit together in ONE rack (sum of x <= A AND sum of y <= B).
DP over subsets: dp[mask] = minimum racks to pack exactly the machines in mask. Transition: pick any feasible submask 'sub' of mask to be the contents of one rack, then dp[mask] = min over sub of dp[mask ^ sub] + 1.
Iterate submasks efficiently with the trick `sub = (sub - 1) & mask`. The total work across all masks is O(3^N).

Quick Overview

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