diff options
| author | William Carroll <wpcarro@gmail.com> | 2020-03-26T11·55+0000 |
|---|---|---|
| committer | William Carroll <wpcarro@gmail.com> | 2020-03-26T11·55+0000 |
| commit | 062af32e4eadd7d808079b538227bf336ce90f4e (patch) | |
| tree | f95f3de25b8ac157c30994ea1deb5faa9d0cdf7a /scratch/deepmind/part_two/todo.org | |
| parent | 3ff6ae36975f1293229f27a4e60d1e1334ad6f77 (diff) | |
Solve InterviewCake's find duplicate beast mode
Write a function to find a duplicate item in a list of numbers. The values are in the range [1, n]; the length of the list is n + 1. The solution should run in linear time and consume constant space. The solution is to construct a graph from the list. Each graph will have a cycle where the last element in the cycle is a duplicate value. See the solution for specific techniques on how to compute the length the cycle without infinitely looping.
Diffstat (limited to 'scratch/deepmind/part_two/todo.org')
| -rw-r--r-- | scratch/deepmind/part_two/todo.org | 4 |
1 files changed, 2 insertions, 2 deletions
diff --git a/scratch/deepmind/part_two/todo.org b/scratch/deepmind/part_two/todo.org index 5d296b9b5287..ee91e47551c7 100644 --- a/scratch/deepmind/part_two/todo.org +++ b/scratch/deepmind/part_two/todo.org @@ -26,7 +26,7 @@ ** DONE 2nd Largest Item in a Binary Search Tree ** DONE Graph Coloring ** DONE MeshMessage -** TODO Find Repeat, Space Edition BEAST MODE +** DONE Find Repeat, Space Edition BEAST MODE * Dynamic programming and recursion ** TODO Recursive String Permutations ** TODO Compute nth Fibonacci Number @@ -45,7 +45,7 @@ ** TODO Does This Linked List Have A Cycle? ** TODO Reverse A Linked List ** TODO Kth to Last Node in a Singly-Linked List -** TODO Find Repeat, Space Edition BEAST MODE +** DONE Find Repeat, Space Edition BEAST MODE * System design ** TODO URL Shortener ** TODO MillionGazillion |