Let’s discuss a few applications.

h2. a + b + c = d

h2. a + b + c + d + e = f

bq. Given an array of integers, find out if there are any four numbers such that the sum of the first five equal to the 6th (you can use the same number more than once).

bq. Given an array, find out if there are any 6 numbers such that the sum of the first five equal to the 6th (you can use the same number more than once).

The naive algorithm is $O(N^4^)$ try all the possible combinations of 6 numbers. A less naive algorithm brute forces through all $n^3$ combinations of 5 numbers and then efficiently checks if their sum is in the original array by using a hash table.
But by now you’ve probably started thinking how meet in the middle can be applied for this problem. The trick is to rewrite the equation as a + b = d - c. Store all the n^3 sums a + b + c in a hash set S. Then iterate through all n^3 combinations for d, e, f and check if S contains f - d - e. This algorithm has O(n^3) time and space complexity.

The naive algorithm is O(N^6) try all the possible combinations of 6 numbers. A less naive algorithm brute forces through all n^5 combinations of 5 numbers and then efficiently checks if their sum is in the original array by using a hash table.
But by now you’ve probably started thinking how meet in the middle can be applied for this problem. The trick is to rewrite the equation as a + b + c = f - d - e. Store all the n^3 sums a + b + c in a hash set S. Then iterate through all n^3 combinations for d, e, f and check if S contains f - d - e. This algorithm has O(n^3) time and space complexity.

h2. Bidirectional search(interview question)

One neat idea is instead of starting the search from one node, start from both and see when the two search spaces meet. If the distance between two nodes is k and the average branching factor in the network is p then we explore O(p^(k/2)) nodes instead of O(p^k) nodes.

h2. Friend of a friend(inteview question)

h2. Friend of a friend problem (inteview question)

bq. Given two user names in a social network find an easy way to test if they one is a friend of a friend of the other.
A trivial solution is to find first the list of friends for the first user and then the lists of friends for each of his friends. Assuming the network has an average degree of k, this approach does k + 1 requests.

A somewhat faster solution precomputes for each user a list of friend of friends. The number of requests is 1 now but space used is O(nk^2) and the size of a reply is O(k^2).
 
A solution that uses the meet in the middle approach has a pretty good balance between memory resources and query execution. We issue two queries, one for the friends of the first user and one for the friends of the second user. Then we intersect the two sets. Now we use just 2 requests, the graph takes O(nk) space, and the reply sizes are O(k).

A somewhat faster solution is to do some preprocessing and store for each user a hash set of its friends of friends. The number of requests is 1 now but space used is O(nk^2) and the size of a reply is O(k^2).
A better solution uses the meet in the middle approach: we issue two queries, one for the friends of the first user and one for the friends of the second user. Then we intersect the two sets. Now we use just 2 requests, the graph takes O(nk) space, and the reply sizes are O(k).

h2. Meet in the middle attack (not to be confused with man in the middle attack)