Python coding and DSA basics

Average lookup is O(1) because dict uses an open-addressing hash table. Worst case is O(n) when many keys collide into the same probe sequence (e.g., adversarial keys with identical hashes), degrading to a linear scan. In practice CPython's SipHash with a randomized seed (PYTHONHASHSEED) makes collision attacks on str/bytes keys impractical, so the worst case is rare for typical data.

list.pop(0) is O(n) because every remaining element must be shifted left. collections.deque provides O(1) appends and pops from both ends, making it the correct FIFO/queue structure. Use deque.popleft() for the head.

from collections import deque
q = deque([1,2,3])
q.append(4)
q.popleft()  # O(1)

It illustrates late binding: each lambda closes over the variable i (a cell), not its value at creation time. i is looked up only when the lambda is called, and by then the loop has finished with i == 2, so all three functions return 2, printing [2, 2, 2]. The fix is to bind the current value, e.g. lambda i=i: i.

fns = [lambda: i for i in range(3)]
print([f() for f in fns])

For a list, 'in' is O(n) (linear scan); for a set, it is O(1) average (hash lookup). When filtering large feature/ID collections, converting the lookup collection to a set turns an O(n*m) operation into O(n+m), a major speedup.

A shallow copy (copy.copy or list[:]) copies the outer container but the inner objects remain shared references, so mutating an inner array affects both. copy.deepcopy recursively duplicates every nested object, so they are fully independent. Deepcopy is slower and uses more memory.

heapq implements a binary min-heap. To get the k largest elements you maintain a min-heap of size k (heappushpop), which is O(n log k) time and O(k) memory, or use heapq.nlargest(k, iterable). For the k smallest, use heapq.nsmallest or a max-heap by negating values.

import heapq
def k_largest(stream, k):
    h = []
    for x in stream:
        if len(h) < k: heapq.heappush(h, x)
        else: heapq.heappushpop(h, x)
    return h

Two pointers run in O(n) time and O(1) extra space by moving inward based on whether the current sum is too large or small. Brute force is O(n^2). It requires the array to be sorted (or O(n log n) to sort first).

def pair_sum(a, t):
    i, j = 0, len(a)-1
    while i < j:
        s = a[i]+a[j]
        if s == t: return (i, j)
        if s < t: i += 1
        else: j -= 1
    return None

It prints False because 0.1, 0.2, and 0.3 cannot be represented exactly in IEEE-754 binary floating point, so the sum is 0.30000000000000004. Compare floats with math.isclose() or an explicit tolerance instead of ==.

import math
math.isclose(0.1+0.2, 0.3)  # True

The Global Interpreter Lock lets only one thread execute Python bytecode at a time, so threads do not speed up pure-Python CPU-bound work; use multiprocessing or native libraries (NumPy/PyTorch release the GIL) instead. Threads still help I/O-bound work because the GIL is released during blocking I/O, and asyncio handles I/O concurrency single-threaded. Note: CPython 3.13+ ships an optional free-threaded (no-GIL) build (PEP 703), but the GIL remains the default.

Naive recursion is O(2^n) time due to repeated subproblems. Memoization (caching results) reduces it to O(n) time and O(n) space; an iterative bottom-up version is O(n) time and O(1) space.

from functools import lru_cache
@lru_cache(None)
def fib(n):
    return n if n < 2 else fib(n-1)+fib(n-2)

The default list is created once at function definition and shared across all calls that omit the argument, so it accumulates state between calls. The fix is to use acc=None and create a new list inside the function. This bug is common in data-processing helpers.

def f(x, acc=None):
    if acc is None: acc = []
    acc.append(x)
    return acc

A sliding window with a hash map tracking the last-seen index of each character solves it in O(n) time and O(min(n, alphabet)) space. The left edge jumps past the last duplicate when a repeat is found.

def length_of_longest(s):
    seen = {}; left = best = 0
    for r, c in enumerate(s):
        if c in seen and seen[c] >= left:
            left = seen[c] + 1
        seen[c] = r
        best = max(best, r-left+1)
    return best

== compares values (via __eq__) while is compares object identity (same object in memory). CPython interns small integers (-5 to 256) and some strings, so identical small ints share one cached object making 'is' True, but large ints typically create distinct objects. Always use == for value comparison; reserve 'is' for None and other singletons.

Python's Timsort is stable: equal elements keep their original relative order. This lets you sort by the secondary key first, then the primary key, to achieve multi-level ordering. Timsort is O(n log n) worst case and adaptive (near O(n) on partially sorted data).

rows.sort(key=lambda r: r.secondary)
rows.sort(key=lambda r: r.primary)  # stable: secondary order preserved

Building the count is O(n) average time and O(k) space (k distinct items). collections.Counter does this idiomatically, and Counter.most_common(1) returns the top item; most_common() without an argument costs O(k log k) to sort, but pulling just the single top element is effectively O(k).

from collections import Counter
c = Counter(items)
top, freq = c.most_common(1)[0]

Generators are lazy: they yield one item at a time so per-step memory stays O(1) regardless of dataset size, ideal for streaming large files. The limitation is they are single-pass (exhaustible) and have no len() or random indexing.

def read_lines(path):
    with open(path) as f:
        for line in f:
            yield line.strip()

Binary search is O(log n) time and O(1) space (iterative). The precondition is that the array is sorted with respect to the comparison key. Python's bisect module provides bisect_left/bisect_right for sorted insertion points.

import bisect
i = bisect.bisect_left(sorted_arr, target)

