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.

MediumTechnical

39 practiced

Given a long stream of tokens that must be windowed for online feature extraction, explain how you would implement efficient sliding-window counts (or maxima/minima) using appropriate queue(s), and how to evict old elements, handle out-of-order arrivals, and memory bounds.

Sample Answer

Approach summary:Use time-ordered deques for eviction and a hashmap + monotonic deque for efficient counts/max/min. Keep items with timestamps so you can evict by window age. For memory/control, fall back to approximate sketches or capped buffers.

Design details:- Core structures: - eventQueue: deque of (timestamp, token) in arrival order (or insertion-order if already ordered). - counts: hashmap token -> integer count for exact counts in window. - maxDeque/minDeque: monotonic deques storing (timestamp, value) to get O(1) current max/min.- Ingestion & eviction: - On arrival, append (ts, token) to eventQueue. - Increment counts[token]. - For max/min, pop from back while new value dominates then push. - Evict loop: while eventQueue.front.timestamp < current_time - window_size: - pop front, decrement counts; if count becomes 0 remove key. - if front equals maxDeque.front, pop maxDeque.front (same for minDeque). - This keeps operations amortized O(1).- Out-of-order arrivals: - Buffer events for a small allowed lateness (L) and use a watermark time = current_time - L; only advance eviction past watermark. - If events arrive older than watermark: either reject/route to “late” handler or apply as best-effort (update counts and correct structures; might require scanning eventQueue to insert—expensive). - For higher out-of-order tolerance, use per-bucket windows (fixed-size time buckets) so late-events update bucket counts without reordering the main deque.- Memory bounds / approximations: - For large vocabularies use Count-Min Sketch (space-memory tradeoff) instead of exact hashmap; gives approximate counts with error guarantees. - Cap queue length and apply sampling or reservoir sampling if throughput is extreme. - TTL on low-frequency tokens to remove rarely-used keys.- Complexity: - Exact solution: amortized O(1) per event, O(N) memory for window size N. - With sketches: O(1) time, bounded memory, probabilistic error.

Trade-offs:- Exact counts and exact max/min require deterministic ordering and can be memory-heavy.- Bucketing + sketches trades accuracy for bounded memory and simpler late-event handling.- Choose L (allowed lateness), bucket size, and sketch parameters based on latency vs accuracy needs.

EasyTechnical

40 practiced

In Python, implement a simple SinglyLinkedList class supporting: insert_head(value), remove_head(), and to_list() for testing. Ensure your implementation correctly handles empty lists, updates head and tail as needed, and runs insert_head in O(1) time. Show Node structure in your answer.

Sample Answer

To implement a simple singly linked list with O(1) insert at head and correct empty/head/tail handling, we keep Node objects with value and next, and the list stores head and tail pointers. insert_head updates both head and tail when the list was empty. remove_head returns the removed value (or None) and updates tail to None when the list becomes empty.

python

class Node:
    """Node for singly linked list"""
    def __init__(self, value):
        self.value = value
        self.next = None

class SinglyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None  # keep tail to track end (useful if we extend later)

    def insert_head(self, value):
        """Insert value at head in O(1) time."""
        node = Node(value)
        node.next = self.head
        self.head = node
        if self.tail is None:  # list was empty before insert
            self.tail = node

    def remove_head(self):
        """Remove and return head value. Return None if list is empty."""
        if self.head is None:
            return None
        removed = self.head
        self.head = self.head.next
        if self.head is None:  # list became empty after removal
            self.tail = None
        removed.next = None  # detach for safety
        return removed.value

    def to_list(self):
        """Return Python list of values for testing."""
        out = []
        cur = self.head
        while cur:
            out.append(cur.value)
            cur = cur.next
        return out

Key points:- insert_head runs in O(1) time and updates tail when list was empty.- remove_head handles empty list and updates tail when list becomes empty.- to_list is O(n) for testing/inspection.

Edge cases:- removing from empty list returns None- inserting into empty list sets both head and tail to new node

EasyTechnical

70 practiced

Given two sorted singly linked lists, write a function to merge them into a single sorted list in-place (reuse nodes, no new allocations). Implement in Python or Java and explain how you maintain O(1) extra space and O(n) time.

Sample Answer

