Loading…
Welcome! This lesson is a fantastic mix of the high-level and the hands-on, which is very common in interviews. We'll start with a high-level system design question about building fast, reliable services. Then, we'll dive into four classic, hands-on coding problemsthat test your algorithm and data structure knowledge. Take a calm breath; these are all building blocks, and we'll go through them one by one.
This is a big-picture question about building systems that don't crash under heavy traffic and can handle failures gracefully. The goal is to avoid having a single point of failure.
Analogy: Think of a single, very popular food truck.
Here’s how the key concepts work together to support this:
Tip: In an interview, you don't need to know every tool. Just explain these three concepts: a load balancerdistributing traffic to multiple stateless servers , all of which are protected by a caching layer .
A palindrome is a string that reads the same forwards and backwards (e.g., "racecar", "madam").
The simplest, most "Pythonic" way uses slicing, but it's often considered a "trick." Interviewers usually prefer to see the two-pointer algorithm , as it proves you understand the logic.
A good interview will also include a follow-up: "How would you handle case, punctuation, and spaces?" We will build a function that handles that.
def is_palindrome_simple(s: str) -> bool:
"""Checks for a palindrome using slicing."""
return s == s[::-1]
def is_palindrome_robust(s: str) -> bool:
"""
Checks for a palindrome using the two-pointer algorithm,
while ignoring case and non-alphanumeric characters.
"""
# 1. Clean the string
# 'isalnum()' checks for letters or numbers
cleaned = [char for char in s.lower() if char.isalnum()]
# 2. Use the two-pointer algorithm
left = 0
right = len(cleaned) - 1
while left < right:
if cleaned[left] != cleaned[right]:
return False
left += 1
right -= 1
return True
# --- Usage ---
s1 = "racecar"
s2 = "A man, a plan, a canal: Panama"
s3 = "hello"
print(f"'{s1}' (simple): {is_palindrome_simple(s1)}")
print(f"'{s1}' (robust): {is_palindrome_robust(s1)}")
print("---")
print(f"'{s2}' (robust): {is_palindrome_robust(s2)}")
print("---")
print(f"'{s3}' (simple): {is_palindrome_simple(s3)}")
print(f"'{s3}' (robust): {is_palindrome_robust(s3)}")
Expected Output:
'racecar' (simple): True
'racecar' (robust): True
---
'A man, a plan, a canal: Panama' (robust): True
---
'hello' (simple): False
'hello' (robust): False
This is a fundamental data structure problem. You are given the`head` of a linked list, and you need to reverse the `next`pointers so the list points in the opposite direction.
The key is the iterative, three-pointer approach. You need to keep track of three nodes as you walk the list:
In each loop step, you point `curr.next`to `prev` , and then move all three pointers one step forward.
# First, define the ListNode
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# Helper function to print a linked list
def print_list(head: ListNode | None):
if not head:
print("None")
return
curr = head
result = []
while curr:
result.append(str(curr.val))
curr = curr.next
print(" -> ".join(result))
def reverse_list(head: ListNode | None) -> ListNode | None:
"""Reverses a linked list iteratively."""
prev = None
curr = head
while curr:
# 1. Store the next node before we break the link
next_temp = curr.next
# 2. Reverse the actual pointer
curr.next = prev
# 3. Move all pointers one step forward
prev = curr
curr = next_temp
# At the end, 'curr' is None, and 'prev' is the new head
return prev
# --- Usage ---
# Create a list: 1 -> 2 -> 3 -> 4
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)
print("Original list:")
print_list(head)
# Reverse the list
new_head = reverse_list(head)
print("\nReversed list:")
print_list(new_head)
Expected Output:
Original list:
1 -> 2 -> 3 -> 4
Reversed list:
4 -> 3 -> 2 -> 1
This is a classic "hard" interview question. "LRU" stands for Least Recently Used . The goal is to build a cache of a fixed `capacity`that evicts the least recently useditem when it's full.
The challenge is that both `get`(retrieving an item) and `put`(adding/updating an item) must be O(1) -constant time.
This requires two data structures working together:
When we `get` or `put`an item, we move it to the front of the list. When we need to evict, we just pop the item from the tail.
# We need a Doubly Linked List node
class DLinkedNode:
def __init__(self, key=0, val=0):
self.key = key
self.val = val
self.prev = None
self.next = None
class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.size = 0
self.cache = {} # The hash map
# Dummy head and tail nodes
self.head = DLinkedNode()
self.tail = DLinkedNode()
self.head.next = self.tail
self.tail.prev = self.head
# --- Internal helper methods ---
def _add_node(self, node: DLinkedNode):
"""Adds a new node right after the head."""
node.prev = self.head
node.next = self.head.next
self.head.next.prev = node
self.head.next = node
def _remove_node(self, node: DLinkedNode):
"""Removes an existing node from the list."""
prev_node = node.prev
next_node = node.next
prev_node.next = next_node
next_node.prev = prev_node
def _move_to_front(self, node: DLinkedNode):
"""Moves a node to the front (used on 'get')."""
self._remove_node(node)
self._add_node(node)
def _pop_tail(self) -> DLinkedNode:
"""Pops the least recently used item (before tail)."""
node = self.tail.prev
self._remove_node(node)
return node
# --- Public API methods ---
def get(self, key: int) -> int:
node = self.cache.get(key)
if not node:
return -1
# This item is now 'most recently used'
self._move_to_front(node)
return node.val
def put(self, key: int, value: int) -> None:
node = self.cache.get(key)
if node:
# Update existing key
node.val = value
self._move_to_front(node)
else:
# Add new key
new_node = DLinkedNode(key, value)
self.cache[key] = new_node
self._add_node(new_node)
self.size += 1
if self.size > self.capacity:
# Evict the LRU item
tail = self._pop_tail()
del self.cache[tail.key]
self.size -= 1
# --- Usage ---
cache = LRUCache(2)
cache.put(1, 1) # Cache is {1: 1}
print("Put(1, 1)")
cache.put(2, 2) # Cache is {1: 1, 2: 2}
print("Put(2, 2)")
print(f"Get(1): {cache.get(1)}") # Returns 1, {2: 2, 1: 1}
cache.put(3, 3) # LRU key 2 was evicted. Cache is {1: 1, 3: 3}
print("Put(3, 3)")
print(f"Get(2): {cache.get(2)}") # Returns -1 (not found)
cache.put(4, 4) # LRU key 1 was evicted. Cache is {3: 3, 4: 4}
print("Put(4, 4)")
print(f"Get(1): {cache.get(1)}") # Returns -1 (not found)
print(f"Get(3): {cache.get(3)}") # Returns 3, {4: 4, 3: 3}
print(f"Get(4): {cache.get(4)}") # Returns 4, {3: 3, 4: 4}
Expected Output:
Put(1, 1)
Put(2, 2)
Get(1): 1
Put(3, 3)
Get(2): -1
Put(4, 4)
Get(1): -1
Get(3): 3
Get(4): 4
This is a classic problem that is the foundation of "Merge Sort." You are given two lists (or linked lists) that are already sorted , and you need to combine them into a single sorted list.
We'll show the solution for Linked Lists , as it's the most common way this is asked. The logic is the same for regular Python lists.
The key is to create a dummy head nodefor our new list. Then, we use two pointers, `l1`and `l2` , to walk the input lists. We compare the values, append the smallernode to our new list, and advance the pointer for that list.
# Define the ListNode again for this self-contained example
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# Helper function to print a linked list
def print_list(head: ListNode | None):
if not head:
print("None")
return
curr = head
result = []
while curr:
result.append(str(curr.val))
curr = curr.next
print(" -> ".join(result))
def merge_two_lists(l1: ListNode | None, l2: ListNode | None) -> ListNode | None:
# 1. Create a dummy node to build the new list
dummy_head = ListNode()
# 'tail' will be our pointer to the end of the new list
tail = dummy_head
# 2. Loop while both lists have nodes
while l1 and l2:
if l1.val < l2.val:
tail.next = l1
l1 = l1.next
else:
tail.next = l2
l2 = l2.next
# Advance the tail pointer
tail = tail.next
# 3. At least one list is now empty.
# Append the remainder of the other list.
if l1:
tail.next = l1
elif l2:
tail.next = l2
# The new list starts *after* our dummy node
return dummy_head.next
# --- Usage ---
# List 1: 1 -> 2 -> 4
l1 = ListNode(1)
l1.next = ListNode(2)
l1.next.next = ListNode(4)
print("List 1:")
print_list(l1)
# List 2: 1 -> 3 -> 4
l2 = ListNode(1)
l2.next = ListNode(3)
l2.next.next = ListNode(4)
print("\nList 2:")
print_list(l2)
# Merge
merged_head = merge_two_lists(l1, l2)
print("\nMerged List:")
print_list(merged_head)
Expected Output:
List 1:
1 -> 2 -> 4
List 2:
1 -> 3 -> 4
Merged List:
1 -> 1 -> 2 -> 3 -> 4 -> 4
3 questions · no sign-up, nothing stored
Progress is stored in this browser only - no sign-up, nothing sent anywhere.
Step through the algorithms behind these answers one operation at a time, forwards or backwards, with the code highlighted as it runs.
Three pointers, and the reason the order of those four lines matters.
Step through get and put, and watch the eviction happen at the tail.
Merging two sorted lists is the inner step of merge sort - watch the two-finger walk.
The technique behind the palindrome check, generalised.
The same topic at architecture level, in the system design curriculum.