Forum
  Classifieds
  News
  Localband
  Shows
  Show Pics
  Polls

  OT Threads
  Other News
  Movies
  VideoGames
  Videos
  TV
  Sports
  Gear
  /r/
  Food

  New Thread
  New Poll

E-mail

New site? Maybe some day.

Username:

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:

UBB enabled. HTML disabled Spam Filtering enabledIcons: (click image to insert) Show All - pop

b i u add: url image video(?)

:	post by the_reverend at 2005-12-06 14:00:48

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

[default homepage]

[print][

9:29:35am Apr 28,2024
load time 0.02087 secs/10 queries]

[search]

[refresh page]