about summary refs log tree commit diff
path: root/scratch/facebook
diff options
context:
space:
mode:
authorWilliam Carroll <wpcarro@gmail.com>2020-11-21T13·35+0000
committerWilliam Carroll <wpcarro@gmail.com>2020-11-21T13·35+0000
commit0ccaa22032d48db8b3961ab4a7af45562eff8d41 (patch)
treec195e6496bb047309381e99a12cb8d1331cab7b4 /scratch/facebook
parent847aad2a146583b21377a2c748b01f9a2df591a5 (diff)
Solve "find duplicate" using a graph
This problem is unusually difficult, but the solution is elegant.
Diffstat (limited to 'scratch/facebook')
-rw-r--r--scratch/facebook/find-duplicate-beast-mode.py57
1 files changed, 57 insertions, 0 deletions
diff --git a/scratch/facebook/find-duplicate-beast-mode.py b/scratch/facebook/find-duplicate-beast-mode.py
new file mode 100644
index 000000000000..e246415efd1f
--- /dev/null
+++ b/scratch/facebook/find-duplicate-beast-mode.py
@@ -0,0 +1,57 @@
+def advance(position, xs):
+    """
+    Return the next element in `xs` pointed to by the current `position`.
+    """
+    return xs[position - 1]
+
+def find_duplicate(xs):
+    """
+    Find the duplicate integer in the list, `xs`.
+    """
+    beg = xs[-1]
+    a = beg
+    b = advance(a, xs)
+    # Find the first element of the cycle
+    cycle_beg = None
+    while a != b:
+        cycle_beg = a
+        a = advance(a, xs)
+        b = advance(b, xs)
+        b = advance(b, xs)
+    # The duplicate element is the element before the `cycle_beg`
+    a = beg
+    result = None
+    while a != cycle_beg:
+        result = a
+        a = advance(a, xs)
+    return result
+
+def find_duplicate(xs):
+    """
+    This is the solution that InterviewCake.com suggests.
+    """
+    # find length of the cycle
+    beg = xs[-1]
+    a = beg
+    for _ in range(len(xs)):
+        a = advance(a, xs)
+    element = a
+    a = advance(a, xs)
+    n = 1
+    while a != element:
+        a = advance(a, xs)
+        n += 1
+    # find the first element in the cycle
+    a, b = beg, beg
+    for _ in range(n):
+        b = advance(b, xs)
+    while a != b:
+        a = advance(a, xs)
+        b = advance(b, xs)
+    return a
+
+xs = [2, 3, 1, 3]
+result = find_duplicate(xs)
+print(result)
+assert result == 3
+print("Success!")