bq. Given A, an array of integers, find out if there are any four numbers in the array that sum up to zero (the same element can be used multiple times). For example given A = [2, 3, 1, 0, -4, -1] a solution is 3 + 1 + 0 - 4 = 0 or 0 + 0 + 0 + 0 = 0.

4sum is one of the most popular programming interview questions.
 

The naive algorithm checks all four number combinations. This solution takes $O(N^4^)$ time.
A slightly improved algorithm brute forces through all $n^3^$ three number combinations and efficiently checks if -(a + b + c) is in the original array using a hash table. This algorithm has $O(n^3^)$ complexity.

  print "No solution."
==

This algorithm has $O(n^2^)$ time and space complexity.
 
Sidenotes: 4sum is one of the most popular programming interview questions. There's no known faster algorithm for this problem.

This algorithm has $O(n^2^)$ time and space complexity. There's no known faster algorithm for this problem.

h2. Bidirectional search