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.
 

h2. Bidirectional search
bq. Find the shortest path between two nodes nodes in a large graph which you can’t keep in memory, for example the Facebook friendship graph.

h2. Additional problems
# *Friend of a friend*(interview question) Given two user names in a social network design an efficient way to test if one is a friend of a friend of the other.

# *6 degrees of separation* Given two user names in a social network design an efficient way to test if they are at most 6 friends apart.

# *Equal partition* Given a set A of 40 real numbers, find out if there is any way to split A in two sets such that the sums of their elements are equal. (Hint: complexity $O(2^n/2^)$)
# *Minimal vertex cover* Given a graph of n nodes (n <= 30), find out a set with the smallest number of vertices such that each edge in the  graph has at least one node inside the set. (Hint: complexity $O(3^n/2^)$)
# *Square fence* You're given an array L which represents the lengths of n planks. You have to answer if there's any way to form the edges of a square fence using all the planks without breaking or overlapping them.  (Hint: complexity $O(4^n/2^)$)