Ass Hat
Home
News
Events
Bands
Labels
Venues
Pics
MP3s
Radio Show
Reviews
Releases
Buy$tuff
Forum
  Classifieds
  News
  Localband
  Shows
  Show Pics
  Polls
  
  OT Threads
  Other News
  Movies
  VideoGames
  Videos
  TV
  Sports
  Gear
  /r/
  Food
  
  New Thread
  New Poll
Miscellaneous
Links
E-mail
Search
End Ass Hat
login

New site? Maybe some day.
Posting Anonymously login: [Forgotten Password]
returntothepit >> discuss >> you aren't geek enough for this thread... by the_reverend on Dec 6,2005 2:00pm
Add To All Your Pages!
toggletoggle post by the_reverend   at Dec 6,2005 2:00pm
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



toggletoggle post by Beakey   at Dec 6,2005 2:04pm
Nobody should have to answer questions like that.



toggletoggle post by the_reverend   at Dec 6,2005 2:08pm
not even jon freaking tesh



toggletoggle post by brian_dc  at Dec 6,2005 2:13pm
I've seen a lot of math...but I'm no coder.



Enter a Quick Response (advanced response>>)
Username: (enter in a fake name if you want, login, or new user)SPAM Filter: re-type this (values are 0,1,2,3,4,5,6,7,8,9,A,B,C,D,E, or F)
Message:  b i u  add: url  image  video(?)show icons
remember:type $#1!, get hit
[default homepage] [print][11:55:06am Mar 28,2024
load time 0.01272 secs/12 queries]
[search][refresh page]