← Microsoft Interview Insights

Microsoft·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
Apr 2026

Summary

Microsoft SWE interview with a classic water jug puzzle. Not the most complex problem on paper but it pushed me to think more carefully about GCD and reachability than I expected.

Questions Asked (1)

Q1

You have two empty jugs with capacities A liters and B liters, and unlimited water. How do you measure out exactly X liters?

Algorithms & Data Structures
Author's notes

My first instinct was to just describe the fill-and-pour steps without thinking about whether X was even achievable.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the problem as a state-space search where each state is the amount of water in each jug, and transitions are fill, empty, and pour operations. Use BFS to find the shortest sequence of operations that results in exactly X liters in one jug, and explain the mathematical condition for solvability (X must be a multiple of gcd(A, B) and ≤ max(A, B)).

Pro tip: Mention that this is a classic problem solvable by the Euclidean algorithm, and that BFS guarantees the shortest solution, which is often expected in interviews. Also, clarify any assumptions about X (e.g., X ≤ max(A,B)) before diving into the solution.

1. Clarify the problem and constraints

Ask if X must be measured in one jug, if jugs can be partially filled, and if X is guaranteed to be achievable. Confirm that operations are limited to filling, emptying, and pouring between jugs.

2. Check feasibility using GCD

Explain that X must be a multiple of gcd(A, B) and ≤ max(A, B) for a solution to exist. This shows mathematical insight and avoids wasting time on impossible cases.

3. Model as a state-space search

Define states as (a, b) where a and b are current amounts in jugs A and B. List possible transitions: fill A, fill B, empty A, empty B, pour A→B, pour B→A.

4. Apply BFS to find shortest sequence

Use BFS from initial state (0,0) to find the shortest path to any state where a = X or b = X. Explain that BFS guarantees minimal number of operations.

5. Present the solution and discuss complexity

Walk through the sequence of operations for the given A, B, X. Mention time complexity O(A*B) and space complexity O(A*B) for BFS, and note that a more efficient solution exists using the Euclidean algorithm.

Key Points to Mention

  • The problem is a classic state-space search and can be solved with BFS.
  • Feasibility condition: X must be a multiple of gcd(A, B) and ≤ max(A, B).
  • Operations allowed: fill a jug, empty a jug, pour from one jug to another until source empty or destination full.
  • BFS guarantees the shortest sequence of operations.
  • Alternative approach: use the Euclidean algorithm to derive the solution directly.
  • Time and space complexity of BFS is O(A*B), which is acceptable for small capacities but may be optimized.

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