Just back from an job interview, one question really sucks! Any idea? It is given 45 mintues to state your thought (either how to do it, or why you can not do it). (Type from what I remember)
1) You choose 5000 different intergers (you can choose any 5000 integers you want to use, just be sure they are different from each other). 2) Take 200 numbers from them by random to form a set. Repeat this many times so you will have many such set. If you like, you can assume these sets are saved to disk (cause there are "many" of them), and step 3 is to test them one by one. 3) For each set (200 numbers), can you design a method that can QUICKLY test whether a certain number k is in it or not? (k belongs to the initial 5000 numbers) 4) Repeat step 3 many times with different k. 5) Require: the memory and time is limited, which means: the most naive method of scaning through (linear or use a hashtable) each set to test k, and repeat for each set will not give you credit. 6) If your method needs some calculation time, make sure the test step takes as littile time as possible (if you have whatever "preprocess", they can take longer time). 7) If you think this can not be done (you can not do much better than the naive method above), please state your reasons (what will be the limit). ----------------- Try to think it over before read my "wrong" method, in case it may mislead you. :-)) .. .. .. .. .. What I think is to find a method to "hash" these 200 integers to one or two small values. My answer at that time, which unluckly did not work, was to use prime numbers: Select 5000 prime numbers. For each 200 randomly selected numbers, times them up to get a "hash value" v. When test, just see if v can be divided by k. So the test step only has a divide operation, and since we "hash" 200 numbers to one value, this does not need to use much memory since we only need to keep one v for each set. However, when I came back from interview, I found my method will not work with 5000 initial numbers: times 200 prime number will get value out of range even if we use "long" type data. Prime numbers are so big, even if I define my own number type, it is quite possible to use more memory than the 200 number set itself! Maybe this can not be done, I am thinking, but I can not say why it can not be done efficiently. :-(
