Katkat
Back

Explain Stack Use Cases and Mutability in Python Containers

J.P. MorganSoftware Engineer II · Onsite
MediumSoftware Engineer IIOnsiteSoftware Engineering Fundamentals

Last updated

This problem tests the understanding of LIFO data structure applications, the implications of object mutability in Python, and the technical constraints imposed by hashability in container types.

Part 1: Stack Implementation

Describe a real-world scenario where a Last-In-First-Out (LIFO) stack is the most efficient data structure to use. Explain how the time complexity of the stack's push and pop operations relates to the memory management of that scenario.

Part 2: Mutation, Rebinding, and Identity

Consider the following Python code:

a = [1, 2, 3]
b = a
c = [1, 2, 3]

a.append(4)
b = [5, 6]
  1. What are the values of a, b, and c after execution?
  2. Explain the difference between mutation and rebinding in this context.
  3. How do the is operator and the == operator differ when comparing a and c?

Part 3: The Tuple-List Paradox

In Python, a tuple is defined as an immutable sequence. However, if you attempt to use a tuple containing a mutable object (e.g., my_tuple = (1, 2, [3, 4])) as a key in a dictionary, Python raises a TypeError: unhashable type: 'list'. Explain why this behavior exists even though the tuple itself cannot be resized or reassigned.

Hints

Hint 1

Think about how call stacks or undo-redo functionality in text editors leverage the LIFO property to maintain state history.

Hint 2

Remember that `is` checks for object identity (memory address) while `==` checks for value equality.

Hint 3

Consider that a dictionary key's hash value must remain constant throughout the object's lifetime to ensure reliable lookups.

Follow-up questions

  • If you were to implement a custom stack class in Python, would you use a list or a collections.deque? Why?
  • How does the behavior of deep copy differ from shallow copy when dealing with nested mutable objects?
  • Can you think of a scenario where you might intentionally want to use aliasing, and what are the risks associated with it?