Uber NG OA Real Questions Review: Min Operations + Good Subarray Complete Analysis

Overview

Uber New Grad OA contains two algorithm questions testing comprehensive application of bit manipulation and sliding window. This article provides complete solution approaches, code implementations, and optimization techniques.

---

Question 1: Minimum Operations to Zero

Problem Description

Given a positive integer n, you can perform one of the following operations in a single step:

• Add a power of 2 (2^i)
• Subtract a power of 2 (2^i)

Find the minimum number of operations required to reduce n to 0.

Example:

Input: n = 5
Output: 2

Explanation:
5 → 5 - 2^0 = 4 → 4 - 2^2 = 0
Or: 5 → 5 - 1 = 4 → 4 - 4 = 0

Example 2:

Input: n = 21
Output: 3

Explanation:
21 in binary: 10101
Requires 3 operations

Constraints:

• 1 ≤ n < 2^60

---

Solution Approach

Key Observation

The key to this problem is binary representation:

• Every positive integer can be represented in binary
• Adding/subtracting powers of 2 = changing bit values
• Goal is to turn all bits to 0 with minimum operations

Method 1: Greedy + Bit Manipulation ⭐ Optimal

Core Idea:

1. Count the number of consecutive 1-bit segments
2. Consecutive 1s can be merged through one "carry" operation
3. Example: 111 (7) = 1000 (8) - 1, only needs 2 operations

Algorithm Steps:

10101 (21)
↓
Segments of consecutive 1s: [1], [1, 1] 
Segments = 2 isolated 1s + 1 consecutive segment = 3

Optimization Trick:

• Consecutive 1s: can be optimized with "addition carry"
• Isolated 1s: directly subtract

Code Implementation

def getMinOperations(n):
    """
    Calculate minimum operations to reduce n to zero
    
    Approach: Count segments of 1s in binary
    - Consecutive 1s count as one segment
    - Each segment needs 1-2 operations
    """
    if n == 0:
        return 0
    
    operations = 0
    prev_bit = 0
    
    while n > 0:
        current_bit = n & 1  # Get lowest bit
        
        # If current bit is 1 and previous bit is 0 (new segment starts)
        if current_bit == 1 and prev_bit == 0:
            operations += 1
        
        prev_bit = current_bit
        n >>= 1  # Right shift by 1
    
    return operations

# Test cases
print(getMinOperations(5))   # Output: 2
print(getMinOperations(21))  # Output: 3
print(getMinOperations(15))  # Output: 1 (1111 -> 10000 - 1)

Time Complexity: O(log n) - traverse binary bits
Space Complexity: O(1)

---

Method 2: Brian Kernighan Algorithm

def getMinOperations_v2(n):
    """
    Using Brian Kernighan algorithm
    Each iteration removes the rightmost 1
    """
    operations = 0
    
    while n:
        # Check if there are consecutive 1s
        if n & (n >> 1):
            # Has consecutive 1s, carry
            n += (n & -(n & (n >> 1)))
        else:
            # No consecutive 1s, directly subtract
            n &= n - 1
        operations += 1
    
    return operations

---

Common Pitfalls

❌ Mistake 1: Directly count number of 1s

# Wrong example
def wrong_solution(n):
    return bin(n).count('1')  # For 111 returns 3, actually needs 2

❌ Mistake 2: Not considering consecutive 1s optimization

# 15 = 1111, direct count is 4, but actually needs only 1 (16 - 1)

✅ Correct Approach: Count segments of consecutive 1s, not number of 1s

---

Question 2: Minimum Length Good Subarray

Problem Description

Given an array of n positive integers arr[n] and an integer k, a subarray is considered good if it contains at least k distinct integers.

Find the minimum length of a good subarray. If no such subarray exists, return -1.

Example:

Input: arr = [2, 2, 1, 1, 3], k = 3
Output: 4

Explanation:
Subarrays with at least 3 distinct integers:
- [2, 2, 1, 1, 3] (length 5)
- [2, 1, 1, 3] (length 4) ✓ shortest

Constraints:

• 1 ≤ n ≤ 10^6
• 1 ≤ arr[i] ≤ 10^6
• 1 ≤ k ≤ n

---

Solution Approach

Core Idea: Sliding Window

This is a classic sliding window problem:

1. Maintain a window tracking distinct integers count
2. When window has ≥ k distinct integers, try to shrink window
3. Record minimum window length that satisfies condition

Algorithm Steps

arr = [2, 2, 1, 1, 3], k = 3

Step 1: [2] - 1 distinct integer
Step 2: [2, 2] - 1 distinct integer
Step 3: [2, 2, 1] - 2 distinct integers
Step 4: [2, 2, 1, 1] - 2 distinct integers
Step 5: [2, 2, 1, 1, 3] - 3 distinct integers ✓

Now try to shrink window:
Step 6: [2, 1, 1, 3] - 3 distinct integers ✓ (length 4)
Step 7: [1, 1, 3] - 2 distinct integers ✗

Answer: 4

---

Code Implementation

