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.

It still amazes me how much people cry that these questions are not relevant and should not be asked in an interview. We’re ultimately only hurting ourselves as Software Engineers in preferring easy interviews, where only predictable questions are asked.

Some places will have hard interviews and that may be a sign that if you join that place, you may jsut end up learning something, improving, getting better.

### Like this:

Like Loading...

*Related*