Linked Lists and Trees Questions

Dynamic and pointer based data structures including linked lists and tree structures commonly tested in interviews. For linked lists cover node based representation, traversal, insertion at head and tail, deletion, searching, reversing a list, detecting cycles, and tradeoffs versus array based lists. For trees cover basic concepts such as binary trees and binary search trees, tree node representation, insertion and deletion in search trees, recursion patterns, and traversal algorithms including depth first search with in order pre order and post order variants and breadth first search. Also include problem solving patterns such as recursion and iterative stack or queue based approaches, analysis of time and space complexity in plain terms, and common interview tasks such as lowest common ancestor, tree balancing awareness, and converting between representations. Practice includes implementing algorithms, writing traversal routines, and reasoning about correctness and performance.

EasyTechnical

72 practiced

Explain the binary search tree (BST) invariant and why an inorder traversal of a BST yields node values in sorted order. Provide a short example tree and state average and worst-case time complexity for search, insert, and delete, explaining how imbalance affects performance.

EasyTechnical

85 practiced

Implement find_middle(head) in Python to return the middle node of a singly linked list in a single pass using the two-pointer (fast/slow) technique. Specify how you choose the middle for even-length lists (first or second middle) and discuss time/space complexity and potential ML batching use-cases.

Sample Answer

Approach: use the classic two-pointer (slow/fast) technique in one pass. I choose the second middle for even-length lists (i.e., when list length is 4, return node 3). That choice is common and useful when you want the later central item as anchor for windowing or splits.

python

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

def find_middle(head):
    """
    Returns the middle node using slow/fast pointers.
    For even-length lists, returns the second middle.
    """
    if head is None:
        return None

    slow = head
    fast = head
    # Advance fast by 2 and slow by 1; when fast reaches end, slow is at middle.
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    return slow

Key points:- We initialize both at head; loop condition fast and fast.next ensures fast moves in steps of two.- Returning slow when loop ends yields the second middle for even lengths.

Time & space complexity:- Time: O(n) single pass over list.- Space: O(1) constant extra space.

Edge cases:- Empty list -> None.- Single-node list -> returns that node.- Two-node list -> returns second node (by design).

ML batching / practical use-cases:- Selecting a representative frame from a streamed video/sequence: pick the middle frame as anchor for temporal cropping or augmentation.- Splitting time-series or sequence data into two halves for contrastive learning or paired augmentations—using the middle node as a deterministic split point.- Stream processing: when building fixed-size windows from a stream, the middle element can serve as label alignment or timestamp anchor for batching.- Efficient online sampling in data pipelines where you traverse linked structures of precomputed features and need O(1) memory, single-pass downsampling.

EasyTechnical

72 practiced

Explain trade-offs between using a linked list vs a dynamic array (resizable array) to implement a dynamic list in ML feature pipelines. Discuss memory locality, CPU cache behavior, random access, insertion/deletion costs, resizing overhead, vectorized/batched operations, and give concrete examples when you would choose each in an ML system.

Sample Answer

High-level trade-off: dynamic arrays (resizable arrays / vectors) favor memory locality and fast random access; linked lists favor cheap O(1) insert/delete at known nodes and stable pointers but pay heavy costs in locality and CPU cache behavior.

Memory locality & CPU cache:- Dynamic array: contiguous memory -> excellent spatial locality, fewer cache misses, much faster for scanning and tight loops (important for feature extraction, normalization, batching).- Linked list: nodes scattered in heap -> many cache misses, pointer chasing stalls CPU, poor throughput for sequential processing.

Random access:- Dynamic array: O(1) index access — ideal when features need random reads (e.g., lookups, sparse-to-dense conversion).- Linked list: O(n) to index — impractical if you frequently need arbitrary access.

Insertion/deletion costs:- Dynamic array: O(1) amortized append; O(n) insert/delete in middle (shift elements).- Linked list: O(1) insert/delete given node pointer; O(n) to find position.

Resizing overhead:- Dynamic array: occasional O(n) copy during resize (amortized cost small). For ML pipelines, pre-allocating or reserving capacity avoids pauses.- Linked list: no resizing copies, but per-element allocation overhead and fragmentation.

Vectorized/batched operations:- Dynamic array: supports SIMD, BLAS calls, bulk memcpy — huge win for numeric ops (batch transforms, tensor assembly).- Linked list: cannot be vectorized efficiently; per-node operations break batching.

Concrete choices in ML systems:- Choose dynamic array when: building feature tensors, batching examples, performing vectorized transforms, or needing random access (most data pipelines, minibatch assembly, embedding lookups). Example: assembling a batch of 1,024 float features for GPU transfer — contiguous array minimizes copy and maximizes throughput.- Choose linked list when: you must frequently insert/remove elements in the middle and dataset sizes are small or operations are pointer-centric (e.g., maintaining an ordered stream of metadata, implementing an LRU cache with splice operations where node stability matters). Example: maintaining a small linked queue of live inference requests with frequent removals by pointer.

