about summary refs log tree commit diff
path: root/users/wpcarro/scratch/facebook/largest-stack.py
diff options
context:
space:
mode:
Diffstat (limited to 'users/wpcarro/scratch/facebook/largest-stack.py')
-rw-r--r--users/wpcarro/scratch/facebook/largest-stack.py49
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!")