Data Stream Problem     Fri, 29 Jan 2010 17:11 Data writes: A network streams to you 100 Mega Bytes of data at a time. In all, you will receive a total of 800 Mega Bytes. I.e. you are to receive a total of 8 such blocks, each 100 Mega Byte in size. However, you donot know when each block will arrive though the total time is bounded. Our total time bound is thirty minutes. I.e. all the 8 blocks will arrive within thirty minutes. Your main memory(RAM) is limited to 100 Mega Byte though you have unlimited(enough) hard disk space.  Give an efficient algorithm to sort the entire 800 Megabyte of data as quick as possible(think hard real time constraints). Note: You can assume that each element that is to be sorted is of positive integer of length 128 bits. Edit: Now consider another scenario. Say, that you have all the 8 blocks(i.e the entire 800 Mega Bytes) on your hard disk. Would you use the same strategy as you used for the earlier case to sort it time efficiently or would you go for a new strategy? Explain. read comments(9) / write comment / 418 views

Uniform distribution     Thu, 21 Jan 2010 17:33 Cygnum writes: This one is (supposedly) from a job interview for Google: You're being streamed an array of numbers. Every second you receive the next cell in the array. The array is final but you don't know when it ends or what's it total length. Your job is to randomly pick one of the numbers from the array so that every number has the same probability of being selected i.e. if the array happens to be 10 cells long, each cell will have a probability of exactly 1/10 of being selected. The catch is that you cannot locally save the array since that might take too much space. How do you do it? read comments(12) / write comment / 930 views

The Straw!     Wed, 06 Jan 2010 19:25 bulibuta writes: A man is found dead in the desert with a straw in his hand... How did he die? RULES (you know I love them): -- if you already know the puzzle don't spoil it for the others, you can message me to confirm if you want -- you can ask me any question about the puzzle in a form that I can answer with yes/no/irrelevant. read comments(59) / write comment / 3200 views

Harry Wires!     Tue, 05 Jan 2010 03:53 newsMonkey writes: Here's a nice problem I came across the other day: ``A bunch of n wires have been labeled at one end with alphabetic codes A, B... The wire identification problem asks for an efficient procedure to mark the other end of the bunch with the corresponding labels. The wires run underground so you can't track them individually and any wire is visibly indistinguishable from any other (except for the labeling).'' NOTE: try to solve the finite cases first and then go after the generalization. RULES:     -- try to be smart about it, don't google it because every idiot can do that     -- try to be as explicit as possible, don't make statements you can't back-up and explain     -- for lolcats, ``funny'' comments and the like, there's always the off-topic forum or /dev/null read comments(27) / write comment / 2042 views

older posts...

Top of page

New Order news rss feed, a sms rss feed or a complete list.