about summary refs log tree commit diff
path: root/scratch/facebook/find-duplicate-optimize-for-space.py
diff options
context:
space:
mode:
authorWilliam Carroll <wpcarro@gmail.com>2020-11-12T14·37+0000
committerWilliam Carroll <wpcarro@gmail.com>2020-11-12T14·37+0000
commitaa66d9b83d5793bdbb7fe28368e0642f7c3dceac (patch)
treea0e6ad240fe1cdfd2fcdba7266931beea9fbe0d6 /scratch/facebook/find-duplicate-optimize-for-space.py
parentd2d772e43e0d4fb1bfaaa58d7de0c9e2cc274a25 (diff)
Add coding exercises for Facebook interviews
Add attempts at solving coding problems to Briefcase.
Diffstat (limited to 'scratch/facebook/find-duplicate-optimize-for-space.py')
-rw-r--r--scratch/facebook/find-duplicate-optimize-for-space.py22
1 files changed, 22 insertions, 0 deletions
diff --git a/scratch/facebook/find-duplicate-optimize-for-space.py b/scratch/facebook/find-duplicate-optimize-for-space.py
new file mode 100644
index 000000000000..7c491aef604e
--- /dev/null
+++ b/scratch/facebook/find-duplicate-optimize-for-space.py
@@ -0,0 +1,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)