I guess the googlers woud answer having "0:1" for duplicates.
Big problem #1: insertions for 1M integers would take ages.
Big problem #2: And some distributions can't be covered this way. For example, 1m integers with distances 0:99 (e.g. +99 each one). Now think the same but with random distance in the range of 0:99. (Note 99999999/1000000 = 99.99, so it's possible input)
Big problem #1: insertions for 1M integers would take ages.
Big problem #2: And some distributions can't be covered this way. For example, 1m integers with distances 0:99 (e.g. +99 each one). Now think the same but with random distance in the range of 0:99. (Note 99999999/1000000 = 99.99, so it's possible input)
Google's approach is nonsense, too.