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, 49 insertions, 0 deletions

diff --git a/users/wpcarro/scratch/facebook/largest-stack.py b/users/wpcarro/scratch/facebook/largest-stack.py
new file mode 100644
index 000000000000..052db44153d4
--- /dev/null
+++ b/users/wpcarro/scratch/facebook/largest-stack.py
@@ -0,0 +1,49 @@
+from stack import Stack, from_list
+from heapq import heapify, heappush, heappop
+from random import shuffle
+
+class MaxStack(Stack):
+    def __init__(self):
+        self.max = Stack()
+        super().__init__()
+
+    def __repr__(self):
+        return super().__repr__()
+
+    def push(self, x):
+        super().push(x)
+        max = self.get_max()
+        if not max:
+            self.max.push(x)
+        else:
+            self.max.push(max if x < max else x)
+
+    def pop(self):
+        self.max.pop()
+        return super().pop()
+
+    def get_max(self):
+        return self.max.peek()
+
+xs = list(range(1, 11))
+shuffle(xs)
+stack = MaxStack()
+for x in xs:
+    stack.push(x)
+
+print(stack)
+result = stack.get_max()
+print(result)
+assert result == 10
+
+popped = stack.pop()
+print("Popped: {}".format(popped))
+print(stack)
+while popped != 10:
+    assert stack.get_max() == 10
+    popped = stack.pop()
+    print("Popped: {}".format(popped))
+    print(stack)
+
+assert stack.get_max() != 10
+print("Success!")