← Uber Interview InsightsSoftware Engineer

Uber·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
Jun 2026

Summary

Uber coding screen for a software engineer role. One algorithmic problem, bit manipulation flavored, the kind that looks like a math puzzle until you realize it isn't.

Questions Asked (1)

Q1

Given a positive integer n, you can add or subtract any power of 2 in a single operation. What is the minimum number of operations needed to reduce n to zero?

Algorithms & Data Structures
Author's notes

My first instinct was greedy, just keep subtracting the largest power of 2 that fits.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Recognize that this is a shortest path problem on integers where edges represent adding or subtracting powers of 2. Use BFS from n to 0, but optimize by observing that the optimal strategy often involves rounding n to the nearest power of 2 and then recursively solving. Alternatively, derive a greedy algorithm based on binary representation: the minimum operations equals the number of 1s in the binary representation of n after repeatedly applying the rule that two consecutive 1s can be replaced by a single 1 at the next higher bit (carry).

Pro tip: Start by testing small values to identify the pattern: the answer is the minimum number of powers of 2 needed to represent n with signs, which is equivalent to the number of nonzero digits in the non-adjacent form (NAF) of n. Mentioning NAF demonstrates deep understanding and can lead to an efficient O(log n) solution.

1. Clarify the problem

Restate the problem: we can add or subtract any power of 2 (including 2^0=1) in one operation, and we want to reduce n to 0 with minimum operations. Confirm that powers of 2 can be used multiple times and that negative results are allowed intermediate.

2. Explore small examples

Compute the minimum operations for small n (e.g., 1,2,3,4,5,6,7,8) manually to identify a pattern. For instance, n=3 requires 2 operations (3-2=1, 1-1=0) or (3-1=2, 2-2=0), while n=7 requires 2 operations (7-8=-1, -1+1=0).

3. Relate to binary representation

Observe that the problem is equivalent to representing n as a sum of signed powers of 2 with minimum number of terms. This is exactly the non-adjacent form (NAF) representation, which minimizes the number of nonzero digits.

4. Derive an algorithm

Describe a greedy algorithm: while n > 0, if n is odd, choose to add or subtract 1 based on which makes n divisible by 4 (or based on the next bit), then divide by 2. Count the operations. Alternatively, use BFS with memoization for small n, but note that greedy is optimal.

5. Analyze complexity and edge cases

The greedy algorithm runs in O(log n) time and O(1) space. Discuss edge cases: n=0 (0 operations), n=1 (1 operation), and large n (e.g., 10^9) to show efficiency.

Key Points to Mention

  • The problem is equivalent to finding the minimum number of signed powers of 2 that sum to n.
  • The non-adjacent form (NAF) of an integer minimizes the number of nonzero digits, which directly gives the minimum operations.
  • A greedy strategy: when n is odd, choose to add or subtract 1 to make n divisible by 4, then halve n; repeat until n=0.
  • The greedy algorithm is optimal and runs in O(log n) time.
  • Edge cases: n=0 requires 0 operations; n=1 requires 1 operation; powers of 2 require 1 operation.
  • The answer can also be computed by counting the number of 1s in the binary representation after applying the transformation: replace each pair of consecutive 1s with a single 1 at the next higher bit (carry).

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