← Uber Interview Insights

Uber·Machine Learning Engineer·Technical Phone Screen·Intermediate

Intermediate
Jul 2026

Summary

Uber MLE interview with a dynamic programming problem on counting ways to reach a target score. Pretty standard bounded knapsack territory but still worth thinking through carefully before diving into code.

Questions Asked (1)

Q1

Given a list of question types where each type has a fixed number of available questions and a fixed point value per question, count the number of distinct ways to score exactly a target number of points. Return the result modulo 10^9 + 7.

Algorithms & Data Structures
Author's notes

This is basically a bounded knapsack / DP counting problem.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the problem as a bounded knapsack where each question type is an item with a fixed count and weight equal to its point value; use dynamic programming to count the number of ways to reach the target sum, applying modulo 10^9+7. Optimize by decomposing each bounded item into 0/1 items via binary splitting or using a monotonic queue for O(target) per type.

Pro tip: Clarify that the order of selecting questions does not matter (combinations, not permutations) and that each type can be used up to its available count; this avoids common off-by-one and overcounting errors.

1. Clarify problem constraints and assumptions

Confirm that we count distinct combinations (order irrelevant) and that each question type can be used at most its available count. Ask about input size to choose the right DP optimization.

2. Define DP state and recurrence

Let dp[s] = number of ways to score exactly s points. For each question type with point value v and count c, update dp using a bounded knapsack transition: dp_new[s] = sum_{k=0..c} dp_old[s - k*v].

3. Optimize bounded transitions

If target and counts are large, use binary splitting to convert each bounded item into O(log c) 0/1 items, or use a monotonic queue to achieve O(target) per type. Apply modulo 10^9+7 at each addition.

4. Implement and test with edge cases

Code the DP iteratively, handling base case dp[0]=1. Test with small examples, zero target, zero counts, and large values to ensure modulo correctness and no overflow.

5. Analyze complexity and discuss trade-offs

State time and space complexity: O(n * target) with binary splitting or O(n * target) with monotonic queue, where n is number of types. Mention space can be O(target).

Key Points to Mention

  • Dynamic programming with state dp[score] = number of ways
  • Bounded knapsack: each item has a limited count
  • Modulo arithmetic to prevent overflow and meet requirement
  • Binary splitting or monotonic queue for optimization
  • Time complexity O(n * target) and space O(target)
  • Edge cases: target=0, zero counts, large target

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