Determine If Two Numbers Sum to Target
Company: LendingClub
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
##### Scenario
Live CodeShare Python/Java question during the same LendingClub interview assessing basic algorithmic fluency.
##### Question
Given an integer array nums and an integer target, return true if any two distinct numbers in nums sum to target; otherwise return false.
##### Hints
An O(n) hash-set solution is acceptable; explain trade-offs vs. sorting.
Overview: This question evaluates a candidate's basic algorithmic fluency in array processing and the ability to reason about pairwise sums using auxiliary data structures.
Given an integer array `nums` and an integer `target`, return `true` if any two distinct elements (at different indices) in `nums` sum to `target`; otherwise return `false`.
Note: the two elements must be at different positions, but they may have equal values (e.g. `nums = [3, 3]`, `target = 6` returns `true`).
**Example 1:**
```
Input: nums = [2, 7, 11, 15], target = 9
Output: true (2 + 7 = 9)
```
**Example 2:**
```
Input: nums = [1, 2, 3], target = 7
Output: false (no pair sums to 7)
```
**Example 3:**
```
Input: nums = [3, 3], target = 6
Output: true (the two 3s are at different indices)
```
An O(n) single-pass hash-set solution is expected; be ready to discuss the trade-off versus sorting then two-pointer (O(n log n) time, O(1) extra space if sorting in place).
Constraints
- 0 <= nums.length <= 10^5
- -10^9 <= nums[i] <= 10^9
- -2 * 10^9 <= target <= 2 * 10^9
- The two chosen elements must be at different indices (but may have equal values).
Examples
Input: ([2, 7, 11, 15], 9)
Expected Output: True
Explanation: 2 + 7 = 9, so a valid pair exists.
Input: ([3, 2, 4], 6)
Expected Output: True
Explanation: 2 + 4 = 6; note 3 + 3 is not valid because there is only one 3.
Hints
- Brute force checks every pair in O(n^2). Can you avoid re-scanning the array for each element?
- As you iterate, for the current value x the partner you need is target - x. If you have already seen that partner, you have a valid pair.
- Use a hash set of values seen so far. Check membership BEFORE inserting the current value so you never pair an element with itself.
- Alternative: sort the array (O(n log n)) and use two pointers from both ends, moving inward based on the running sum — trades time for O(1) extra space.