Suppose you have an array of 99 numbers. The array contains the digits 1 to 100 with one digit missing. Describe four different algorithms to compute the missing number. Two of these should optimize for low storage and two of these should optimize for fast processing.

1. Describe how you would store a social graph in a relational database.
2. Describe an efficient algorithm to determine whether or not person X is a 2nd degree connection of person Y.
3. Describe an efficient algorithm to determine whether or not person X is a 3rd degree connection of person Y.
4. How can you make #3 very quick. E.g. how does Linked In compute 3rd degree connections quickly?

Write a string to find a substring in a given string. Do this in O(n) or better

What is a hashtable? Give an example of a type of problem that a hashtable is useful for.

Explain big o notation and how it is useful in computer science to classify algorithms.

• What order is a hash table lookup?
• What order is determining if a number is even or odd?
• What order is finding an item in an unsorted list?
• What order is a binary search?

For the data structures: Array and Linked List explain:

• Where you might use them
• Operations that are commonly supported (add, insert etc)

Implement a function with signature find_chars(string1, string2) that takes two strings and returns a string that contains only the characters found in string1 and string two in the order that they are found in string1. Implement a version of order N*N and one of order N.

Given a circular list of integers (when you reach the end of the list you come back to the beginning), what is the most efficient algorithm to find the smallest integer in the list?

For example: circular_list = [22, 52, 66, 82, 5, 8, 12, 19].

Given a N by N matrix of both negative and positive integers. Write an efficient algorithm to find the sub-matrix with the largest sum of all the contained elements.

Design a system to efficiently calculate the top 1MM Google search queries and create a report of these. Additionally:

• You are given twelve servers
• Each has two processors, 4GB of ram and four 400GB hard drives.
• The machines are networked
• The log data as roughly 100 Billion log lines in it.
• The log data comes in twelve, 320 Gb files.
• Each line of the files has roughly 40 search queries
• You can only use open source software or software that you write.

Given an array A[N] containing N numbers. Crate an array Output[N] where Output[i] is equal to the product of all the elements of A[N] except A[i].

For example Output[0] is the product of A[1] to A[N-1] and Output[1] is the product of A[0] and from A[2] to A[N-1].

Do this without using the division operator. Do it in O(n).

You are given a linked list of integers of length N.

N is very large and you don’t know N.

Write a function to return k completely random numbers from the list.

Do this in O(n).

Hint: Use random function rand() (returns a number between 0 and 1) and irand() (return either 0 or 1) 2.

Write a function to efficiently determine the result of a game of Tic Tac Toe.

The function takes as input the game and the sign (x or o) of the player. The function returns if this player has won the game or not.

Carefully consider both the data structure and the algorithm for your answer.

Given any integer, efficiently find the next highest integer that uses the same digits.

For example if the number is 15432, you should return 21345.

Write a function that, given a word and a dictionary will efficiently return the minimal edits (character addition or deletion) to get to a word that exists in the dictionary.

Write a function to efficiently determine if a linked list has a cycle in it.

Given two arrays of strings, A and B.

B contains every element in A, and has one additional member, for example:

* A = ['dog', 'cat', 'monkey]
* B = ['cat', 'rat', 'dog', 'monkey']

Write a function to find the extra string in B. Do this in O(n)

Express the following table as a static structure, and write a function, find_routes(source, destination) that efficiently outputs all possible routes.

Source  | Dest
~~~~~~    ~~~~
Seattle | LA
LA      | Florida
LA      | Maine
Florida | Seattle
Seattle | Florida

The solution for find_routes('Seattle', 'Florida') should be [Seattle -> Florida, Seattle -> LA -> Florida]

Write a function to efficiently convert a floating point number to a rational number. For example, given 0.125 return "1/8"

The least common multiple of a set of integers is the smallest positive integer that is a multiple of all of the integers in the set.

Write a function that takes an array of integers and efficiently calculates and returns the LCM.

Write function that takes a binary tree and efficiently returns the Nth smallest element.

For example, if N=4, and the tree looks like:

    3
   / \
  2   5
 /   / \
1   4   6

The function should return 4.

Given a file of size 1TB, containing only 32 bit integers, describe how you would efficiently sort it. You have only 2GB of memory available.

Write a function to efficiently find the fifth maximum element in a binary search tree. Try to do this without using significant additional storage.