From b4ee283b23b8a85c75339e07b0adf43d1c3ca770 Mon Sep 17 00:00:00 2001 From: William Carroll 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 ++++++++++++++++++++++++++++++++++++++ 1 file changed, 40 insertions(+) create mode 100644 crack_the_coding_interview/11_1.py (limited to 'crack_the_coding_interview/11_1.py') 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 + +################################################################################ +# 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!') -- cgit 1.4.1