Python Data Structures Interview Questions — Lists, Dicts, Sets & More

# Demonstrating WHY tuples can be dict keys and lists cannot

# A tuple can represent a fixed geographic coordinate
office_location = (51.5074, -0.1278)  # latitude, longitude of London

# Tuples are hashable, so they work as dictionary keys
location_names = {
    (51.5074, -0.1278): "London HQ",
    (40.7128, -74.0060): "New York Office",
    (35.6762, 139.6503): "Tokyo Branch",
}

print(location_names[office_location])  # Works perfectly

# Now try the same with a list — this will blow up
try:
    bad_key = [51.5074, -0.1278]  # a list version of the same coords
    bad_dict = {bad_key: "This will never work"}
except TypeError as error:
    print(f"TypeError caught: {error}")

# Demonstrating amortised O(1) append vs O(n) insert at front
import time

request_queue = []

# Appending 100,000 items — fast, O(1) amortised each
start = time.perf_counter()
for request_id in range(100_000):
    request_queue.append(request_id)  # adds to the END — cheap
append_time = time.perf_counter() - start

# Inserting at position 0 — slow, O(n) each time
front_insert_queue = []
start = time.perf_counter()
for request_id in range(10_000):  # only 10k — already slower
    front_insert_queue.insert(0, request_id)  # shifts EVERY element right
insert_time = time.perf_counter() - start

print(f"100k appends:       {append_time:.4f}s")
print(f" 10k front-inserts: {insert_time:.4f}s")  # notice 10x fewer items, yet slower
print("Use collections.deque if you need fast front insertion!")

from collections import defaultdict, Counter

# ── EXAMPLE 1: O(1) lookup power ──────────────────────────────────────────
# Imagine checking if a username is taken
taken_usernames = {"alice", "bob", "carol", "dave"}  # a set — no values needed

print("'alice' taken?", "alice" in taken_usernames)   # O(1) — hash jump
print("'zara' taken?",  "zara"  in taken_usernames)   # O(1) — hash jump

# Compare: same check with a list is O(n) — scans every element
taken_list = ["alice", "bob", "carol", "dave"]
print("'alice' in list?", "alice" in taken_list)  # works, but slower at scale

# ── EXAMPLE 2: defaultdict removes the 'key exists?' dance ────────────────
# Counting word frequency the old way (lots of boilerplate)
sentence = "the cat sat on the mat and the cat sat"
word_frequency_old = {}
for word in sentence.split():
    if word in word_frequency_old:          # have to check first
        word_frequency_old[word] += 1
    else:
        word_frequency_old[word] = 1        # initialise manually

# The clean way with defaultdict
word_frequency = defaultdict(int)           # int() returns 0 — perfect default
for word in sentence.split():
    word_frequency[word] += 1              # no existence check needed

print("\nWord frequencies:", dict(word_frequency))

# ── EXAMPLE 3: Counter — the specialised frequency dict ──────────────────
votes = ["alice", "bob", "alice", "carol", "alice", "bob"]
vote_tally = Counter(votes)                 # built for exactly this use case

print("\nVote tally:", vote_tally)
print("Top candidate:", vote_tally.most_common(1))  # returns [(name, count)]

# ── EXAMPLE 4: Set operations — the interview favourite ──────────────────
premium_users  = {"alice", "carol", "eve"}
active_users   = {"alice", "bob", "carol", "dave"}

print("\nPremium AND active:",  premium_users & active_users)   # intersection
print("Premium OR  active:",  premium_users | active_users)   # union
print("Premium NOT active:",  premium_users - active_users)   # difference
print("Active  NOT premium:", active_users  - premium_users)  # difference (flipped)

from collections import deque
import heapq

# ── STACK (LIFO) — use a plain list ───────────────────────────────────────
# Real-world: undo history in a text editor
undo_history = []                            # empty stack
undo_history.append("typed 'Hello'")
undo_history.append("typed ' World'")
undo_history.append("deleted last word")

print("Undo stack:", undo_history)
last_action = undo_history.pop()             # O(1) — removes from end
print("Undoing:", last_action)
print("Stack after undo:", undo_history)

# ── QUEUE (FIFO) — use deque, NOT a list ──────────────────────────────────
# Real-world: print job queue — first submitted, first printed
print_queue = deque()
print_queue.append("Report.pdf")             # appendright — O(1)
print_queue.append("Invoice.pdf")
print_queue.append("Resume.pdf")

print("\nPrint queue:", print_queue)
next_job = print_queue.popleft()             # O(1) — removes from front
print("Now printing:", next_job)
print("Remaining queue:", print_queue)

# ── PRIORITY QUEUE — use heapq ────────────────────────────────────────────
# Real-world: support ticket system — severity 1 is most urgent
# heapq is a MIN-heap: smallest value pops first
support_tickets = []

# Each tuple: (priority, ticket_id, description)
# Tuple comparison checks first element first — so priority drives ordering
heapq.heappush(support_tickets, (3, 101, "Slow page load"))
heapq.heappush(support_tickets, (1, 102, "Site is DOWN — all users affected"))
heapq.heappush(support_tickets, (2, 103, "Login button misaligned"))
heapq.heappush(support_tickets, (1, 104, "Payment processing failing"))

print("\nProcessing tickets by priority:")
while support_tickets:
    priority, ticket_id, description = heapq.heappop(support_tickets)  # always pops min
    print(f"  Priority {priority} | #{ticket_id}: {description}")

import sys

# ── List comprehension: builds everything in memory immediately ────────────
# Imagine fetching all user IDs from a large database table
all_user_ids = range(1, 1_000_001)           # pretend these come from a DB

# List comprehension — every filtered ID sits in RAM right now
active_users_list = [uid for uid in all_user_ids if uid % 2 == 0]  # even IDs only

print(f"List size in memory: {sys.getsizeof(active_users_list):,} bytes")

# ── Generator expression: computes lazily, one item at a time ─────────────
# Same filter, but items are generated only when consumed
active_users_gen = (uid for uid in all_user_ids if uid % 2 == 0)

print(f"Generator size in memory: {sys.getsizeof(active_users_gen):,} bytes")
print("(The generator object is tiny — the data isn't loaded yet)")

# ── When you NEED a list comprehension (multiple passes, indexing) ─────────
temperature_readings = [22.5, 19.0, 30.1, 17.8, 25.3, 28.6]

# We need to compute average THEN filter — two passes over the data
average_temp = sum(temperature_readings) / len(temperature_readings)
hot_days = [temp for temp in temperature_readings if temp > average_temp]

print(f"\nAverage temperature: {average_temp:.1f}°C")
print(f"Above-average days:  {hot_days}")

# ── Nested comprehension — common interview question ──────────────────────
# Flatten a 2D grid of sensor readings into a single list
sensor_grid = [
    [12, 15, 11],   # row 0: building floor 1
    [18, 22, 19],   # row 1: building floor 2
    [9,  13, 10],   # row 2: building floor 3
]

# Read: "give me each reading, for each row, for each reading in that row"
all_readings = [reading for row in sensor_grid for reading in row]
print(f"\nAll sensor readings: {all_readings}")
print(f"Max reading: {max(all_readings)}, Min reading: {min(all_readings)}")