Bytedance·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Jun 2026Remote

Summary

Bytedance SWE coding round, one BFS problem the whole time. I hadn't interviewed in ages and it showed. The interviewer was patient but I fumbled through the logic and needed a bunch of hints before we moved on.

Questions Asked (1)

You have two cups of sizes x and y and unlimited water. You can fill a cup, empty a cup, or pour from one into the other. Can you measure exactly z units of water, and if so, what is the minimum number of operations to get there?

Algorithms & Data Structures

Author's notes

Classic water jug BFS and I still botched it.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the problem as a graph where states are the amounts in each cup, and edges are operations. Use BFS to find the shortest path to any state where one cup contains exactly z units. If no such state is reachable, conclude it's impossible.

Pro tip: Before coding, mention that the problem is equivalent to the classic water jug puzzle and that a solution exists if and only if z is a multiple of gcd(x, y) and z ≤ max(x, y). This shows mathematical insight and can save time.

1. Understand the problem and constraints

Clarify that cups have capacities x and y, initially empty, and operations are fill, empty, and pour until source empty or destination full. The goal is to measure exactly z units in either cup.

2. Check feasibility using GCD

Compute g = gcd(x, y). If z is not a multiple of g or z > max(x, y), then it's impossible. Otherwise, a solution exists.

3. Model as a graph and apply BFS

Represent each state as (a, b) where a and b are current amounts. Use BFS from (0,0) to find the shortest sequence of operations to reach any state with a == z or b == z.

4. Optimize and handle edge cases

Use a visited set to avoid cycles. Consider symmetry: if z can be measured in one cup, the other cup may also work. Also handle z = 0 (0 operations) and z > max(x, y) (impossible).

5. Return the minimum operations or -1

If BFS finds a target state, return the number of operations (depth). If the queue exhausts without finding, return -1 (though feasibility check should prevent this).

Key Points to Mention

The problem is a classic water jug puzzle and can be solved using BFS on state space.
Feasibility condition: z must be a multiple of gcd(x, y) and z ≤ max(x, y).
State representation: (amount in cup x, amount in cup y).
Operations: fill x, fill y, empty x, empty y, pour x->y, pour y->x.
BFS guarantees minimum number of operations because each edge has unit cost.
Edge cases: z = 0, z > max(x, y), and x = y.

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