Python Full-Stack Interview Questions 86–90 (Classic Algorithms III & Python Implementations)

Hello! This lesson focuses on more classic coding problems and one very important conceptual question. We'll start with some common utility functions (character counting, list flattening) that test your knowledge of data structures. Then, we'll tackle two famous brain-teasers: implementing a stack with queues, and a queue with stacks. Finally, we'll zoom out to discuss what "Python" itself actually is, by comparing its different implementations.

86. Write a Python program to count character frequency in a string.

This is a very common warm-up question. The goal is to return a data structure that maps each character to the number of times it appeared.

Analogy: Imagine you're taking inventory of a box of T-shirts. You pull them out one by one. You have a clipboard (a dictionary) with "Red," "Blue," and "Green." When you see a red shirt, you add a tally mark next to "Red."

We will look at the manual, classic way, and then the fast, "Pythonic" way.

Method 1: Manual Dictionary

def count_frequency_manual(text):
    frequency = {}
    for char in text:
        # Use .get() to provide a default value (0)
        # if the key (char) doesn't exist yet.
        frequency[char] = frequency.get(char, 0) + 1
    return frequency

my_string = "hello world"
print(f"Manual count: {count_frequency_manual(my_string)}")

Expected Output:

Manual count: {'h': 1, 'e': 1, 'l': 3, 'o': 2, ' ': 1, 'w': 1, 'r': 1, 'd': 1}

Method 2: Pythonic (Using `collections.Counter`)

This is the best answer in a real-world scenario, as it's faster, cleaner, and part of the standard library.

from collections import Counter

def count_frequency_counter(text):
    # Counter is a dictionary subclass built for this!
    return Counter(text)

my_string = "hello world"
print(f"Counter count: {count_frequency_counter(my_string)}")

Expected Output:

Counter count: Counter({'l': 3, 'o': 2, 'h': 1, 'e': 1, ' ': 1, 'w': 1, 'r': 1, 'd': 1})

87. Write a Python program to flatten a nested list.

The goal is to take a list that contains other lists (which themselves can contain lists), and "flatten" it into a single, one-dimensional list.

Analogy: You have a set of nested "Matryoshka" dolls. The flattenfunction is a rule: "Open the doll. If there's another doll inside, apply this same rule to it. If it's a piece of candy (a number), put it in the final pile."

Recursion is the most natural way to solve this. A recursive generator is a particularly elegant way to do it in Python.

def flatten_list(nested_list):
    """
    Flattens a nested list using a recursive generator.
    """
    for item in nested_list:
        # Check if the item is a list (or tuple, etc.)
        if isinstance(item, (list, tuple)):
            # If it is, yield all items from a
            # recursive call to this function.
            yield from flatten_list(item)
        else:
            # If it's not a list, just yield the item.
            yield item

# --- Usage ---
my_nested_list = [1, [2, 3], 4, [5, [6, 7]], 8]
print(f"Nested: {my_nested_list}")

# The generator returns an 'iterator', so we
# cast it to a 'list' to see the full result.
flattened = list(flatten_list(my_nested_list))
print(f"Flattened: {flattened}")

Expected Output:

Nested: [1, [2, 3], 4, [5, [6, 7]], 8]
Flattened: [1, 2, 3, 4, 5, 6, 7, 8]

88. Write a Python program to implement a stack using queues.

This is a classic data structure brain-teaser.

The goal is to make a queue (lunch line) behave like a stack (pile of plates). We can do this with one or two queues. The "costly push" method using two queues is often easiest to understand.

Analogy (Costly Push):You have your main line `q1`and a temporary line `q2` .

from collections import deque

class StackUsingQueues:
    def __init__(self):
        # We'll use Python's deque as our queue
        self.q1 = deque()
        self.q2 = deque()
        
    def push(self, x):
        """
        Puts new element 'x' at the 'top' of the stack.
        This is the 'costly' operation.
        """
        # 1. Add new element to the empty q2
        self.q2.append(x)
        
        # 2. Move all elements from q1 to q2
        while self.q1:
            self.q2.append(self.q1.popleft())
            
        # 3. Swap the names of q1 and q2
        self.q1, self.q2 = self.q2, self.q1
        
    def pop(self):
        """Removes and returns the 'top' element."""
        if self.is_empty():
            return None
        return self.q1.popleft()
        
    def top(self):
        """Returns the 'top' element without removing."""
        if self.is_empty():
            return None
        return self.q1[0] # [0] is the 'left' side
        
    def is_empty(self):
        return len(self.q1) == 0

