Add 'universe/' from commit '8ad51b24dd8719840aac47134835ea25cfe1b0b8'

git-subtree-dir: universe
git-subtree-mainline: 15110e6de9f85537c7847267caa35fa068aea001
git-subtree-split: 8ad51b24dd8719840aac47134835ea25cfe1b0b8

2 files changed, 51 insertions, 0 deletions

diff --git a/universe/crack_the_coding_interview/11_1.py b/universe/crack_the_coding_interview/11_1.py
new file mode 100644
index 000000000000..ec7b65dae0c3
--- /dev/null
+++ b/universe/crack_the_coding_interview/11_1.py
@@ -0,0 +1,40 @@
+# Implementation for a problem from "Crack the Coding Interview".
+#
+# Dependencies:
+# - python 2.7.16
+# - entr 4.1
+#
+# To run the tests, run: `python 11_1.py`
+# For a tight development loop, run: `echo 11_1.py | entr python /_`
+#
+# Author: William Carroll <wpcarro@gmail.com>
+
+################################################################################
+# Implementation
+################################################################################
+def insert_sorted(xs, ys):
+    """
+    Merges `ys` into `xs` and ensures that the result is sorted.
+
+    Assumptions:
+    - `xs` and `ys` are both sorted.
+    - `xs` has enough unused space to accommodate each element in `ys`.
+    """
+    for y in ys:
+        xi = xs.index(None) - 1
+        yi = xs.index(None)
+        xs[yi] = y
+        while xi != -1 and y < xs[xi]:
+            xs[xi], xs[yi] = xs[yi], xs[xi]
+            xi, yi = xi - 1, yi - 1
+    return xs
+
+################################################################################
+# Tests
+################################################################################
+assert insert_sorted([1, 3, 5, None, None], [2, 4]) == [1, 2, 3, 4, 5]
+assert insert_sorted([None, None], [2, 4]) == [2, 4]
+assert insert_sorted([None, None], [2, 4]) == [2, 4]
+assert insert_sorted([1, 1, None, None], [0, 0]) == [0, 0, 1, 1]
+assert insert_sorted([1, 1, None, None], [1, 1]) == [1, 1, 1, 1]
+print('All tests pass!')
diff --git a/universe/crack_the_coding_interview/to_tree.hs b/universe/crack_the_coding_interview/to_tree.hs
new file mode 100644
index 000000000000..8496d88c0c0c
--- /dev/null
+++ b/universe/crack_the_coding_interview/to_tree.hs
@@ -0,0 +1,11 @@
+data Tree a = Node a [Tree a] deriving (Show)
+
+withRoot :: [a] -> [Tree a]
+withRoot xs = xs |> toThing |> fmap buildTree
+
+buildTree :: (a, [a])
+
+
+toTree :: [a] -> Tree a
+toTree [x]      = Node x []
+toTree [x | xs] = Node x (toTree xs)