Software Engineer · Online Assessment · Coding

Uber — Software Engineer ✅ Passed

Level: Junior-Level

Round: Online Assessment · Type: Coding · Difficulty: 7/10 · Duration: 60 min · Interviewer: Unfriendly

Topics: Greedy Algorithms, Bit Manipulation, Sliding Window, Hash Table, Monotonic Stack

Location: San Francisco, CA

Interview date: 2026-01-21

Summary

I completed an online assessment with three coding questions on HackerRank.

Question 1: Minimize operations to reduce n to 0 using powers of 2.

Question 2: Find the shortest subarray containing at least k distinct integers.

Question 3: Calculate the final price with discounts based on the first smaller price to the right.

Details

The online assessment consisted of three questions on HackerRank. The questions involved a full-screen mode but did not require a camera.

Question 1:

Minimize operations to convert a positive integer n to 0. In each operation, you can either add or subtract 2^i (where i >= 0).

The optimal strategy is a greedy approach using the signed binary representation (Non-Adjacent Form - NAF). Steps:

1. If n is even: Divide n by 2.
2. If n is odd:
   • If n % 4 == 1: Subtract 1 from n.
   • If n % 4 == 3: Add 1 to n.

Special cases: n == 1, directly subtract 1; n == 3, subtracting 1 is more intuitive.

Question 2:

Given an array arr and an integer k, find the length of the shortest subarray that contains at least k distinct integers. Return -1 if no such subarray exists.

I used a sliding window/two-pointer technique with a counting hash table. Steps:

1. Maintain a window using left and right pointers.
2. Use a dictionary dict to record the frequency of each value within the window, and use len(dict) to represent the number of distinct elements.
3. Expand right pointer to the right, adding arr[right] into count.
4. When len(dict) >= k, attempt to contract the left pointer:
   • Update the result res = min(res, right - left + 1)
   • Decrement the count, removing any value with a count of 0 from the dictionary.
   • Increment left by 1

Question 3:

For each index i in prices, the discount is the price at the first index j > i such that prices[j] <= prices[i]. If no such j exists, there is no discount and the original price is used.

Output:

1. The sum of the final prices.
2. The indices (0-based, ascending order, space-separated) where the original price was used.

I used a monotonic stack (find the first element to the right that is <= the current element).

Iterate from right to left, maintaining a stack of indices representing candidate discounts in non-decreasing price order. When processing index i:

1. While the stack is not empty and prices[stack[-1]] > prices[i], pop the stack (as these prices cannot be valid discounts).
2. If the stack is empty, record index i as having no discount, and add prices[i] to the total price.
3. Otherwise, the discount is prices[stack[-1]], and add prices[i] - prices[stack[-1]] to the total price.
4. Push index i onto the stack.

Reverse the list of indices without discounts to produce ascending order.