you aren't geek enough for this thread...[views:1563][posts:3]_____________________________________ [Dec 6,2005 2:00pm - the_reverend ""] this is from a friend of a friend's interview... I can answer some of them off the top of my head.. but man, all the dude wanted to do was flip burgers. 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 |
| _______________________________ [Dec 6,2005 2:04pm - Beakey ""] Nobody should have to answer questions like that. |
| _____________________________________ [Dec 6,2005 2:08pm - the_reverend ""] not even jon freaking tesh |
| _________________________________ [Dec 6,2005 2:13pm - brian_dc ""] I've seen a lot of math...but I'm no coder. |