From aa66d9b83d5793bdbb7fe28368e0642f7c3dceac Mon Sep 17 00:00:00 2001
From: William Carroll <wpcarro@gmail.com>
Date: Thu, 12 Nov 2020 14:37:29 +0000
Subject: Add coding exercises for Facebook interviews

Add attempts at solving coding problems to Briefcase.
---
 .../facebook/find-duplicate-optimize-for-space.py  | 22 ++++++++++++++++++++++
 1 file changed, 22 insertions(+)
 create mode 100644 scratch/facebook/find-duplicate-optimize-for-space.py

(limited to 'scratch/facebook/find-duplicate-optimize-for-space.py')

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)
-- 
cgit 1.4.1