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 Facebook friendship graph.

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.

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.

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. Caveats
Unlike divide and conquer the trick in meet in the middle can't be applied recursively because the sub problems don't have the same structure as the original problem.

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

# 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^)$)

# 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: You're given an array L which represents the sizes of n planks. You have to answer if there's any way to form a square using the planks without breaking them of overlapping them. (Hint: complexity $O(4^n/2^)$)
# 8 puzzle: Solve 8 puzzle. (Hint: Each position is solvable in at most 31 moves.)