Google·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Jun 2026

Summary

Google SWE interview with a pretty gnarly low-level math problem and a follow-up LC problem. The coding round pushed into bit manipulation territory which I wasn't expecting from what looked like a simple multiplication question.

Questions Asked (2)

Implement a product(int a, int b) function that returns a * b using only the operators +, ++, --, %, and >>. Write both a recursive and an iterative version, handle negatives and zero, and discuss the time complexity.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

The basic iterative version came to me fast, just add a to itself b times.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying that multiplication is repeated addition, then handle signs by converting to positive operands and adjusting the result. Implement both iterative and recursive versions using only the allowed operators, and analyze time complexity as O(|b|) or O(min(|a|,|b|)) if optimized.

Pro tip: Optimize by iterating over the smaller absolute value to reduce time, and mention that recursion depth can be O(|b|) which may cause stack overflow for large inputs, so iterative is preferred in practice.

1. Clarify requirements and edge cases

Confirm that only +, ++, --, %, and >> are allowed, and discuss handling of zero, negative numbers, and potential overflow.

2. Design sign handling

Determine the sign of the result by checking if exactly one operand is negative, then work with absolute values to simplify the core logic.

3. Implement iterative version

Use a loop to add the multiplicand repeatedly, decrementing the multiplier until it reaches zero, and apply the sign at the end.

4. Implement recursive version

Define a recursive function that adds the multiplicand and calls itself with the multiplier decremented by one, with a base case when the multiplier is zero.

5. Analyze time complexity and trade-offs

State that both versions run in O(|b|) time, and discuss how choosing the smaller operand as the multiplier can reduce iterations, plus recursion depth concerns.

Key Points to Mention

Multiplication as repeated addition
Handling negative numbers by converting to positive and adjusting sign
Zero case: return 0 immediately
Time complexity O(|b|) and optimization by iterating over smaller absolute value
Recursion depth and stack overflow risk for large inputs
Use of only allowed operators: +, ++, --, %, >> (e.g., using >> for division by 2 if needed)

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

Follow-up: given a positive integer n, find the minimum number of operations to reduce it to 1, where each operation is either divide by 2 (if even), or add 1 or subtract 1 (if odd).

Algorithms & Data Structures

Author's notes

This is a known problem and I'd seen it before, which helped.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying the problem and edge cases, then propose a greedy strategy with a tie-breaking rule for odd numbers (prefer n-1 when n ≡ 3 mod 4 and n > 3, otherwise n+1). Explain why greedy works by analyzing the binary representation, and mention that BFS or DP can serve as fallback solutions with higher complexity.

Pro tip: Demonstrate deep understanding by connecting the greedy choice to binary patterns: adding 1 to a number ending in '11' creates trailing zeros, enabling more divisions by 2. Also, note that for n=3, subtracting 1 is optimal despite the mod 4 rule.

1. Clarify and define

Restate the problem, confirm operations and constraints, and handle edge cases like n=1, n=2, n=3.

2. Explore naive approaches

Discuss BFS or DP solutions to establish a baseline, noting their O(n) time and space complexity.

3. Derive greedy strategy

Propose a greedy algorithm: if even, divide by 2; if odd, choose +1 or -1 based on n mod 4 (with special case n=3).

4. Prove correctness

Argue why greedy is optimal by analyzing binary representation and the effect of operations on trailing zeros.

5. Analyze complexity

State that the greedy approach runs in O(log n) time and O(1) space, and discuss potential pitfalls.

Key Points to Mention

Greedy choice: divide by 2 when even; for odd n, prefer n-1 if n ≡ 3 mod 4 and n > 3, else n+1.
Special case: n=3 requires subtracting 1 (not adding 1) to reach 1 in 2 steps.
Binary representation: adding 1 to a number ending in '11' creates trailing zeros, reducing future operations.
Proof of optimality: each operation should maximize the number of trailing zeros in the binary representation.
Complexity: O(log n) time and O(1) space for the greedy solution.
Alternative approaches: BFS/DP for verification, but they are less efficient.

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