Two-Sum Variation | Dataford Interview Questions

An eBay checkout flow needs to identify two listings whose prices exactly match a customer’s budget. Given an array of integer listing prices and a target budget, return the lexicographically smallest pair of distinct indices whose prices sum to the target.

A pair [i, j] must satisfy i < j and prices[i] + prices[j] == budget. Pair [a, b] is lexicographically smaller than [c, d] when a < c, or when a == c and b < d. Return [-1, -1] if no valid pair exists.

Formal Specification

Implement find_listing_pair(prices, budget).

Input: prices, a list of integers, and budget, an integer.
Output: a two-element list containing the selected indices, or [-1, -1] when no pair exists.
The same listing cannot be used twice.

Constraints

2 <= len(prices) <= 100,000
-10^9 <= prices[i] <= 10^9
-10^9 <= budget <= 10^9
Prices may contain duplicates
Multiple valid pairs may exist

Function Signature

def find_listing_pair(prices, budget):

Your question is Two-Sum Variation. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem