Programming Fundamentals Questions

Direct answer
The four core built-in containers split along two axes: mutability (can you change it after creation?) and whether elements need to be ordered/duplicable versus unique/hashable. A list is a mutable ordered sequence, a tuple is an immutable ordered sequence, a set is a mutable unordered collection of unique hashable elements, and a dict is a mutable unordered mapping of unique hashable keys to values.

Structured elaboration

The O(1)-average / O(n)-worst-case split for set/dict comes from hashing: normally a hash lookup goes straight to (approximately) the right bucket, but if many keys collide into the same bucket, resolving the collision degenerates toward a linear scan. list/tuple index access is O(1) because the underlying storage is one contiguous block, computing an offset from the index is arithmetic, not a search; searching a list BY VALUE (x in my_list) is O(n) because there's no shortcut, every element may need to be checked.

Worked example
Hashability is the concrete reason tuples, not lists, can be dict keys or set members: {(1, 2): 'a point'} works because a tuple's contents can't change after creation, so its hash value is stable for its lifetime; {[1, 2]: 'a point'} raises TypeError: unhashable type: 'list' because a list's contents CAN change, so Python refuses to let it serve as a hash key at all (verified: t = (1, 2, 3) then t[0] = 99 raises TypeError: 'tuple' object does not support item assignment; {1, 2, 2, 3} == {1, 2, 3}, confirming a set silently drops the duplicate 2).

Trade-offs & pitfalls
The most common mistake is choosing list by default and doing repeated x in my_list membership checks in a hot path, that's O(n) per check and O(n*m) over m checks; switching to a set for membership-only use cases is one of the cheapest performance wins available. The second is using a mutable default in a spot that implicitly needs hashability (trying to use a list as a dict key, or storing lists inside a set) and hitting a TypeError that a tuple would have avoided entirely.

Direct answer
Plain assignment doesn't copy anything, it just gives a second name to the same object. A shallow copy creates a new outer container but reuses references to the same nested objects inside it, so mutating a nested element through either the original or the shallow copy is visible in both. A deep copy recursively copies every nested object too, giving you a fully independent structure.

Structured elaboration

• Assignment (b = a): a and b are now two names for the exact same object; b is a is True. There is no 'original' versus 'copy', they're the same thing.
• Shallow copy (copy.copy(a), or list(a), or a[:] for a list): creates a genuinely new outer object (b is a is now False), but for every element that is itself a mutable object (a nested list, a dict, a custom object), the copy holds a reference to the SAME nested object, not a copy of it (b[0] is a[0] is True).
• Deep copy (copy.deepcopy(a)): recursively walks the structure and makes a new copy of every nested mutable object too, so nothing is shared (b[0] is a[0] is False).
• The bug shape this causes: code that shallow-copies a nested structure believing it now has an independent snapshot, then mutates the original, and the 'snapshot' silently changes too, because the shallow copy's nested elements were never actually copied.

Worked example

import copy
original = [[1, 2, 3], [4, 5, 6]]
shallow = copy.copy(original)
deep = copy.deepcopy(original)

original[0].append(999)   # mutate a NESTED element of the original

Verified results after that mutation: original == [[1, 2, 3, 999], [4, 5, 6]], shallow == [[1, 2, 3, 999], [4, 5, 6]] (the nested list was shared, so the shallow copy sees the change too), deep == [[1, 2, 3], [4, 5, 6]] (fully independent, unaffected).

A realistic version of this bug: code takes a shallow copy of a dataset as a 'before' snapshot, then runs an in-place normalization pass over the dataset:

def normalize_inplace(rows):
    for row in rows:
        total = sum(row)
        for i in range(len(row)):
            row[i] = row[i] / total if total else 0

After running normalize_inplace on the dataset, the shallow-copied 'snapshot' taken beforehand is bitwise identical to the now-normalized dataset (verified by running it: snapshot == dataset evaluates True after normalization), because normalize_inplace mutates each row list in place, and the shallow copy's rows are the SAME row objects as the original's. The 'backup' was never a backup.

Trade-offs & pitfalls
The fix depends on what you actually need: if you truly need an independent snapshot, use copy.deepcopy (accepting its cost, see the mutability discussion) or rebuild the structure by copying each nested piece explicitly. If deep-copying every row of a large dataset is too expensive, the more scalable fix is usually to stop mutating in place at all, have normalize_inplace return a new structure instead of mutating its argument, which sidesteps the shallow/deep copy question entirely by removing the shared-mutable-state pattern that created the risk.

