Python Data Structures and Algorithms: Essential Interview Guide

Data structures and algorithms are the foundation of technical interviews at top tech companies. Python's clean syntax makes it an excellent language for implementing and explaining these concepts. This guide covers the essentials with Python implementations and interview context.

Big O Notation

Big O describes how an algorithm's time or space requirements grow relative to input size.

Notation	Name	Example
O(1)	Constant	Dictionary lookup
O(log n)	Logarithmic	Binary search
O(n)	Linear	Linear search
O(n log n)	Linearithmic	Merge sort
O(n²)	Quadratic	Bubble sort
O(2ⁿ)	Exponential	Fibonacci (naive)

Always analyse best case, average case, and worst case separately. Interviewers usually care about worst case.

Arrays and Lists

Python lists are dynamic arrays — contiguous memory, O(1) random access, O(n) insert/delete in the middle.

python
# Common operations
nums = [3, 1, 4, 1, 5, 9, 2, 6]

nums.append(7)          # O(1) amortized
nums.insert(0, 0)       # O(n) -- shifts elements
nums.pop()              # O(1) -- remove last
nums.pop(0)             # O(n) -- shifts elements
nums[2]                 # O(1) -- random access
nums[1:4]               # O(k) -- slice of length k

# Two-pointer pattern
def two_sum_sorted(arr, target):
    left, right = 0, len(arr) - 1
    while left < right:
        current = arr[left] + arr[right]
        if current == target:
            return [left, right]
        elif current < target:
            left += 1
        else:
            right -= 1
    return []

# Sliding window
def max_sum_subarray(arr, k):
    window_sum = sum(arr[:k])
    max_sum = window_sum
    for i in range(k, len(arr)):
        window_sum += arr[i] - arr[i - k]
        max_sum = max(max_sum, window_sum)
    return max_sum

Hash Maps (Dictionaries)

Python dicts are hash maps — O(1) average for get, set, and delete.

python
# Frequency counter pattern
def top_k_frequent(nums, k):
    count = {}
    for n in nums:
        count[n] = count.get(n, 0) + 1
    # Sort by frequency descending, take top k keys
    return sorted(count, key=count.get, reverse=True)[:k]

# Two Sum (classic)
def two_sum(nums, target):
    seen = {}  # value -> index
    for i, n in enumerate(nums):
        complement = target - n
        if complement in seen:
            return [seen[complement], i]
        seen[n] = i
    return []

# Group anagrams
def group_anagrams(strs):
    groups = {}
    for s in strs:
        key = tuple(sorted(s))
        groups.setdefault(key, []).append(s)
    return list(groups.values())

Stack

LIFO structure. Python list as a stack:

python
stack = []
stack.append(1)  # push
stack.append(2)
stack.append(3)
stack.pop()      # 3 -- pop
stack[-1]        # 2 -- peek

# Valid parentheses
def is_valid(s):
    stack = []
    pairs = {")": "(", "}": "{", "]": "["}
    for char in s:
        if char in "({[":
            stack.append(char)
        elif char in ")}]":
            if not stack or stack[-1] != pairs[char]:
                return False
            stack.pop()
    return len(stack) == 0

# Monotonic stack -- next greater element
def next_greater(nums):
    result = [-1] * len(nums)
    stack = []  # stores indices
    for i, n in enumerate(nums):
        while stack and nums[stack[-1]] < n:
            result[stack.pop()] = n
        stack.append(i)
    return result

Queue and Deque

FIFO structure. Use collections.deque for O(1) operations on both ends:

python
from collections import deque

queue = deque()
queue.append(1)       # enqueue right
queue.append(2)
queue.popleft()       # dequeue left -- O(1)

# BFS using a queue
def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)
    result = []

    while queue:
        node = queue.popleft()
        result.append(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return result

Linked List

python
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# Reverse a linked list -- iterative
def reverse_list(head):
    prev = None
    curr = head
    while curr:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    return prev

# Detect cycle -- Floyd's algorithm
def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

# Merge two sorted lists
def merge_sorted(l1, l2):
    dummy = ListNode(0)
    curr = dummy
    while l1 and l2:
        if l1.val <= l2.val:
            curr.next = l1
            l1 = l1.next
        else:
            curr.next = l2
            l2 = l2.next
        curr = curr.next
    curr.next = l1 or l2
    return dummy.next

Binary Tree

python
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# Inorder traversal (left, root, right)
def inorder(root):
    if not root:
        return []
    return inorder(root.left) + [root.val] + inorder(root.right)

# Max depth
def max_depth(root):
    if not root:
        return 0
    return 1 + max(max_depth(root.left), max_depth(root.right))

# Level order traversal (BFS)
def level_order(root):
    if not root:
        return []
    result, queue = [], deque([root])
    while queue:
        level = []
        for _ in range(len(queue)):
            node = queue.popleft()
            level.append(node.val)
            if node.left:  queue.append(node.left)
            if node.right: queue.append(node.right)
        result.append(level)
    return result

# Validate BST
def is_valid_bst(root, min_val=float('-inf'), max_val=float('inf')):
    if not root:
        return True
    if not (min_val < root.val < max_val):
        return False
    return (is_valid_bst(root.left, min_val, root.val) and
            is_valid_bst(root.right, root.val, max_val))

Sorting Algorithms

python
# Merge sort -- O(n log n), stable
def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i]); i += 1
        else:
            result.append(right[j]); j += 1
    return result + left[i:] + right[j:]

# Quick sort -- O(n log n) average, O(n²) worst
def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left   = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right  = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

Binary Search

python
# Standard binary search -- O(log n)
def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = left + (right - left) // 2  # avoids overflow
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

# Search in rotated sorted array
def search_rotated(nums, target):
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        if nums[left] <= nums[mid]:  # left half sorted
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:  # right half sorted
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1
    return -1

Dynamic Programming

Break problems into overlapping subproblems, cache results:

python
# Fibonacci with memoization
from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n < 2: return n
    return fib(n - 1) + fib(n - 2)

# Longest Common Subsequence
def lcs(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return dp[m][n]

# 0/1 Knapsack
def knapsack(weights, values, capacity):
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for w in range(capacity + 1):
            dp[i][w] = dp[i-1][w]
            if weights[i-1] <= w:
                dp[i][w] = max(dp[i][w], dp[i-1][w - weights[i-1]] + values[i-1])
    return dp[n][capacity]

Practice Algorithms on Froquiz

Data structures and algorithm fundamentals are the backbone of technical interviews. Test your Python knowledge on Froquiz — we cover data structures, OOP, and core Python concepts across all difficulty levels.

Summary

• Know your Big O — interviewers always ask about time and space complexity
• Arrays: two-pointer and sliding window solve most sequence problems
• Hash maps: frequency counting, two-sum, grouping — O(1) lookup changes everything
• Stack: parentheses matching, monotonic stack for next-greater problems
• Queue/deque: BFS, level-order traversal
• Linked lists: reversal, cycle detection (Floyd's), merge patterns
• Trees: recursion for DFS, deque for BFS/level-order
• Binary search: not just for sorted arrays — works on any monotonic condition
• Dynamic programming: identify overlapping subproblems, cache with @lru_cache or a table