# --- Usage ---
s = StackUsingQueues()
print("Push 1")
s.push(1)
print("Push 2")
s.push(2)
print("Push 3")
s.push(3)

print(f"Top: {s.top()}")
print(f"Pop: {s.pop()}")
print(f"Top: {s.top()}")
print(f"Pop: {s.pop()}")
print(f"Top: {s.top()}")
print(f"Pop: {s.pop()}")
print(f"Empty: {s.is_empty()}")

Expected Output:

Push 1
Push 2
Push 3
Top: 3
Pop: 3
Top: 2
Pop: 2
Top: 1
Pop: 1
Empty: True

89. Write a Python program to implement a queue using stacks.

This is the reverse problem. We need to make two stacks (piles of plates) behave like a queue (a lunch line).

This has a very clever and efficient solution that leads to "amortized" O(1) time.

Analogy: You have two piles of plates:

The Rules:

This is "amortized O(1)" because the slow O(n) step only happens occasionally. Most of the time, `pop` is fast.

class QueueUsingStacks:
    def __init__(self):
        # We'll use lists as our stacks
        self.s1_inbox = []
        self.s2_outbox = []

    def push(self, x):
        """Adds element 'x' to the back of the queue."""
        self.s1_inbox.append(x)
        
    def _transfer(self):
        """Moves items from inbox to outbox."""
        if not self.s2_outbox:
            while self.s1_inbox:
                self.s2_outbox.append(self.s1_inbox.pop())
                
    def pop(self):
        """Removes and returns the front element."""
        # Ensure the outbox is ready
        self._transfer()
        
        if not self.s2_outbox:
            return None # Queue is empty
        return self.s2_outbox.pop()
        
    def peek(self):
        """Returns the front element without removing."""
        # Ensure the outbox is ready
        self._transfer()
        
        if not self.s2_outbox:
            return None
        return self.s2_outbox[-1] # [-1] is the 'top'
        
    def is_empty(self):
        return not self.s1_inbox and not self.s2_outbox

# --- Usage ---
q = QueueUsingStacks()
print("Push 1")
q.push(1)
print("Push 2")
q.push(2)
print("Push 3")
q.push(3)

print(f"Peek: {q.peek()}") # 1. _transfer() runs here
print(f"Pop: {q.pop()}")   # 1
print(f"Peek: {q.peek()}") # 2
print("Push 4")
q.push(4)
print(f"Pop: {q.pop()}")   # 2
print(f"Pop: {q.pop()}")   # 3
print(f"Pop: {q.pop()}")   # 4
print(f"Empty: {q.is_empty()}")

Expected Output:

Push 1
Push 2
Push 3
Peek: 1
Pop: 1
Peek: 2
Push 4
Pop: 2
Pop: 3
Pop: 4
Empty: True

90. What is the difference between CPython, PyPy, Jython, and other Python implementations? When would you choose one over another?

This is a fantastic conceptual question. The first step is to understand that "Python" is just a specification— a blueprint that defines the language's rules and syntax.

The implementationsare the actual engines built from that blueprint.

Analogy: "USB-C" is a specification. The cableyou buy from Apple, Samsung, or another brand is theimplementation . They all follow the same rules, but they are built differently.

The Implementations:

When would you choose one?

- Choose CPython (99% of the time):This is the default. If you need libraries like Pandas, Django, Flask, or NumPy, you use CPython.

- Choose PyPy:When you have a long-running, pure Python server or script that is CPU-bound (e.g., complex math, string processing) and you have profiled it and know that Python code (not C extensions) is the bottleneck.

- Choose Jython or IronPython:Only when your primary business requirement is to integrate deeply with an existing, large Java or .NET codebase.