Katkat
Back

Minimize moves to transform floor layouts

OptiverData Scientist · Online Assessment
MediumData ScientistOnline AssessmentCoding & Algorithms

Last updated

This question evaluates algorithm design and combinatorial optimization skills, focusing on reasoning about minimal moves, greedy heuristics, and proving optimality within the Coding & Algorithms domain for data-science technical roles.

You are given an initial arrangement of apartments across Floors 1–4 and a target arrangement. In one move you may reposition a single apartment to a different floor (assume any move is allowed unless it violates the target’s per-floor apartment counts). Design an algorithm to transform the initial arrangement into the target using the fewest moves. Answer the following:

  • Describe your algorithm and prove or argue its optimality.
  • Analyze its time and space complexity.
  • Evaluate the greedy strategy "fix Floor 1 first, then Floors 2–4": is it always optimal? Provide a counterexample or a proof.
  • If multiple optimal solutions exist, how would you output one sequence of moves?