Uber·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Apr 2026

Summary

Uber SWE coding round with a task assignment optimization problem. Pretty clean problem once you see the greedy insight, but it's the kind of thing that looks harder than it is under pressure.

Questions Asked (1)

You have n tasks, each with a different reward depending on whether person 1 or person 2 does it. Person 1 must be assigned exactly k tasks, person 2 gets the rest. How do you maximize the total reward?

Algorithms & Data Structures

Author's notes

I stared at this for a bit and started thinking about sorting by reward1 descending, which was wrong.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by computing the difference (reward1 - reward2) for each task. Sort tasks by this difference in descending order and assign the top k tasks to person 1, the rest to person 2. This greedy approach maximizes total reward because it selects tasks where person 1 has the greatest relative advantage.

Pro tip: Mention that this is equivalent to minimizing the opportunity cost of assigning person 1 instead of person 2, and that the greedy choice is optimal due to the matroid structure of the problem.

1. Understand the problem

Clarify that we need to assign exactly k tasks to person 1 and n-k to person 2 to maximize total reward. Each task has two possible rewards depending on assignee.

2. Compute differences

For each task i, calculate d_i = reward1_i - reward2_i. This represents the gain (or loss) from assigning task i to person 1 instead of person 2.

3. Sort by difference

Sort tasks in descending order of d_i. Tasks with higher d_i are more beneficial to assign to person 1.

4. Assign top k to person 1

Select the first k tasks from the sorted list and assign them to person 1. Assign the remaining tasks to person 2.

5. Compute total reward

Sum the rewards: for tasks assigned to person 1, add reward1_i; for others, add reward2_i. This yields the maximum total reward.

Key Points to Mention

Greedy algorithm: sorting by difference and picking top k is optimal.
Proof of optimality: exchange argument or matroid theory.
Time complexity: O(n log n) due to sorting.
Space complexity: O(n) for storing differences or O(1) extra if sorting in place.
Edge cases: k=0 or k=n, negative differences.
Alternative perspective: minimizing opportunity cost.

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