Uber·Software Engineer·Online Assessment (OA)·Intermediate

IntermediatePrefer not to say

Apr 2026

Summary

Went through Uber's OA for a SWE role and got a bit-manipulation problem that looks straightforward until you hit the edge cases. The input arrives as a base-10 string which tripped me up initially, and the greedy logic for odd numbers has a subtle branch that I did not see coming.

Questions Asked (1)

Given a positive integer n (up to 2^60, passed as a base-10 string), find the minimum number of operations to reduce it to zero, where each operation adds or subtracts any power of two.

Algorithms & Data Structures

Author's notes

I recognized this as a signed-binary representation problem partway through, which helped.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the problem as finding the minimal number of signed powers of two that sum to n, which is equivalent to minimizing the Hamming weight of a signed binary representation (non-adjacent form). Use dynamic programming on the binary digits, considering carries, to compute the minimum operations in O(log n) time.

Pro tip: Emphasize that the greedy approach of always subtracting the largest power of two fails; instead, use DP to handle carries and achieve optimality. Mention that this is a classic problem solvable with digit DP and that the answer is the minimal Hamming weight of a signed binary representation.

1. Understand the problem

Restate the problem: each operation adds or subtracts a power of two, and we want the minimum number of operations to reach zero. Recognize that this is equivalent to representing n as a sum of signed powers of two with minimum terms.

2. Relate to binary representation

Observe that the standard binary representation uses only positive powers, but allowing negative powers can reduce the number of terms. This leads to the concept of signed binary representation, such as non-adjacent form (NAF).

3. Design a DP solution

Process the binary digits from least significant to most significant. At each bit, decide whether to add or subtract a power of two, and keep track of the carry. Use DP states: index and carry, minimizing operations.

4. Implement and optimize

Write the DP recurrence: dp[i][carry] = min operations to process bits up to i. Transition by considering the current bit plus carry, and either using a power of two (increment count) or not. Handle the final carry. The time complexity is O(log n).

5. Test with examples

Verify with small values: n=1 (1 op), n=3 (2 ops: 4-1), n=7 (2 ops: 8-1), n=15 (2 ops: 16-1). Also test large values near 2^60 to ensure the algorithm handles big integers.

Key Points to Mention

The problem is equivalent to finding the minimum Hamming weight of a signed binary representation.
Greedy subtraction of the largest power of two is not always optimal (e.g., n=15: greedy gives 4 ops, optimal is 2).
Dynamic programming with carry handles the trade-off between using a power now or propagating a carry.
The non-adjacent form (NAF) gives a minimal weight representation, but DP is more straightforward to implement.
Time complexity is O(log n) and space O(log n) or O(1) with optimization.
Edge cases: n=0 (0 ops), n=1 (1 op), and numbers like 2^k - 1 (2 ops).

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