Uber·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Jun 2026

Summary

Uber SWE interview with a disk defragmentation problem. Pretty algorithmic, not the kind of thing you use day to day, but it made sense once I stopped overthinking it.

Questions Asked (1)

You're given a disk represented as an array of cells, where each cell is either free or occupied by a file. Write a solution to defragment the disk so all occupied cells end up contiguous, using the minimum number of moves.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

My first instinct was to just sort the array somehow, but that misses the point entirely since you need to count or minimize actual move operations.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Clarify the problem constraints (e.g., definition of a move, whether swaps or shifts are allowed) and then propose an optimal algorithm such as two-pointer compaction or counting inversions. Explain the time and space complexity, and discuss trade-offs between different approaches.

Pro tip: Mention that the minimum number of moves equals the number of inversions between the current arrangement and the target compact arrangement, and that this can be computed efficiently without simulating each move.

1. Clarify the problem

Ask questions to understand what constitutes a move (swap, shift, or block move), whether the order of files must be preserved, and the expected input/output format.

2. Identify the target arrangement

Determine the contiguous block of occupied cells that minimizes moves, typically by preserving the relative order of files and choosing the position that minimizes total distance.

3. Choose an algorithm

Select an efficient method such as two-pointer compaction for O(n) time, or counting inversions for O(n log n) time, depending on the move definition.

4. Analyze complexity and trade-offs

Discuss time and space complexity of the chosen approach, and compare with alternatives like sorting or greedy shifting.

5. Test with edge cases

Validate the solution with cases like all free, all occupied, alternating, and large inputs to ensure correctness and performance.

Key Points to Mention

Definition of a move: swap vs. shift vs. block move, and whether order preservation is required.
Minimum moves equals number of inversions between current and target arrangement.
Two-pointer technique for O(n) compaction when shifting is allowed.
Counting inversions using merge sort or Fenwick tree for O(n log n) when swaps are allowed.
Trade-offs between time complexity and implementation simplicity.
Edge cases: empty disk, full disk, already compact, and large input sizes.

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