__str__ returns a human-readable string (used by print/str), while __repr__ returns an unambiguous developer-oriented representation (ideally reconstructable), used by repr(), the REPL, and containers. Debuggers, logging of containers, and Jupyter display fall back to __repr__, so define it for any custom data class.

It prints [1, 2, 3, 4]. b = a makes both names reference the same list object, and += on a list calls in-place extend (__iadd__), mutating the shared object. To avoid this, use b = a + [4] or b = a.copy().

Floyd's tortoise-and-hare algorithm uses two pointers, one moving one step and one moving two steps per iteration. If they ever meet, a cycle exists; if the fast pointer reaches None, there is no cycle. It runs in O(n) time and O(1) space, beating a hash-set approach that uses O(n) space.

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

An instance method receives the instance (self); a classmethod receives the class (cls) and is often used for alternative constructors; a staticmethod receives neither and is just a namespaced plain function. Classmethods enable factory patterns and respect subclassing via cls.

class M:
    @classmethod
    def from_config(cls, cfg): return cls(**cfg)
    @staticmethod
    def util(x): return x*2

A hash map for O(1) key lookup combined with a doubly linked list to maintain usage order and allow O(1) removal/insertion of the most/least recently used node. In Python, collections.OrderedDict (or functools.lru_cache) provides this via move_to_end and popitem(last=False).

from collections import OrderedDict
class LRU:
    def __init__(self, cap):
        self.cap = cap; self.d = OrderedDict()
    def get(self, k):
        if k not in self.d: return -1
        self.d.move_to_end(k); return self.d[k]
    def put(self, k, v):
        if k in self.d: self.d.move_to_end(k)
        self.d[k] = v
        if len(self.d) > self.cap: self.d.popitem(last=False)

return terminates the function and produces a value once; yield suspends the function, producing a value and preserving local state so execution resumes after the yield on the next call. A function containing yield becomes a generator that is lazy and resumable.

Using a min-heap of the current heads gives O(N log k), where N is the total number of elements and k is the number of lists. Concatenating then sorting is O(N log N); since k <= N, the heap method is asymptotically better when k is small relative to N.

import heapq
def merge_k(lists):
    return list(heapq.merge(*lists))  # heap-based, O(N log k)

Empty containers and zero values are falsy: bool([]) is False, bool({}) is False, bool(0.0) is False. But bool('0') is True because any non-empty string is truthy regardless of content. This trips up code that checks string flags.

defaultdict auto-creates a default value for missing keys using a factory (e.g., list, int), avoiding repetitive key-existence checks when grouping or counting. The pitfall is that merely accessing a missing key inserts it, which can silently grow the dict or mask KeyErrors you intended to catch.

from collections import defaultdict
g = defaultdict(list)
for k, v in pairs: g[k].append(v)

Because Python strings are immutable, s += chunk in a loop can be O(n^2) since each concatenation may copy the accumulated string. (CPython has a fragile in-place optimization for this specific pattern, but it is not guaranteed.) The preferred approach is to append chunks to a list and call ''.join(parts), which is O(n) total.

parts = []
for chunk in chunks: parts.append(chunk)
result = ''.join(parts)

BFS finds the shortest path (fewest edges) in an unweighted graph because it explores nodes in order of distance from the source, so the first time a node is reached is via a shortest path. DFS does not guarantee shortest paths. Both are O(V+E); BFS uses a queue, DFS a stack/recursion. For weighted graphs use Dijkstra instead.

from collections import deque
def bfs_dist(adj, src):
    dist = {src: 0}; q = deque([src])
    while q:
        u = q.popleft()
        for v in adj[u]:
            if v not in dist:
                dist[v] = dist[u]+1; q.append(v)
    return dist

enumerate yields (index, item) pairs lazily, letting you track position without a separate counter variable, and start sets the first index. It is cleaner, avoids off-by-one bugs, and works on any iterable including generators where len() is unavailable.

for i, batch in enumerate(loader, start=1):
    ...  # i is the batch number

Both set() and set comprehensions remove duplicates in O(n) average time but do NOT preserve insertion order. To dedupe while preserving first-seen order, use dict.fromkeys(iterable), since dicts are insertion-ordered (guaranteed since Python 3.7).

deduped = list(dict.fromkeys(items))  # order-preserving

Kadane's algorithm runs in O(n) time and O(1) space. It scans once, maintaining the best subarray sum ending at the current index (taking max of the current element vs. extending the running sum) and tracking the global maximum. This is a classic dynamic-programming reduction.

def max_subarray(a):
    cur = best = a[0]
    for x in a[1:]:
        cur = max(x, cur + x)
        best = max(best, cur)
    return best

The walrus operator assigns a value to a variable as part of an expression. It is useful for capturing and testing a value at once, e.g., reading chunks in a while loop or filtering in a comprehension while reusing the computed value, reducing redundant computation.

while (chunk := f.read(8192)):
    process(chunk)

Both are O(n) time, but s[::-1] creates a full reversed copy using O(n) extra space, while the two-pointer approach uses O(1) extra space and can short-circuit on the first mismatch. For large strings or memory-sensitive code, two pointers are preferable.

def is_pal(s):
    i, j = 0, len(s)-1
    while i < j:
        if s[i] != s[j]: return False
        i += 1; j -= 1
    return True

lru_cache requires arguments to be hashable, so unhashable inputs like lists or NumPy arrays raise TypeError. With maxsize=None the cache grows unboundedly, which can leak memory in long-running services; set a bounded maxsize or call cache_clear() periodically.

from functools import lru_cache
@lru_cache(maxsize=1024)
def embed(text: str): ...