Direct answer
The four pillars are encapsulation (bundling data with the methods that operate on it, and hiding internal state behind a controlled interface), abstraction (exposing only what a caller needs, hiding how it's implemented), inheritance (a class reusing and specializing another class's behavior), and polymorphism (code that works against a common interface behaving correctly for many concrete types).

Structured elaboration

• Encapsulation: internal fields are kept private (or convention-marked, e.g. Python's leading underscore) and reached only through methods. Benefit: you can change the internal representation later without breaking every caller. Pitfall: exposing a mutable internal collection directly (a public list field) defeats encapsulation even if the field itself is 'private', because callers can still reach in and mutate it.
• Abstraction: a caller depends on a small, stable surface (an interface, an abstract base class, or just a documented method contract) rather than on implementation detail. Benefit: implementations can be swapped freely. Pitfall: a 'leaky abstraction' that forces callers to know implementation detail anyway (e.g. an interface that only makes sense if you know it's backed by a SQL table).
• Inheritance: a subclass gets a base class's fields and methods and can override behavior. Benefit: real code reuse for a genuine is-a relationship. Pitfall: inheritance used purely for code reuse (not a real is-a relationship) creates fragile coupling, since a change in the base class can silently break every subclass; composition (a class holding an instance of another class instead of inheriting from it) is often the safer default for anything beyond a shallow, genuinely-is-a hierarchy.
• Polymorphism: calling code written against a base type or interface automatically gets the right behavior for whatever concrete subtype is actually passed in, without an if/else on type. Benefit: adding a new type means adding a new class, not editing every call site (this is most of what the 'open/closed' principle (a design should be open to new behavior but closed to editing existing, working code) is about). Pitfall: relying on type-checking (isinstance) instead of polymorphism reintroduces the very branching the pattern exists to remove.

Worked example

class MetricCollector:
    def __init__(self, name):
        self._name = name          # encapsulation: internal state, reached via methods
        self._samples = []
    def record(self, value):
        self._samples.append(value)
    def summary(self):
        return f"{self._name}: n={len(self._samples)}"

class LatencyCollector(MetricCollector):   # inheritance
    def summary(self):                     # polymorphism: overrides base behavior
        if not self._samples:
            return f"{self._name}: no samples"
        avg = sum(self._samples) / len(self._samples)
        return f"{self._name}: avg={avg:.2f}ms over {len(self._samples)} samples"

Calling .summary() on a plain MetricCollector gives "requests: n=2"; calling the exact same method name on a LatencyCollector after recording 12.0 and 18.0 gives "p50_latency: avg=15.00ms over 2 samples" (verified: (12.0 + 18.0) / 2 = 15.00). Code that only knows it has a MetricCollector and calls .summary() gets the right behavior either way, that's the polymorphism.

Trade-offs & pitfalls
The pillars are not equally load-bearing in modern code: encapsulation and abstraction are used constantly and rarely controversial, while deep inheritance hierarchies are increasingly avoided in favor of composition ('composition over inheritance') once a hierarchy goes past one or two levels, because each additional layer makes behavior harder to predict from any single class definition. A senior answer should name that tension rather than presenting a 4-item inheritance-friendly hierarchy as the goal in itself.

Direct answer
Recursion trades stack space and a per-call overhead for code that mirrors the problem's natural self-similar structure; iteration trades that clarity for constant stack usage and typically better raw performance. The concrete risk with recursion is a stack overflow on deep input, and the usual mitigating technique, tail-call optimization, is not guaranteed across mainstream languages (notably CPython does not do it).

Structured elaboration

• Readability: recursion often reads closer to the mathematical or structural definition of the problem (a tree, a fractal-like decomposition, n! = n * (n-1)!). Iteration usually needs an explicit accumulator or work-list and can obscure that structure, especially for tree/graph problems.
• Stack usage: each recursive call pushes a new stack frame (return address, local variables). A recursive call chain of depth n uses O(n) stack space, while a well-written iterative loop uses O(1) auxiliary stack space (the loop variables live in one frame).
• Stack overflow risk: if depth exceeds the runtime's limit, you get a hard failure (Python's RecursionError, a native segfault-style crash in some languages). This is a real production risk whenever recursion depth is driven by input size rather than a small fixed bound.
• Tail-call optimization (TCO): in a 'tail-recursive' function, the recursive call is the very last operation, nothing happens after it returns. A compiler or runtime that supports TCO can reuse the current stack frame for that call instead of pushing a new one, turning the recursion into a loop under the hood with O(1) stack usage. Languages like Scheme and (in the target-relevant case) Java's Scala guarantee this for self-tail-calls; CPython deliberately does NOT implement it (a language design choice, not a limitation of the trick) partly because it would make stack traces less informative for debugging.

Worked example

def factorial_recursive(n):
    if n <= 1:
        return 1
    return n * factorial_recursive(n - 1)      # NOT tail-recursive: multiply happens after the call returns

def factorial_tail_style(n, acc=1):
    if n <= 1:
        return acc
    return factorial_tail_style(n - 1, acc * n)  # tail-recursive IN FORM, but Python still doesn't optimize it

def factorial_iterative(n):
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

All three agree on small input (verified: factorial_recursive(10) == factorial_iterative(10) == factorial_tail_style(10) == 3628800). The difference shows up at depth: with CPython's default recursion limit of 1000, factorial_recursive(5000) raises RecursionError: maximum recursion depth exceeded (confirmed by running it), while factorial_iterative(5000) completes normally regardless of the tail-style rewrite, because CPython never collapses the recursive call chain into a loop. The same real-world shape shows up walking a deep hierarchical structure (a category tree, a nested comment thread): a recursive walker is elegant until the tree gets deep enough that the recursion limit, not the actual computation, is what fails.

Trade-offs & pitfalls
A correct senior answer does not claim 'just write tail-recursive code and it'll be fine' in a language like Python, that is a common and wrong mental shortcut. The real decision is: if depth is bounded and small (most tree structures in practice), recursion's readability usually wins; if depth scales with untrusted or unbounded input, convert to an explicit iterative version with your own stack (see the tree-traversal conversion question for a worked version of exactly that conversion) rather than relying on the language to save you.

Direct answer
An immutable object's state can never change after construction, any operation that looks like a modification actually produces a new object; a mutable object's state can be changed in place through the same reference. The trade-off is safety and reasoning simplicity (immutable) versus avoided copying and lower memory churn (mutable).

Structured elaboration

• What immutability buys you: once you hold a reference to an immutable object, nobody else holding a different reference to the SAME object can surprise you by changing it out from under you. This matters most where a value is shared: as a dict/set key (see the containers discussion), as a default function argument, and across threads.
• Why it helps concurrency specifically: a data race requires at least one thread to write while another reads (or writes) the same memory. If the object literally cannot be written to after construction, that half of the race is structurally impossible, so immutable data can be freely shared across threads with zero synchronization (no locks needed) for reads. This is a much stronger guarantee than 'we were careful with locking'.
• What it costs: every 'modification' allocates a new object and (for anything nontrivial) copies the parts that didn't logically change. For a small string this is free; for a large data structure updated in a tight loop, allocating a full new copy per update can dominate runtime and memory traffic, this is the performance problem immutability can become.
• Java's concrete example: String is immutable, every apparent concatenation makes a new String object; repeatedly concatenating in a loop is a classic O(n^2) performance trap for exactly this reason, which is why StringBuilder (a mutable, purpose-built accumulator) exists as the escape hatch. Python's tuple vs list is the same shape: tuple gives you the sharing-safety and hashability of immutability, list gives you cheap in-place growth when you know you own the only reference.

Worked example

name = "engineer"
upper_name = name.upper()   # returns a NEW string; name itself is untouched
assert name == "engineer"
assert upper_name == "ENGINEER"

nums = [1, 2, 3]
nums.append(4)              # mutates the SAME list object in place
assert nums == [1, 2, 3, 4]

(both assertions verified). name.upper() cannot change name because Python strings are immutable, there is no operation that mutates a str in place; nums.append(4) changes the exact object nums refers to, so any other variable that also referenced that list would see the appended 4 too, that aliasing behavior is the concrete risk mutable shared state introduces.

Trade-offs & pitfalls
The practical decision is rarely 'immutability is always better', it's 'default to immutable for anything shared or used as a key, and reach for mutable structures deliberately, in the narrow scope where you know you own the only reference and the update pattern is hot enough that copy-on-write would actually cost something measurable'. Treating one choice as universally correct, in either direction, is the mistake.