Coding & Algorithms · Interview Question
Find for each array element whether its complement (target - x) exists. Naive is O(n²). Get it to O(n)?
How to answer
One pass with a hash set/map: for each x, check if (target - x) is stored in O(1) average; else insert x. Total O(n) average time, O(n) space. The pattern is trading memory for time by replacing an inner scan with a constant-time lookup.
Key idea: Quoting O(1) hash lookups as worst-case — they're O(1) AVERAGE; adversarial keys degrade to O(n) per lookup.
More: Quant interview prep · Quant salary
Related Coding & Algorithms questions
- A fair six-sided die pays you its face value in dollars. What is the risk-neutral fair price to play this game once, and why?
- Draw a uniformly random element from a stream of unknown length in O(1) memory. How does reservoir sampling work?
- Expected and worst-case time complexity of quicksort, and why does the expected case dominate in practice?
- Given a sorted array, how do you find a target in O(log n), and what are the two most common bugs?