subtree(users/wpcarro): docking briefcase at '24f5a642' r/3226

git-subtree-dir: users/wpcarro
git-subtree-mainline: 464bbcb15c09813172c79820bcf526bb10cf4208
git-subtree-split: 24f5a642af3aa1627bbff977f0a101907a02c69f
Change-Id: I6105b3762b79126b3488359c95978cadb3efa789

1 files changed, 67 insertions, 0 deletions

diff --git a/users/wpcarro/scratch/facebook/moderate/unsorted-substring.py b/users/wpcarro/scratch/facebook/moderate/unsorted-substring.py
new file mode 100644
index 000000000000..de7326b05822
--- /dev/null
+++ b/users/wpcarro/scratch/facebook/moderate/unsorted-substring.py
@@ -0,0 +1,67 @@
+# Write a function that accepts an array of integers and returns the indices for
+# the starting and ending integers that, if their elements were sorted, the
+# entire array would be sorted.
+
+################################################################################
+# First Attempt
+################################################################################
+
+def unsorted_substring(xs):
+    ys = xs[:]; ys.sort()
+    m = 0
+    while xs[m] == ys[m]:
+        m += 1
+        if m >= len(xs):
+            return -1, -1
+    n = len(xs) - 1
+    while xs[n] == ys[n]:
+        n -= 1
+    return m, n
+
+################################################################################
+# Second Attempt
+################################################################################
+
+def unsorted_substring_2(xs):
+    beg = 1
+    while xs[beg - 1] <= xs[beg]:
+        beg += 1
+        if beg >= len(xs):
+            return -1, -1
+    end = len(xs) - 2
+    while xs[end + 1] >= xs[end]:
+        end -= 1
+
+    min_mid = xs[beg]
+    max_mid = xs[beg]
+    i = beg + 1
+    while i <= end:
+        min_mid = min(min_mid, xs[i])
+        max_mid = max(max_mid, xs[i])
+        i += 1
+
+    # beg -= 1 until max(lhs) <= min(mid)
+    while beg - 1 >= 0 and xs[beg - 1] >= min_mid:
+        beg -= 1
+
+    # end += 1 while max(mid) <= min(rhs)
+    while end + 1 < len(xs) and max_mid >= xs[end + 1]:
+        end += 1
+    return beg, end
+
+################################################################################
+# Tests
+################################################################################
+
+xs = [
+    [1,2,4,7,10,11,7,12,6,7,16,18,19],
+    [1,2,3,4],
+    [4,3,2,1],
+    [1,3,2,4],
+    [2,1,3,4],
+]
+
+for x in xs:
+    print("Testing: {}".format(x))
+    print("1) {}".format(unsorted_substring(x)))
+    print("2) {}".format(unsorted_substring_2(x)))