Phone Interview:

Based on previous experience and one question related to databases: Design a database for querying the interests/likes of site users. Assume the number of users is over 6 billion.

On-Site Interview:

Round 1: Consider a linked list with nodes having a next pointer and a random pointer. Replicate the list.

Round 2: Find out if a linked list is cyclic. If it is cyclic, remove the cycle.

Round 3: You are given an array of strings, a starting word, and an ending word. Design an algorithm and code (any language) to give the shortest path from the starting word to the ending word, if a path exists. You can move between one word to another by only changing one character in each word.

Time: 30 minutes

Example array: {"cat", "bot", "bat", "bog", "mat"}, starting word: "cat", ending word: "bog"

Output: Path exists Path: cat->bat->bot->bog

I could not solve this problem during the interview. This can be done by constructing a graph and using a shortest path algorithm. Each word would be a node in your graph and it connects to a word that differs by only one character. Ex: "cat" connects to "bat" and "mat".

Question in Round 3 on graphs and shortest path.