Uber SDE-1/2/SDE-Intern OA Questions | Kumar K | February 2026 |Set 35

Question

Uber | SDE-2 | OA | 2026

 

Question 1: Purchase Optimization

Alex is shopping at Ozone Galleria Mall, where each cubicle sells products at a fixed price. The cubicles are arranged so that prices are in non-decreasing order from left to right.

There is an array of n integers, prices, where prices[i] is the price at the ith cubicle, and q queries to process. For each query, you are given:

• pos: Alex's initial position (1-indexed)
• amount: the amount of money Alex has

Alex visits each cubicle from position pos to n and can purchase a maximum of one product from each cubicle visited. The goal is to determine the maximum number of products Alex can buy without exceeding the available amount.

Example:

• Input: n=5, prices = [3, 4, 5, 5, 7], q=3, pos = [2, 1, 5], amount = [10, 24, 5]
• Output: [2, 5, 0]
• Explanation:
  • Query 1 (pos = 2, amount = 10): Alex visits cubicles 2 through 5. Prices available are [4, 5, 5, 7]. Alex can buy from cubicle 2 and 3: 4+5=9≤10. The answer is 2.
  • Query 2 (pos = 1, amount = 24): Alex visits all cubicles. Total cost is 3+4+5+5+7=24≤24. The answer is 5.
  • Query 3 (pos = 5, amount = 5): Alex visits cubicle 5. Price is 7, which exceeds the available amount (5). The answer is 0.

Constraints:

• 1≤n≤5⋅105
• 1≤q≤2⋅105
• 1≤prices[i]≤106
• prices[i]≤prices[i+1]
• 1≤pos[i]≤n
• 0≤amount[i]≤1012

Approach: Since the prices array is already sorted in non-decreasing order, the optimal greedy strategy is to simply buy the cheapest available items starting from pos. You can compute a Prefix Sum array of the prices in O(N). For each query, since prefix sums are monotonically increasing, you can use Binary Search (std::upper_bound in C++) to find the maximum number of items Alex can afford in O(logN) time per query. Total time: O(N+QlogN).