about summary refs log tree commit diff
path: root/scratch/facebook/find-duplicate-optimize-for-space.py
blob: 7c491aef604e71839591dfde3888e4a1412c02e7 (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import random

def find_duplicate(xs):
    print(xs)
    # entry point in our cycle is the duplicate
    i = xs[0]
    j = xs[xs[0]]
    while i != j:
        print(i, xs[i], j, xs[j])
        i = xs[i]
        j = xs[xs[j]]
    # detect cycle
    j = 0
    while i != j:
        i = xs[i]
        j = xs[j]
    return xs[i]

n = random.randint(5, 10)
xs = [random.randint(0, n - 1) for _ in range(n)]
result = find_duplicate(xs)
print(xs, result)