Summary: For ML pipelines prioritizing throughput, batching, and numeric operations, dynamic arrays are almost always the better default. Use linked lists only for niche cases where constant-time splices and stable node identities outweigh severe locality and vectorization penalties.

MediumTechnical

72 practiced

Implement merge_two_sorted_lists(l1, l2) in Python to merge two sorted singly linked lists into a single sorted list in-place (do not create new nodes). Return the head of the merged list and analyze time/space complexity and pointer invariants for correctness.

Sample Answer

To merge two sorted singly linked lists in-place, iterate with a dummy/prehead pointer and splice nodes from l1 or l2 by reassigning next pointers — never allocate new ListNode objects. This preserves nodes and achieves O(n) time and O(1) extra space.

python

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

def merge_two_sorted_lists(l1: ListNode, l2: ListNode) -> ListNode:
    """
    Merge two sorted linked lists in-place and return head of merged list.
    """
    pre = ListNode(-1)      # temporary dummy node (allowed as pointer only)
    tail = pre              # tail always points to last node in merged list

    a, b = l1, l2
    while a and b:
        if a.val <= b.val:
            tail.next = a   # link a into merged list
            a = a.next      # advance a
        else:
            tail.next = b   # link b into merged list
            b = b.next      # advance b
        tail = tail.next    # advance tail to newly linked node

    # attach remaining nodes (no new allocations)
    tail.next = a if a else b

    return pre.next

Key points and pointer invariants:- Invariant 1: pre.next is head of merged prefix; tail is last node of that prefix.- Invariant 2: a and b always point to heads of remaining sorted sublists.- Each loop iteration advances exactly one of a or b and moves tail to include that node; no node is lost because tail.next is set before advancing the chosen pointer.- After loop, one list is exhausted and remaining nodes are already sorted, so attaching its head preserves overall order.

Time complexity: O(n+m) where n and m are lengths of l1 and l2. Space complexity: O(1) extra (dummy node is constant auxiliary pointer; no new list nodes created).

Edge cases: one or both inputs None, lists with duplicate values, very long lists (no recursion used so safe for deep lists).

MediumTechnical

71 practiced

You maintain a large, frequently-read, occasionally-changed tree representing feature hierarchies used at runtime. Propose data structures, caching, and update strategies to support low-latency lookups and occasional insert/delete operations without heavy rebalancing. Explain how you would validate and safely deploy updates.

Sample Answer

Design summary:- Use an immutable, versioned in-memory tree representation for reads and a log/CRDT-like apply path for writes. Keep the canonical mutable store in a database (e.g., PostgreSQL/Document DB) and publish fully-built immutable snapshots to readers.

Data structures & caching:- Represent the hierarchy as an immutable tree (nodes with children arrays and metadata). Immutable snapshots allow lock-free reads and cheap copy-on-write for updates.- For ultra-fast lookups, maintain: - A memory-mapped flat index (hash map) mapping feature keys/IDs to node pointers for O(1) access. - Sharded caches (per service instance) with read-through behavior and small LRU TTLs for rarely accessed branches. - Optional prefix trie if many prefix/pattern queries are common.- Store snapshots in a content-addressed cache (e.g., S3 + CDN or Redis + version key) so services can load by version.

Update strategy (occasional inserts/deletes, avoid rebalancing):- Apply updates to a builder process that loads current snapshot, does localized copy-on-write of affected branches, produces a new immutable snapshot (no global rebalance needed).- Persist delta as an append-only log entry with metadata, validation, and a new snapshot version hash.- Use atomic version pointer swap: update a single version key (etcd/consul/DB) to point readers to the new snapshot.

Validation & safe deployment:- Pre-commit validations: schema checks, invariants (no cycles, depth limits), unit tests, and property tests on builder.- Dry-run: run offline simulations with representative traffic (or sample production traffic) to ensure behavior and latency.- Canary rollout: publish new snapshot to a small subset of instances; monitor correctness metrics (lookup counts, misses, downstream ML feature drift, tail latency).- Automated sanity checks: checksums, node counts, and end-to-end test queries validated against expected outputs.- Fast rollback: keep previous snapshot versions and only swap version pointer back on failure.- Observability: log version ID with every feature lookup, expose metrics (latency, error rate, cache hit rate), and alert on anomalies.

Why this works for ML systems:- Immutable snapshots avoid read contention during inference serving.- Versioning enables reproducible model runs and A/B testing.- Localized copy-on-write keeps updates cheap without expensive rebalancing.- Canary + metrics reduce risk of corrupt/behavioral regressions impacting models.

Unlock Full Question Bank

Get access to hundreds of Linked Lists and Trees interview questions and detailed answers.

Join thousands of developers preparing for their dream job.