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?"
================================================== =======
In case you were wondering, no, i didn't get the job. I attended one of their "College Days" a couple weeks back for my second round of interviews. I was only asked 6 of the above questions (#1, #2, #3,#4, #5, #8) and out of them i answered 3 correctly, 2 sorta correctly after receiving hints, and 1 i didnt answer at all (this was also my first interview on campus and my first real tech interview ever.) Basically my impression is: if you want a job at Google, you better eventually arrive at complete and optimal solutions to all of the questions.
I feel like i could of done better ( i was nervous and only got 3 hours of sleep the night before), but i learned a lot about technical interviews and here are some tips:
**** IMPORTANT TIPS FOR INTERVIEWING AT TECH COMPANIES:
#1) If you're asked to write code, first forumlate an algorithm in your head. Next DOUBLE check that algorithm, even if it takes 5 minutes, and even if it takes drawing some detailed example cases. Whatever you do, make 100% SURE that what you're going to code is correct, THEN write the code.
After you're finished writing the code, the interviewer will probably have you explain the code and illustrate a test run of the code, possibly on a white board. If your code is incorrect, you both will eventually arrive at that conclusion, and by the time you've found out its incorrect, there won't be enough time to fix the code. This is why its 100% important to get it the first time. This exact scenario happened to me - i tried writing up a solution real fast (#5) , but it back fired on me.
#2) If you're asked to describe an algorithm for solving a particular problem efficiently, FIRST think of the brute-force inefficient case. The brute force algorithm will most likely be very obvious, so go over the brute force approach in detail first. This is key, because a thorough investigation of the brute force algorithm will help you understand the problem space better, and may lead you directly to the efficient algorithm. I didn't do this during my first interview (problem #8) and i didnt arrive at the answer. I tried doing the same problem at home one night, worked out the brute force algorithm, and within minutes i had the optimal solution.
#3) Don't try to rush, just stay calm and go through things methodically.
[/b]
ones3k is offline Reply With Quote
No comments:
Post a Comment