about summary refs log tree commit diff
path: root/data_structures_and_algorithms/norman.py
diff options
context:
space:
mode:
authorWilliam Carroll <wpcarro@gmail.com>2020-01-15T14·25+0000
committerWilliam Carroll <wpcarro@gmail.com>2020-01-15T14·25+0000
commitd4d8397e5ffe6734ed5861e48ce475848956a3fe (patch)
tree7f0f8563750a2084ad9a4b9908cbb5316fe6bf10 /data_structures_and_algorithms/norman.py
parentb4ee283b23b8a85c75339e07b0adf43d1c3ca770 (diff)
Add InterviewCake.com examples
Adds some of the code I generated while studying for a role transfer at Google
using the fantastic resource, InterviewCake.com. This work predates the
mono-repo.

I should think of ways to DRY up this code and the code in
crack_the_coding_interview, but I'm afraid I'm creating unnecessary work for
myself that way.
Diffstat (limited to 'data_structures_and_algorithms/norman.py')
-rw-r--r--data_structures_and_algorithms/norman.py78
1 files changed, 78 insertions, 0 deletions
diff --git a/data_structures_and_algorithms/norman.py b/data_structures_and_algorithms/norman.py
new file mode 100644
index 000000000000..379ba92abba8
--- /dev/null
+++ b/data_structures_and_algorithms/norman.py
@@ -0,0 +1,78 @@
+
+
+
+# Write a function with the following type signature:L
+# equal? :: String -> String -> Bool
+#
+# Determine equality between two inputs with backspace characters encoded as
+# "<".
+
+################################################################################
+# Solution 1
+################################################################################
+
+# from collections import deque
+
+# def equal(a, b):
+#     sa = deque()
+#     sb = deque()
+
+#     for c in a:
+#         if c == '<':
+#             sa.pop()
+#         else:
+#             sa.append(c)
+
+#     for c in b:
+#         if c == '<':
+#             sb.pop()
+#         else:
+#             sb.append(c)
+
+#     return sa == sb
+
+################################################################################
+# Solution 2
+################################################################################
+
+def handle_dels(num_dels, i, xs):
+    if i < 0:
+        return -1
+
+    while xs[i] == '<':
+        num_dels += 1
+        i -= 1
+
+    while num_dels > 0 and xs[i] != '<':
+        num_dels -= 1
+        i -= 1
+
+    if xs[i] == '<':
+        return handle_dels(num_dels, i, xs)
+    else:
+        return i
+
+def update_index(i, xs):
+    # TODO: Indexing into non-available parts of a string.
+    if xs[i] != '<' and xs[i - 1] != '<':
+        return i - 1
+
+    elif xs[i - 1] == '<':
+        return handle_dels(0, i - 1, xs)
+
+def equal(a, b):
+    ia = len(a) - 1
+    ib = len(b) - 1
+
+    while ia >= 0 and ib >= 0:
+        if a[ia] != b[ib]:
+            return False
+        ia = update_index(ia, a)
+        ib = update_index(ib, b)
+
+    if ia != 0:
+        return update_index(ia, a) <= -1
+    if ib != 0:
+        return update_index(ib, b) <= -1
+
+    return True