Data Structures in Python

import array

# Fixed-type array (like C arrays)
nums = array.array("i", [10, 20, 30, 40, 50])

nums[0] = 99              # O(1) - direct index access
val = nums[2]             # O(1) - read by index

nums.append(60)           # O(1) amortized
nums.insert(1, 15)        # O(n) - shifts elements right

idx = nums.index(30)      # O(n) - linear search
nums.remove(15)           # O(n) - shifts elements left

sorted_nums = sorted(nums)  # O(n log n)

names = ["Alice", "Bob", "Charlie"]

names.append("Diana")          # O(1) amortized
names.insert(1, "Eve")         # O(n) - shifts elements
names.pop()                    # O(1) - remove last
names.pop(0)                   # O(n) - shifts elements

has = "Bob" in names           # O(n) - linear scan
idx = names.index("Bob")       # O(n) - first occurrence

names.sort()                   # O(n log n) - Timsort
squares = [x * x for x in range(10)]  # O(n) list comprehension

stack: list[int] = []

stack.append(10)        # O(1) - push
stack.append(20)
stack.append(30)

top = stack[-1]         # O(1) - peek -> 30
val = stack.pop()       # O(1) - pop -> 30

# Interview pattern: valid parentheses
def is_valid(s: str) -> bool:
    pairs = {"(": ")", "[": "]", "{": "}"}
    st: list[str] = []
    for c in s:
        if c in pairs:
            st.append(pairs[c])
        elif not st or st.pop() != c:
            return False
    return len(st) == 0

from collections import deque

queue: deque[str] = deque()

queue.append("Task A")      # O(1) - enqueue
queue.append("Task B")
queue.append("Task C")

first = queue[0]            # O(1) - peek front
val = queue.popleft()       # O(1) - dequeue -> "Task A"

# Interview pattern: BFS
def bfs(root):
    q = deque([root])
    while q:
        node = q.popleft()           # O(1)
        print(node.val, end=" ")
        if node.left:  q.append(node.left)
        if node.right: q.append(node.right)

prices = {"apple": 3, "banana": 5}

prices["cherry"] = 2              # O(1) - add
prices["apple"] = 10              # O(1) - update
has = "banana" in prices          # O(1) - key check
del prices["cherry"]              # O(1) - remove

count = prices.get("mango", 0)   # O(1) - safe lookup

# Interview pattern: Two Sum
def two_sum(nums: list[int], target: int) -> list[int]:
    seen: dict[int, int] = {}
    for i, num in enumerate(nums):
        need = target - num
        if need in seen:            # O(1) lookup
            return [seen[need], i]
        seen[num] = i               # O(1) insert
    return []

s = {1, 2, 3, 4, 5}

s.add(6)                # O(1)
s.discard(1)            # O(1) - no error if missing
has = 4 in s            # O(1) -> True

# Set operations
other = {4, 5, 6, 7}
s & other               # intersection -> {4, 5, 6}
s | other               # union
s - other               # difference

# Interview pattern: contains duplicate
def contains_duplicate(nums: list[int]) -> bool:
    return len(nums) != len(set(nums))

from collections import deque

# deque is a doubly-linked list under the hood
dll: deque[int] = deque()

dll.append(10)          # O(1) - add right
dll.appendleft(5)       # O(1) - add left
dll.pop()               # O(1) - remove right
dll.popleft()           # O(1) - remove left

# Interview pattern: reverse a linked list
class ListNode:
    def __init__(self, val=0, next=None):
        self.val, self.next = val, next

def reverse(head: ListNode | None) -> ListNode | None:
    prev, curr = None, head
    while curr:
        curr.next, prev, curr = prev, curr, curr.next
    return prev

# pip install sortedcontainers
from sortedcontainers import SortedList

sl = SortedList([5, 3, 8, 1, 9])
# Maintains sorted order: [1, 3, 5, 8, 9]

sl.add(4)                    # O(log n)
sl.discard(3)                # O(log n)

minimum = sl[0]              # O(1) -> 1
maximum = sl[-1]             # O(1) -> 9

# Range query
left = sl.bisect_left(4)    # O(log n)
right = sl.bisect_right(8)  # O(log n)
between = list(sl[left:right])  # [4, 5, 8]

# pip install sortedcontainers
from sortedcontainers import SortedDict

sd = SortedDict({"banana": 2, "apple": 5, "cherry": 1})

sd["date"] = 3              # O(log n)
val = sd["apple"]           # O(log n) -> 5
del sd["cherry"]            # O(log n)

# Iterates in sorted key order
for key, value in sd.items():
    print(f"{key}: {value}")
# apple: 5, banana: 2, date: 3

first_key = sd.keys()[0]    # O(1) -> "apple"
last_key = sd.keys()[-1]    # O(1) -> "date"

import heapq

heap: list[int] = []

heapq.heappush(heap, 3)       # O(log n)
heapq.heappush(heap, 1)
heapq.heappush(heap, 2)

top = heap[0]                  # O(1) - peek min -> 1
val = heapq.heappop(heap)     # O(log n) - pop min -> 1

# Max-heap: negate values
max_heap: list[int] = []
heapq.heappush(max_heap, -10)
largest = -heapq.heappop(max_heap)  # -> 10

# Interview pattern: K closest points
def k_closest(points, k):
    heap = [(x*x + y*y, [x, y]) for x, y in points]
    heapq.heapify(heap)            # O(n)
    return [heapq.heappop(heap)[1] for _ in range(k)]

import threading

class ThreadSafeDict:
    def __init__(self):
        self._data: dict = {}
        self._lock = threading.Lock()

    def get(self, key, default=None):
        with self._lock:
            return self._data.get(key, default)

    def set(self, key, value):
        with self._lock:
            self._data[key] = value

    def get_or_add(self, key, factory):
        with self._lock:
            if key not in self._data:
                self._data[key] = factory(key)
            return self._data[key]

cache = ThreadSafeDict()
cache.set("counter", 0)

# memoryview - zero-copy view over bytes/bytearray
data = bytearray(b"Hello, World!")
view = memoryview(data)

# Zero-copy slicing
chunk = view[7:12]            # O(1) - view of "World"
chunk[0] = ord("E")          # mutates original
print(data)                   # bytearray(b"Hello, Eorld!")

# Efficient binary parsing
header = view[:5]             # O(1) - no copy
body = view[7:]               # O(1) - no copy

view.release()                # free the buffer lock