Linked Lists, Stacks, and Queues Questions

Covers core singly and doubly linked list concepts and the fundamental abstract data types stack and queue. For linked lists this includes node structure, traversal, insertion at head and tail, deletion, reversal, finding middle, merging, detecting cycles, removing duplicates, intersection detection, and pointer manipulation details for languages with manual memory management. For stacks and queues this includes LIFO and FIFO semantics, push, pop, peek, enqueue, dequeue, circular buffer implementations, and implementing one with the other (for example queue with two stacks). Also includes array versus linked list implementations, complexity analysis for time and space, and common algorithmic patterns that use these structures (for example bracket matching, reverse polish notation evaluation, depth first search using a stack, breadth first search using a queue, sliding window and monotonic queue techniques). Interviewers assess correct implementation, edge case handling, performance tradeoffs, and ability to choose the appropriate structure or approach for a problem.

EasyTechnical

44 practiced

Given the following C++ singly linked list Node:

cpp

struct Node { int val; Node* next; };

Describe correct deletion of a node and how to avoid memory leaks and dangling pointers. Explain how you would manage ownership with unique_ptr/shared_ptr in modern C++ in the context of ML code that integrates native layers with Python bindings.

Sample Answer

To delete a node correctly with the raw Node type:

- If you own a Node* allocated with new, call delete exactly once. After delete, set the pointer to nullptr to avoid a dangling pointer.- When removing a node from a singly linked list, fix links first, then delete the node.

Example (safe removal of the node after prev):

cpp

// remove node `curr` given pointer `prev` (prev->next == curr)
prev->next = curr->next;   // unlink
delete curr;               // free memory
curr = nullptr;            // avoid dangling pointer

If removing the head:

cpp

Node* tmp = head;
head = head->next;
delete tmp;
tmp = nullptr;

Common pitfalls: double-delete (deleting same pointer twice), deleting stack or static memory, and use-after-free when other code still holds pointers to the deleted node.

Modern C++ ownership: prefer smart pointers.

- unique_ptr for exclusive ownership: - Use std::unique_ptr<Node> next; ownership is a single chain; automatic deletion when the owner goes out of scope; move semantics when re-linking nodes. - Example:

cpp

struct Node { int val; std::unique_ptr<Node> next; };
    // to insert: node->next = std::make_unique<Node>(...);
    // to remove: node->next = std::move(node->next->next); // deletes the removed node automatically

- shared_ptr for shared ownership: - Use std::shared_ptr<Node> when multiple owners need access. Be careful of cycles — they leak memory. - Break cycles with std::weak_ptr for back-references.

In ML code integrating native layers with Python bindings:

- Prefer shared_ptr across language boundaries because both C++ and Python may hold references. pybind11 and other binding tools can manage std::shared_ptr lifetimes safely by sharing ownership with Python objects.- For transient C++-only ownership, use unique_ptr to express intent and move semantics; expose a non-owning raw pointer or create a shared_ptr when handing ownership to Python.- Avoid exposing naked new/delete to Python — use smart pointers or factory functions that return std::shared_ptr to ensure deterministic lifetime.- When using CUDA or other native resources, wrap them in RAII types (unique_ptr with custom deleter or a dedicated resource class) so resource cleanup is deterministic even across exceptions.

Summary best practices:- Prefer smart pointers: unique_ptr for single ownership and performance, shared_ptr + weak_ptr when ownership is shared.- Always null out raw pointers after delete if you must use them.- In bindings, favor shared_ptr to let Python hold references safely; use weak_ptr to avoid cycles.

EasyTechnical

36 practiced

Explain Floyd's Tortoise and Hare algorithm for cycle detection in a singly linked list. Describe how to find the cycle's start node after detecting a cycle, and give time and space complexity. Mention how this is relevant when debugging pointer-based data structures in lower-level ML components (e.g., C++ memory pools).

EasyTechnical

44 practiced

Implement a queue using two stacks in Python. Provide enqueue(x) and dequeue() with amortized O(1) time. Explain the amortized analysis and what happens in worst-case single operations. Discuss how this pattern might be used to implement an asynchronous buffer in a microservice that only exposes stack-like primitives.

Sample Answer

Approach: Use two stacks, inbox for enqueue, outbox for dequeue. Enqueue pushes to inbox. Dequeue pops from outbox; if outbox empty, pour all items from inbox to outbox (reverses order). This yields amortized O(1) per operation.

python

