Saturday, October 8, 2011

Find the missing number

Given a db with about 300Millions social numbers where each number is  9 digits find a number that is missing. You have 2MB of Ram and unlimited disk

Solution
300Millions = 300 * 10^6 = 3 * 10^8

Suppose we take 10 counters and "hash" each number considering only the highest order digit, incrementing the counter if a given number has that starting digit.  One missing number would be located by the counter with the lowest value. That is the intuition, we can now use a bitmap which fits 2MB of Ram and apply the same principle.

No comments:

Post a Comment