NOTE: I will be using well-known computer science and programming terminology. If you don't know what something means, search the web. I'm posting this because i couldnt find any damned sample questions before my interview.
also NOTE: The interviewers did not describe these problems exactly as i am describing them. I am describing them in a condensed form, so before attempting the problem, take the time to figure out whats going on first. The interviewers described these problems to me verbally and with diagrams.
=========================================================
Question #1) Given k sorted streams where each stream could possibly be infinite in length, describe an efficient algorithm to merge the k streams into a new stream (also in sorted order).
Question #2) Given a set of KEY->VALUE pairs such that each KEY is unique, describe a method of storing these pairs on disk, and a method for accessing the corresponding VALUE given a KEY. Assume that RAM is fixed at 1gb and the set of pairs requires 40gb.
HINT: we are trying to minimize page-transfers
Question #3) Given N computers networked together, with each computer storing N integers, describe a procedure for finding the median of all of the numbers. Assume that a computer can only hold O(N) integers (i.e. no computer can store all N^2 integers). Also assume that there exists a computer on the network without integers, that we can use to interface with the computers storing the integers.
Question #4) Given the sequence S1 = {a,b,c,d,...,x,y,z,aa,ab,ac.... } and given that this sequence corresponds (term for term) to the sequence S2 = {1,2,3,4,....}
Write code to convert an element of S1 to the corresponding element of S2. Write code to convert an element of S2 to the corresponding element of S1.
Question #5) Given a binary tree with the following constraints:
a) A node has either both a left and right child OR no children
b) The right child of a node is either a leaf or NULL
write code to invert this tree. HINT: Draw this out
Question #6) Given a square with side length = 1, describe all points inside square that are closer to the center of the square than to the edge of the square.
Question #7) How many 0's are at the end of N!
hint: look at the prime factorization of N!
Question #8) Given an array A[string], an array of strings where each string represents a word in a text document. Also given 3 search terms T1, T2, and T3 and 3 corresponding sorted sequences of integers S1, S2, and S3 where each integer in Si represents an index in A where search term Ti occured (i.e. S1, S2, and S3 contain the locations of the search terms in our array of words). Now find a minimal subarray of A that contains all of the search terms T1, T2, and T3. Extend this algorithm for an arbitrary number of search terms.
hint: think of the brute force algorithm first
Question #9) Design a data structure that supports push(), pop(), and min() all in O(1) time
Q: "You are shrunk to the height of a nickel and your mass is proportionally reduced so as to maintain your original density. You are then thrown into an empty glass blender. The blades will start moving in 60 seconds. What do you do?"
Q: "How would you find out if a machine's stack grows up or down in memory?"
Q: "Explain a database in three sentences to your eight-year-old nephew."
Q: "How many gas stations would you say there are in the United States?"
=========================================================
also NOTE: The interviewers did not describe these problems exactly as i am describing them. I am describing them in a condensed form, so before attempting the problem, take the time to figure out whats going on first. The interviewers described these problems to me verbally and with diagrams.
=========================================================
Question #1) Given k sorted streams where each stream could possibly be infinite in length, describe an efficient algorithm to merge the k streams into a new stream (also in sorted order).
Question #2) Given a set of KEY->VALUE pairs such that each KEY is unique, describe a method of storing these pairs on disk, and a method for accessing the corresponding VALUE given a KEY. Assume that RAM is fixed at 1gb and the set of pairs requires 40gb.
HINT: we are trying to minimize page-transfers
Question #3) Given N computers networked together, with each computer storing N integers, describe a procedure for finding the median of all of the numbers. Assume that a computer can only hold O(N) integers (i.e. no computer can store all N^2 integers). Also assume that there exists a computer on the network without integers, that we can use to interface with the computers storing the integers.
Question #4) Given the sequence S1 = {a,b,c,d,...,x,y,z,aa,ab,ac.... } and given that this sequence corresponds (term for term) to the sequence S2 = {1,2,3,4,....}
Write code to convert an element of S1 to the corresponding element of S2. Write code to convert an element of S2 to the corresponding element of S1.
Question #5) Given a binary tree with the following constraints:
a) A node has either both a left and right child OR no children
b) The right child of a node is either a leaf or NULL
write code to invert this tree. HINT: Draw this out
Question #6) Given a square with side length = 1, describe all points inside square that are closer to the center of the square than to the edge of the square.
Question #7) How many 0's are at the end of N!
hint: look at the prime factorization of N!
Question #8) Given an array A[string], an array of strings where each string represents a word in a text document. Also given 3 search terms T1, T2, and T3 and 3 corresponding sorted sequences of integers S1, S2, and S3 where each integer in Si represents an index in A where search term Ti occured (i.e. S1, S2, and S3 contain the locations of the search terms in our array of words). Now find a minimal subarray of A that contains all of the search terms T1, T2, and T3. Extend this algorithm for an arbitrary number of search terms.
hint: think of the brute force algorithm first
Question #9) Design a data structure that supports push(), pop(), and min() all in O(1) time
Q: "You are shrunk to the height of a nickel and your mass is proportionally reduced so as to maintain your original density. You are then thrown into an empty glass blender. The blades will start moving in 60 seconds. What do you do?"
Q: "How would you find out if a machine's stack grows up or down in memory?"
Q: "Explain a database in three sentences to your eight-year-old nephew."
Q: "How many gas stations would you say there are in the United States?"
=========================================================
Facebook
Twitter