← Accenture Interview Insights

Accenture·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
May 2026

Summary

Accenture software engineer interview with a combinatorial optimization problem that honestly had me second-guessing whether I even understood the constraints correctly. The problem was more involved than typical coding rounds and pushed into algorithm design territory.

Questions Asked (1)

Q1

You have N machines, each requiring two types of resources (x_i, y_i). Each rack has a fixed capacity (A, B) across those two dimensions, and a machine must fit entirely in one rack. Multiple machines can share a rack as long as their combined resource usage stays within the rack's limits. What is the minimum number of racks needed to place all machines, and can you do better than a brute-force bitmask DP over subsets?

Algorithms & Data StructuresTechnical Trade-offs
Author's notes

I knew immediately this was a bin packing variant and that brute force over subsets would be exponential, which I said out loud.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, clarify that this is a 2D bin packing problem, which is NP-hard, so exact solutions are exponential. Then, discuss the brute-force bitmask DP over subsets (O(3^N)) and explain its limitations, and finally propose better approaches like branch-and-bound, approximation algorithms, or heuristics for practical use.

Pro tip: Acknowledge the NP-hardness and focus on practical trade-offs: for small N, use DP with pruning; for large N, use heuristics like First-Fit Decreasing with 2D constraints, and mention that the problem can be modeled as a graph coloring or set cover problem.

1. Clarify the problem and constraints

Restate the problem as 2D bin packing with fixed bin capacities (A, B) and items (x_i, y_i). Ask about the expected size of N and whether an exact or approximate solution is needed.

2. Discuss brute-force bitmask DP

Explain that a bitmask DP over subsets can solve the problem in O(3^N) time by precomputing valid subsets that fit in one rack, then finding the minimum partition. Note that this is only feasible for N up to ~15-20.

3. Propose better exact algorithms

Mention branch-and-bound with pruning, or integer linear programming (ILP) formulations that can solve larger instances optimally. Also note that the problem is NP-hard, so no polynomial-time exact algorithm is likely.

4. Suggest approximation and heuristic methods

For large N, recommend heuristics like First-Fit Decreasing (FFD) adapted to 2D, or metaheuristics like simulated annealing. Discuss approximation ratios and practical performance.

5. Conclude with trade-offs and recommendations

Summarize that the choice depends on N and required optimality: use DP for small N, ILP or branch-and-bound for medium N, and heuristics for large N. Emphasize that the problem is NP-hard, so trade-offs are inevitable.

Key Points to Mention

  • The problem is 2D bin packing, which is NP-hard.
  • Brute-force bitmask DP over subsets has O(3^N) time complexity and is only feasible for small N.
  • Exact methods like branch-and-bound or ILP can handle larger instances but may still be exponential.
  • Heuristics like First-Fit Decreasing (FFD) can provide good approximations quickly.
  • The problem can be modeled as set cover or graph coloring, offering alternative perspectives.
  • Practical solutions often involve a hybrid approach: use exact methods for small N and heuristics for large N.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.