What is the amortized time complexity per operation for append() and pop() at the right end of a Python list?
Python lists over-allocate capacity when growing, guaranteeing amortized O(1) time complexity for append() and pop() at the end.
Consider a stack S and queue Q. S is populated with [1, 2, 3, 4, 5] (5 at top). All elements are popped from S and enqueued into Q. Then all elements are dequeued from Q and pushed into S. What element is now at the top of S?
S pop sequence: 5, 4, 3, 2, 1. Q enqueue order: 5, 4, 3, 2, 1. Q dequeue order: 5, 4, 3, 2, 1. S push order: 5, 4, 3, 2, 1 (top becomes 1).
Which traversal method of an expression tree corresponds to the POSTFIX form of the underlying mathematical expression?
Postorder traversal (Left, Right, Root) of an expression tree produces the exact Postfix notation of the expression.
What is the output of the following stack simulation in Python?
stack = []
for x in [5, 10, 15]:
stack.append(x)
stack.append(x * 2)
stack.pop()
print(stack[-1])Iter 1 (5): push 5, push 10, pop 10 -> stack=[5]. Iter 2 (10): push 10, push 20, pop 20 -> stack=[5, 10]. Iter 3 (15): push 15, push 30, pop 30 -> stack=[5, 10, 15]. Top stack[-1] is 15.
What is the postfix form of the infix expression (A + B) * C?
Parentheses force (A + B) to be converted first -> A B +. Multiplying by C yields A B + C *.