Software Engineer · Phone Screen · Coding

Uber — Software Engineer ✅ Passed

Level: Senior-Level

Round: Phone Screen · Type: Coding · Difficulty: 6/10 · Duration: 60 min · Interviewer: Unfriendly

Topics: Dynamic Programming

Location: San Francisco, CA

Interview date: 2026-01-15

Summary

Round 1: Phone Screen

Question: I was asked to determine if a subset of distinct positive integers from a given array sums up to a specified target value. Each element can be used at most once, and the order doesn't matter. The interviewer was looking for a dynamic programming solution.

Details

Problem Description

You are given an array of distinct positive integers called nums, along with a positive integer target.

Determine whether it is possible to select some elements from nums (each element can be used at most once) such that the sum of the selected elements is exactly equal to target.

---

Requirements

• Each number in nums may either be chosen or skipped
• No element can be used more than once
• The order of elements does not matter

Return:

• true if there exists at least one subset whose sum equals target
• false otherwise

---

Constraints

• 1 ≤ nums.length ≤ 1000
• 1 ≤ nums[i] ≤ 1000
• 1 ≤ target ≤ 1000
• All values in nums are unique

---

Examples

Example 1

Input

nums = [2, 5, 3, 11] target = 10

Output

true

Explanation Selecting the subset {2, 5, 3} results in a total sum of 10.

---

Example 2

Input

nums = [3, 9, 4] target = 8

Output

false

Explanation No combination of numbers from the array can sum up to 8.

---

Example 3

Input

nums = [1, 2, 3, 7] target = 6

Output

true

Explanation The subset {1, 2, 3} produces the required sum.

---

What Interviewers Typically Look For

• Understanding of classic subset sum / knapsack-style DP
• Ability to optimize space (1D vs 2D DP)
• Handling constraints efficiently
• Correct interpretation of “use each element at most once”

---

Proposed Solution

`python from typing import List, Optional

class Solution: def subsetSum(self, nums: List[int], target: int) -> bool: dpArray = [False] * (target + 1) dpArray[0] = True

    for currentNum in nums:
        # Iterate backwards to use each number at most once
        for currentSum in range(target, currentNum - 1, -1):
            dpArray[currentSum] = dpArray[currentSum] or dpArray[currentSum - currentNum]
    
    return dpArray[target]

`