To merge two sorted singly linked lists in-place, iterate through both lists with pointers and stitch nodes by adjusting next pointers—no new nodes allocated. Use a dummy/prehead node for easier handling (prehead is a pointer, not a new data node allocation of list elements—allowed as 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 singly linked lists in-place (reuse nodes).
    Returns head of merged list.
    """
    prehead = ListNode(-1)         # O(1) extra space helper
    prev = prehead

    while l1 and l2:
        if l1.val <= l2.val:
            prev.next = l1         # reuse l1 node
            l1 = l1.next
        else:
            prev.next = l2         # reuse l2 node
            l2 = l2.next
        prev = prev.next

    # attach remaining part (one list may be non-empty)
    prev.next = l1 if l1 else l2

    return prehead.next

Key points:- We only rewire next pointers; no node creation except one constant helper (prehead).- Time complexity O(n) where n = total nodes (each node visited once).- Space complexity O(1) extra (constant pointers).Edge cases:- One or both lists empty.- Lists with duplicate values.Alternative:- Without prehead: handle head initialization separately, but prehead simplifies logic.

EasyTechnical

39 practiced

Describe a circular buffer (ring buffer) for implementing a fixed-capacity queue. Explain how you detect full vs empty, and write enqueue/dequeue pseudo-code in C++ that avoids moving elements and runs in O(1) time.

Sample Answer

A circular buffer (ring buffer) is a fixed-size array used as a FIFO queue by treating the array as circular: when an index reaches the end it wraps to 0. It avoids moving elements by maintaining indices for head (pop position) and tail (push position). Two common ways to distinguish full vs empty:

- Maintain a size counter (size == 0 => empty, size == capacity => full).- Or use capacity+1 and treat buffer as full when (tail + 1) % (capacity+1) == head (simpler boolean-free check).

Using the size approach (clear and intuitive), here is O(1) enqueue/dequeue pseudo-code in C++ style:

cpp

// Fixed-capacity circular buffer (no element moves)
template<typename T>
class RingBuffer {
public:
    RingBuffer(size_t capacity) : cap(capacity), buf(new T[capacity]), head(0), tail(0), sz(0) {}

    ~RingBuffer() { delete[] buf; }

    bool enqueue(const T& item) {
        if (sz == cap) return false; // full
        buf[tail] = item;
        tail = (tail + 1) % cap;
        ++sz;
        return true;
    }

    bool dequeue(T &out) {
        if (sz == 0) return false; // empty
        out = buf[head];
        head = (head + 1) % cap;
        --sz;
        return true;
    }

    bool empty() const { return sz == 0; }
    bool full() const { return sz == cap; }
    size_t size() const { return sz; }

private:
    size_t cap;
    T* buf;
    size_t head; // next to read
    size_t tail; // next to write
    size_t sz;   // current number of elements
};

Key points:- Enqueue/dequeue are O(1): single assignment and index arithmetic.- No element shifting; elements are overwritten only when explicitly allowed (after dequeue).- Space: O(capacity). Edge cases: ensure capacity>0, handle wrap with modulo, and decide behavior on full (reject or overwrite).

EasyTechnical

39 practiced

Given a singly linked list, implement a function to return the middle node. For even-length lists return the second of the two middle nodes. Write code (in Python or Java) and explain why your approach is O(n) time and O(1) space using two pointers (fast and slow).

Sample Answer

To find the middle node (for even length return the second middle) we use two pointers: slow moves one step, fast moves two steps. When fast reaches the end, slow is at the desired middle. This is O(n) time because each loop advances fast by two nodes so the loop runs ~n/2 iterations; O(1) space because only two pointers are used.

python

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

def middleNode(head: ListNode) -> ListNode:
    """
    Return middle node of singly linked list.
    If list has even length, returns the second middle node.
    """
    slow = head
    fast = head
    # advance fast by 2 and slow by 1; when fast is None or fast.next is None, slow is middle (second middle for even)
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow

Key points:- Initialization: both pointers start at head.- Loop condition fast and fast.next ensures fast can move two steps safely.- For even-length lists (e.g., 4 nodes), iterations move slow to node 3 — the second middle.

Time complexity: O(n) — each node visited constant number of times (fast skips but overall proportional to n). Space complexity: O(1) — only two pointer variables used.

Edge cases:- Empty list: head is None — function returns None (handle if needed). - Single-node list: returns that node. - Very large lists: still O(1) additional memory and linear time.

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.