Let’s discuss a few applications.

h2. Bidirectional search

h2. Bidirectional search(interview question)

bq. Find the shortest path between two nodes nodes in a large graph which you can’t keep in memory, for example the web graph of the facebook friendship graph, find out the shortest path between them.

h2. Friend of a friend problem (inteview question)

q. 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.

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 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).

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

q. 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).

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^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. the discrete logarithm problem

q. Given n a prime number and p, q two integer numbers between 0 and n-1 find k such that  p^k = q modulo n.

bq. Given n a prime number and p, q two integer numbers between 0 and n-1 find k such that  p^k = q modulo n.

The baby step, giant step uses the meet in the middle principle.
We can write k = i ([sqrt(n)] + 1) + j.
Notice that i <= sqrt(n) and j <= sqrt(n).

h2. Minimal vertex cover

q. 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.

bq. 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.

As before we split the nodes in half. We’ll brute force the set of vertices that are in the first half of the nodes and in a minimum vertex cover. For edges (f, s) where node f is in the first half but not in our picked set and s in the second half we have to use s to cover the edge. Now we’re left with edges that have both end nodes in the second half. We compute the minimum edge cover for each induced subgraph. O(3^n).