The Power of Two
Given an integer $n$, return true if it is a power of two. Solve using a single Bit Manipulation operation ($O(1)$).
Why Interviewers Ask This
Interviewers at Uber ask this to evaluate a candidate's ability to optimize for performance and memory efficiency. They specifically test knowledge of binary representation, as Bit Manipulation is critical in high-throughput systems like ride-matching algorithms where O(1) operations reduce latency significantly.
How to Answer This Question
1. Clarify constraints immediately: Confirm if n can be negative or zero, noting that powers of two must be positive integers. 2. Propose the brute force solution first to show baseline understanding, then pivot to the optimal approach. 3. Explain the bit pattern: Powers of two have exactly one bit set (e.g., 8 is 1000). Subtracting 1 flips all bits after that single bit (7 becomes 0111). 4. Derive the logic: The bitwise AND of n and n-1 will always be zero for powers of two because they share no set bits. 5. Validate edge cases: Explicitly mention that n=0 fails this check since 0 & -1 equals 0, requiring an additional 'n > 0' condition. This demonstrates rigorous thinking aligned with Uber's focus on robust engineering.
Key Points to Cover
- Recognizing that powers of two have exactly one bit set in binary
- Deriving the n & (n-1) == 0 property through logical deduction
- Handling the specific edge case where n equals zero
- Ensuring the solution meets the strict O(1) time complexity requirement
- Connecting the algorithmic optimization to real-world system performance needs
Sample Answer
To solve this efficiently in O(1) time without loops, I'd leverage the unique properties of binary numbers. First, we must handle the edge case where n is less than or equal to zero, as powers of two are strictly positiv…
Common Mistakes to Avoid
- Forgetting to check if n is greater than zero, leading to false positives for n=0
- Using a loop to divide by two repeatedly, which results in O(log n) instead of O(1)
- Attempting to use logarithms with floating-point arithmetic, risking precision errors
- Failing to explain the binary logic behind the bit manipulation trick during the interview
Sound confident on this question in 5 minutes
Answer once and get a 30-second AI critique of your structure, content, and delivery. First attempt is free — no signup needed.