Posted on April 15, 2014

Shit just got real

Given an array with n numbers and a number s, find whether there are 2 numbers on the array whose sum is equal to s.

First brute-force O(n^2), then linear O(n).

Then adapt it for sums of 3 numbers O(n^2).

Then for 4 numbers O(n^3), and then reduce it to O(n^2).

Then generalize it for x numbers O(n^{x/2}).

Taken from Oxford Knight’s interview preparation page.

You would be surprised about how much people cry that these questions are not relevant and should not be asked in an interview.