class QueueWithTwoStacks:
    def __init__(self):
        self.inbox = []   # push-only stack
        self.outbox = []  # pop-only stack

    def enqueue(self, x):
        # O(1)
        self.inbox.append(x)

    def dequeue(self):
        # Amortized O(1)
        if not self.outbox:           # only transfer when needed
            while self.inbox:
                self.outbox.append(self.inbox.pop())
        if not self.outbox:
            raise IndexError("dequeue from empty queue")
        return self.outbox.pop()

    def peek(self):
        if not self.outbox:
            while self.inbox:
                self.outbox.append(self.inbox.pop())
        if not self.outbox:
            raise IndexError("peek from empty queue")
        return self.outbox[-1]

    def empty(self):
        return not self.inbox and not self.outbox

Amortized analysis: Each element is moved at most once from inbox→outbox, and each push/pop is O(1). Over n operations, total work is O(n), so amortized O(1) per operation. Worst-case single operation: a dequeue may cost O(n) when it triggers a full transfer.

Pattern usage in microservice async buffer: If a service only exposes stack-like primitives (push/pop) — e.g., a limited storage API — you can implement FIFO buffering by maintaining two logical stacks in the service (or two endpoints). Producers push to inbox; consumer pops from outbox, with a background or on-demand transfer operation to reverse inbox into outbox. Ensure idempotency, persistence, and concurrency control (locking or optimistic compare-and-swap) when multiple producers/consumers exist. This pattern provides a simple FIFO layer over stack-only storage with predictable amortized performance.

EasyTechnical

74 practiced

Implement a basic singly linked list in Python with these operations: insert_head(value), insert_tail(value), delete(value), and to_list(). Use the following Node skeleton:

python

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

Ensure insert_tail is O(1) amortized time. Handle empty list edge cases.

Sample Answer

To satisfy O(1) amortized insert_tail, keep both head and tail pointers and update them on inserts/deletes.

python

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

class SinglyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
        self.size = 0  # optional, useful for checks

    def insert_head(self, value):
        new_node = Node(value, self.head)
        self.head = new_node
        if self.tail is None:  # list was empty
            self.tail = new_node
        self.size += 1

    def insert_tail(self, value):
        new_node = Node(value)
        if self.tail is None:  # empty list
            self.head = self.tail = new_node
        else:
            self.tail.next = new_node
            self.tail = new_node
        self.size += 1

    def delete(self, value):
        prev = None
        curr = self.head
        while curr:
            if curr.val == value:
                if prev:
                    prev.next = curr.next
                else:
                    self.head = curr.next
                if curr is self.tail:  # removed tail
                    self.tail = prev
                self.size -= 1
                return True  # deleted first occurrence
            prev, curr = curr, curr.next
        return False  # not found

    def to_list(self):
        out = []
        curr = self.head
        while curr:
            out.append(curr.val)
            curr = curr.next
        return out

Key points:- insert_tail is O(1) because we maintain tail pointer.- delete is O(n) to find the node; handles removing head, middle, tail, and empty list.- to_list is O(n).Edge cases: inserting into empty list, deleting the only node (updates head and tail), deleting non-existent value, duplicates (deletes first match). Alternative: keep dummy head to simplify delete logic.

EasyTechnical

49 practiced

Describe the algorithm that uses a stack to validate balanced brackets in a string (e.g., "()[]{}"), and state time/space complexity. Provide a short Python-style pseudocode snippet and explain one real ML engineering use case where bracket matching or expression validation matters (for example, parsing model configuration or computation graph expressions).

Sample Answer

Algorithm: use a stack to ensure every opening bracket has a matching closing bracket in correct order (LIFO). Scan characters; push opening brackets; when you see a closing bracket, check stack top matches its corresponding opening bracket; if not, invalid. At end, stack must be empty.

Pseudocode (Python-style):

python

def is_balanced(s):
    pairs = {')':'(', ']':'[', '}':'{'}
    stack = []
    for ch in s:
        if ch in pairs.values():        # opening
            stack.append(ch)
        elif ch in pairs:              # closing
            if not stack or stack[-1] != pairs[ch]:
                return False
            stack.pop()
        else:
            continue                   # ignore other chars or handle as needed
    return not stack

Why it works:- Stack enforces nesting order: most recent unclosed opening must be closed first.- Matching via dictionary ensures type correctness.

Complexity:- Time: O(n) — single pass over string.- Space: O(n) in worst case (all openings on stack).

Edge cases:- Empty string -> balanced.- More closings than openings -> early False.- Non-bracket characters -> skip or validate separately.

ML engineering use case:- Validating model configuration expressions or computation-graph specs (e.g., custom layer definitions, serialized computation expressions, or small DSLs used in pipeline configs). Ensures parentheses/bracketed parameter lists and tensor shape expressions are well-formed before parsing into a graph (prevents runtime errors in graph construction or wrong operator arity), improving reliability of model deployment and automated config validation in CI.

Unlock Full Question Bank

Get access to hundreds of Linked Lists, Stacks, and Queues interview questions and detailed answers.

Join thousands of developers preparing for their dream job.