Problem:
Find the number of integers in [-10,000, 10,000] such that it is representable as a sum of two distinct integers in a list of a million integers.
Solution:
The original solution is to use hash table to look up, but that is too slow for this problem, people reported that will take hours. The distribution of the number has a very wide range and therefore sorting helped a lot, in particular, we will keep two pointers, left and right
If data[left] + data[right] > 10,000, there is no way there are any solution starting with data[right], so we decrement right by 1.
Similarly, if data[left] + data[right] < -10,000, we can increment left by 1.
Otherwise we found a match, but then what - we cannot discard left/right.
Now just move on a try if data[start] can match anything on the right by scanning right inward without moving the actual right pointer yet. Similarly we do the same for data[end].
With the above exercise, we should be exhausted everything that can start with start or end, so we are done with them, we decrement right by 1 and increment left by 1.
Here is the code of that!
Find the number of integers in [-10,000, 10,000] such that it is representable as a sum of two distinct integers in a list of a million integers.
Solution:
The original solution is to use hash table to look up, but that is too slow for this problem, people reported that will take hours. The distribution of the number has a very wide range and therefore sorting helped a lot, in particular, we will keep two pointers, left and right
If data[left] + data[right] > 10,000, there is no way there are any solution starting with data[right], so we decrement right by 1.
Similarly, if data[left] + data[right] < -10,000, we can increment left by 1.
Otherwise we found a match, but then what - we cannot discard left/right.
Now just move on a try if data[start] can match anything on the right by scanning right inward without moving the actual right pointer yet. Similarly we do the same for data[end].
With the above exercise, we should be exhausted everything that can start with start or end, so we are done with them, we decrement right by 1 and increment left by 1.
Here is the code of that!
Hi! I did the assignment years ago using hash table with specially designed hash function and can tell that it runs on par with the solution above. I just tested my old solution with the original assignment input file and got 0.9 seconds with my C solution. As I am learning Python, I rewrote it in Python3 and it yelded twice as short but terminated in 7 seconds. The above solution in C++ is terminating in 0.9 seconds. Testing was done on Devuan GNU/Linux with 'time' command.
ReplyDeleteHi Robert, could you please share details about the hash function you have designed?
DeleteHi Robert, could you please share details about the hash function you have designed?
Deletewhat is the answer?
ReplyDelete