def findMinimumLengthSubarray(arr, k):
    """
    Use sliding window to find shortest subarray with at least k distinct integers
    
    Time Complexity: O(n)
    Space Complexity: O(k)
    """
    from collections import defaultdict
    
    n = len(arr)
    if k > n:
        return -1
    
    # Count of each number in window
    window = defaultdict(int)
    left = 0
    min_length = float('inf')
    
    for right in range(n):
        # Expand window
        window[arr[right]] += 1
        
        # When window has >= k distinct integers, try to shrink
        while len(window) >= k:
            min_length = min(min_length, right - left + 1)
            
            # Shrink window
            window[arr[left]] -= 1
            if window[arr[left]] == 0:
                del window[arr[left]]
            left += 1
    
    return min_length if min_length != float('inf') else -1

# Test cases
print(findMinimumLengthSubarray([2, 2, 1, 1, 3], 3))  # Output: 4
print(findMinimumLengthSubarray([1, 2, 3, 4], 2))     # Output: 2
print(findMinimumLengthSubarray([1, 1, 1, 1], 2))     # Output: -1

---

Optimized Version: More Concise Implementation

def findMinimumLengthSubarray_v2(arr, k):
    """
    Optimized version: using Counter
    """
    from collections import Counter
    
    if k > len(set(arr)):
        return -1
    
    window = Counter()
    left = 0
    min_length = float('inf')
    
    for right, num in enumerate(arr):
        window[num] += 1
        
        while len(window) >= k:
            min_length = min(min_length, right - left + 1)
            window[arr[left]] -= 1
            if window[arr[left]] == 0:
                del window[arr[left]]
            left += 1
    
    return min_length if min_length != float('inf') else -1

Time Complexity: O(n) - each element visited at most twice
Space Complexity: O(k) - hash table stores at most k distinct elements

---

Common Pitfalls

❌ Mistake 1: Using brute force O(n²)

# Timeout!
def brute_force(arr, k):
    min_len = float('inf')
    for i in range(len(arr)):
        for j in range(i, len(arr)):
            if len(set(arr[i:j+1])) >= k:
                min_len = min(min_len, j - i + 1)
    return min_len if min_len != float('inf') else -1

❌ Mistake 2: Not properly maintaining window

# Forgetting to delete elements with count 0
window[arr[left]] -= 1
# Should add:
if window[arr[left]] == 0:
    del window[arr[left]]

✅ Correct Approach: Use sliding window + hash table, O(n) time complexity

---

On-Site Strategy

Time Allocation Suggestion

Question	Difficulty	Suggested Time	Priority
Question 1	Medium	20-25 minutes	⭐⭐⭐
Question 2	Medium	25-30 minutes	⭐⭐⭐⭐

Total Time: 45-55 minutes (leave 5-10 minutes for review)

---

Debugging Tips

Question 1 Debugging:

def debug_operations(n):
    """Print each operation step"""
    print(f"n = {n}, binary = {bin(n)}")
    operations = 0
    prev_bit = 0
    
    while n > 0:
        current_bit = n & 1
        if current_bit == 1 and prev_bit == 0:
            operations += 1
            print(f"New segment found at position, operations = {operations}")
        prev_bit = current_bit
        n >>= 1
    
    return operations

Question 2 Debugging:

def debug_window(arr, k):
    """Print window state"""
    from collections import defaultdict
    
    window = defaultdict(int)
    left = 0
    
    for right in range(len(arr)):
        window[arr[right]] += 1
        print(f"Window [{left}:{right+1}]: {dict(window)}, distinct = {len(window)}")
        
        while len(window) >= k:
            print(f"  → Found valid window, length = {right - left + 1}")
            window[arr[left]] -= 1
            if window[arr[left]] == 0:
                del window[arr[left]]
            left += 1

---

Knowledge Points Summary

Question 1 Topics

• ✅ Bit manipulation basics
• ✅ Binary representation
• ✅ Greedy algorithm
• ✅ Mathematical optimization

Question 2 Topics

• ✅ Sliding window
• ✅ Hash table application
• ✅ Two pointers technique
• ✅ Time complexity optimization

---

Related Problems

Question 1 Related

• LeetCode 191: Number of 1 Bits
• LeetCode 338: Counting Bits
• LeetCode 201: Bitwise AND of Numbers Range

Question 2 Related

• LeetCode 340: Longest Substring with At Most K Distinct Characters
• LeetCode 904: Fruit Into Baskets
• LeetCode 3: Longest Substring Without Repeating Characters

---

🚀 Need OA/VO Assistance?

oavoservice provides professional interview assistance services:

✅ Real-time Code Support - Full OA/VO assistance
✅ Real Question Bank - 1000+ latest questions
✅ Mock Interviews - 1-on-1 simulation training
✅ Resume Optimization - Improve interview pass rate

👉 Add WeChat Now: Coding0201
👉 Visit Website: oavoservice.com

---

Last Updated: 2026-03-15
Difficulty Rating: ⭐⭐⭐ Medium
Pass Rate: ~65%
Company: Uber New Grad OA