From b4ee283b23b8a85c75339e07b0adf43d1c3ca770 Mon Sep 17 00:00:00 2001
From: William Carroll <wpcarro@gmail.com>
Date: Wed, 15 Jan 2020 14:23:37 +0000
Subject: Add "Crack the Coding Interview" examples

I believe I have multiple other snippets and attempts scattered across /tmp,
~/programming, and other directories. Again, I created these files and others
before the mono-repo.
---
 crack_the_coding_interview/11_1.py    | 40 +++++++++++++++++++++++++++++++++++
 crack_the_coding_interview/to_tree.hs | 11 ++++++++++
 2 files changed, 51 insertions(+)
 create mode 100644 crack_the_coding_interview/11_1.py
 create mode 100644 crack_the_coding_interview/to_tree.hs

diff --git a/crack_the_coding_interview/11_1.py b/crack_the_coding_interview/11_1.py
new file mode 100644
index 000000000000..ec7b65dae0c3
--- /dev/null
+++ b/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/crack_the_coding_interview/to_tree.hs b/crack_the_coding_interview/to_tree.hs
new file mode 100644
index 000000000000..8496d88c0c0c
--- /dev/null
+++ b/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)
-- 
cgit 1.4.1