Flatten a Multilevel Doubly Linked List

🎯

Flatten a Multilevel Doubly Linked List

mediumDESIGNAmazonMicrosoftGoogle

Imagine you have a complex file system where folders can contain files and other folders nested arbitrarily deep. You want to list all files in a single linear order, flattening the hierarchy.

💡 This problem involves traversing and modifying a complex linked data structure with multiple levels. Beginners often struggle because it requires careful pointer manipulation and understanding how to traverse nested structures without losing track of nodes.

📋

Problem Statement

You are given a doubly linked list where in addition to the next and previous pointers, each node may have a child pointer, which may point to a separate doubly linked list. These child lists may have one or more children of their own, and so on, to produce a multilevel data structure. Flatten the list so that all the nodes appear in a single-level, doubly linked list. The nodes should appear in the order they are encountered in a depth-first traversal.

1 ≤ Number of nodes ≤ 10^5Node values are integersChild pointers may be nullThe list may be empty (head is null)

💡

Example

Input"1---2---3---4---5---6--NULL\n |\n 7---8---9---10--NULL\n |\n 11--12--NULL"

Output1---2---3---7---8---11---12---9---10---4---5---6--NULL

Starting at head 1, traverse next nodes until 3, then go down child list starting at 7, flattening recursively, then continue with 4, 5, 6.

• Empty list (head is null) → output is null
• List with no child pointers → output is the same list
• List where every node has a child → output is a deeply nested flattened list
• List with multiple levels of nesting → output is a single-level list preserving DFS order

⚠️

Common Mistakes

Not removing the child pointer after splicing

Leads to infinite loops or incorrect list structure

✅ Set node.child = None/null after splicing child list

Incorrectly updating prev pointers when splicing

Broken doubly linked list, causing traversal errors

✅ Always update both next and prev pointers when connecting nodes

Using recursion without considering stack overflow

Runtime error on very deep nested lists

✅ Use iterative approach with explicit stack for deep nesting

Finding tail of child list repeatedly in in-place approach

Leads to O(n^2) time complexity and slow performance

✅ Use stack-based approach or memoize tail nodes if possible

Not handling empty list input

Null pointer exceptions or crashes

✅ Check if head is null at start and return immediately

🧠

Brute Force (Pure Recursion)

💡 Starting with a pure recursive approach helps understand the problem's depth-first nature and how child lists are integrated. It is intuitive but can cause stack overflow on deep nesting.

Intuition

Recursively flatten each child list and splice it into the main list at the node with the child pointer, then continue flattening the rest of the list.

Algorithm

1. If the current node is null, return null.
2. Recursively flatten the child list if it exists.
3. Splice the flattened child list between the current node and the next node.
4. Recursively flatten the next node after splicing and return the head.

💡 The challenge is to correctly connect the child list in place without losing track of the next nodes, which recursion helps manage by implicit call stack.

</>

Code

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

def flatten(head):
    if not head:
        return head

    def dfs(node):
        curr = node
        last = node
        while curr:
            next_node = curr.next
            if curr.child:
                child_last = dfs(curr.child)
                curr.next = curr.child
                curr.child.prev = curr
                curr.child = None
                if next_node:
                    child_last.next = next_node
                    next_node.prev = child_last
                last = child_last
            else:
                last = curr
            curr = next_node
        return last

    dfs(head)
    return head

# Driver code to test
if __name__ == '__main__':
    # Build example list manually or use helper functions
    pass  # For brevity, driver omitted

Line Notes

if not head:Handle empty list edge case immediately

def dfs(node):Define recursive helper to flatten starting at node

while curr:Traverse current level nodes sequentially

if curr.child:When child exists, recursively flatten child list

curr.next = curr.childSplice child list into next pointer

curr.child.prev = currMaintain doubly linked property backward

curr.child = NoneRemove child pointer after splicing

if next_node:Reconnect the tail of child list to next node

return lastReturn last node of flattened list for linking

class Node {
    public int val;
    public Node prev;
    public Node next;
    public Node child;

    public Node(int val) {
        this.val = val;
    }
}

public class Solution {
    public Node flatten(Node head) {
        if (head == null) return head;
        dfs(head);
        return head;
    }

    private Node dfs(Node node) {
        Node curr = node;
        Node last = node;
        while (curr != null) {
            Node next = curr.next;
            if (curr.child != null) {
                Node childLast = dfs(curr.child);
                curr.next = curr.child;
                curr.child.prev = curr;
                curr.child = null;
                if (next != null) {
                    childLast.next = next;
                    next.prev = childLast;
                }
                last = childLast;
            } else {
                last = curr;
            }
            curr = next;
        }
        return last;
    }

    // Main method omitted for brevity
}

Line Notes

if (head == null) return head;Quickly handle empty input

private Node dfs(Node node) {Recursive helper to flatten from node

while (curr != null) {Iterate current level nodes

if (curr.child != null) {Process child list recursively

curr.next = curr.child;Splice child list into main list

curr.child.prev = curr;Maintain backward link

curr.child = null;Remove child pointer after splicing

if (next != null) {Reconnect tail of child list to next node

return last;Return last node for linking

class Node {
public:
    int val;
    Node* prev;
    Node* next;
    Node* child;
    Node(int _val) : val(_val), prev(nullptr), next(nullptr), child(nullptr) {}
};

class Solution {
public:
    Node* flatten(Node* head) {
        if (!head) return head;
        dfs(head);
        return head;
    }

private:
    Node* dfs(Node* node) {
        Node* curr = node;
        Node* last = node;
        while (curr) {
            Node* next = curr->next;
            if (curr->child) {
                Node* childLast = dfs(curr->child);
                curr->next = curr->child;
                curr->child->prev = curr;
                curr->child = nullptr;
                if (next) {
                    childLast->next = next;
                    next->prev = childLast;
                }
                last = childLast;
            } else {
                last = curr;
            }
            curr = next;
        }
        return last;
    }
};

// main() omitted for brevity

Line Notes

if (!head) return head;Handle empty list edge case

Node* dfs(Node* node) {Recursive helper to flatten starting at node

while (curr) {Traverse nodes at current level

if (curr->child) {Recursively flatten child list

curr->next = curr->child;Splice child list into next pointer

curr->child->prev = curr;Maintain backward link

curr->child = nullptr;Remove child pointer after splicing

if (next) {Reconnect tail of child list to next node

return last;Return last node of flattened list

class Node {
    constructor(val, prev = null, next = null, child = null) {
        this.val = val;
        this.prev = prev;
        this.next = next;
        this.child = child;
    }
}

var flatten = function(head) {
    if (!head) return head;

    function dfs(node) {
        let curr = node;
        let last = node;
        while (curr) {
            let next = curr.next;
            if (curr.child) {
                let childLast = dfs(curr.child);
                curr.next = curr.child;
                curr.child.prev = curr;
                curr.child = null;
                if (next) {
                    childLast.next = next;
                    next.prev = childLast;
                }
                last = childLast;
            } else {
                last = curr;
            }
            curr = next;
        }
        return last;
    }

    dfs(head);
    return head;
};

// Example usage omitted for brevity

Line Notes

if (!head) return head;Return immediately if list is empty

function dfs(node) {Recursive helper to flatten from node

while (curr) {Traverse current level nodes

if (curr.child) {Process child list recursively

curr.next = curr.child;Splice child list into main list

curr.child.prev = curr;Maintain backward link

curr.child = null;Remove child pointer after splicing

if (next) {Reconnect tail of child list to next node

return last;Return last node for linking

⏱

Complexity

TimeO(n)

SpaceO(n) due to recursion stack in worst case

Each node is visited once, but recursion depth can be up to n in worst case of deep nesting.

💡 For n=1000 nodes, this means roughly 1000 operations but recursion stack could be large if nesting is deep.

Interview Verdict: Accepted but may cause stack overflow on very deep nesting

This approach is intuitive and acceptable for moderate input sizes but risky for very deep lists due to recursion depth limits.

🧠

Iterative DFS Using Stack

💡 Using an explicit stack to simulate recursion avoids stack overflow and clarifies the depth-first traversal order, making it more robust for large inputs.

Intuition

Traverse the list iteratively, pushing next nodes onto a stack before diving into child lists, so you can return to the next nodes after finishing children.

Algorithm

1. Initialize a stack and push the head node.
2. Pop a node from the stack and process it, connecting it to the previous node.
3. If the node has a next pointer, push it onto the stack.
4. If the node has a child pointer, push the child onto the stack and remove the child pointer.
5. Repeat until the stack is empty.

💡 The stack keeps track of nodes to visit next, ensuring depth-first order without recursion.

</>

Code

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

def flatten(head):
    if not head:
        return head

    stack = [head]
    prev = None

    while stack:
        curr = stack.pop()
        if prev:
            prev.next = curr
            curr.prev = prev
        if curr.next:
            stack.append(curr.next)
        if curr.child:
            stack.append(curr.child)
            curr.child = None
        prev = curr

    return head

# Driver code omitted for brevity

Line Notes

if not head:Handle empty list edge case

stack = [head]Initialize stack with head node to start traversal

while stack:Process nodes until none left

curr = stack.pop()Pop node to process in DFS order

if prev:Link current node with previous node

if curr.next:Push next node to stack to visit later

if curr.child:Push child node to stack to visit next

curr.child = NoneRemove child pointer after pushing

prev = currUpdate previous pointer

import java.util.Stack;

class Node {
    public int val;
    public Node prev;
    public Node next;
    public Node child;

    public Node(int val) {
        this.val = val;
    }
}

public class Solution {
    public Node flatten(Node head) {
        if (head == null) return head;

        Stack<Node> stack = new Stack<>();
        stack.push(head);
        Node prev = null;

        while (!stack.isEmpty()) {
            Node curr = stack.pop();
            if (prev != null) {
                prev.next = curr;
                curr.prev = prev;
            }
            if (curr.next != null) {
                stack.push(curr.next);
            }
            if (curr.child != null) {
                stack.push(curr.child);
                curr.child = null;
            }
            prev = curr;
        }

        return head;
    }

    // Main method omitted for brevity
}

Line Notes

if (head == null) return head;Handle empty input quickly

Stack<Node> stack = new Stack<>();Use stack to simulate recursion

stack.push(head);Start traversal from head

while (!stack.isEmpty()) {Process nodes until stack empty

Node curr = stack.pop();Pop node to process

if (prev != null) {Link current node with previous

if (curr.next != null) {Push next node for later processing

if (curr.child != null) {Push child node to process next

curr.child = null;Remove child pointer after pushing

prev = curr;Update previous pointer

#include <stack>

class Node {
public:
    int val;
    Node* prev;
    Node* next;
    Node* child;
    Node(int _val) : val(_val), prev(nullptr), next(nullptr), child(nullptr) {}
};

class Solution {
public:
    Node* flatten(Node* head) {
        if (!head) return head;

        std::stack<Node*> stack;
        stack.push(head);
        Node* prev = nullptr;

        while (!stack.empty()) {
            Node* curr = stack.top();
            stack.pop();
            if (prev) {
                prev->next = curr;
                curr->prev = prev;
            }
            if (curr->next) {
                stack.push(curr->next);
            }
            if (curr->child) {
                stack.push(curr->child);
                curr->child = nullptr;
            }
            prev = curr;
        }

        return head;
    }
};

// main() omitted for brevity

Line Notes

if (!head) return head;Handle empty list edge case

std::stack<Node*> stack;Stack to simulate recursion

stack.push(head);Start from head node

while (!stack.empty()) {Process nodes until stack empty

Node* curr = stack.top();Pop node to process

if (prev) {Link current node with previous

if (curr->next) {Push next node for later processing

if (curr->child) {Push child node to process next

curr->child = nullptr;Remove child pointer after pushing

prev = curr;Update previous pointer

class Node {
    constructor(val, prev = null, next = null, child = null) {
        this.val = val;
        this.prev = prev;
        this.next = next;
        this.child = child;
    }
}

var flatten = function(head) {
    if (!head) return head;

    const stack = [head];
    let prev = null;

    while (stack.length > 0) {
        const curr = stack.pop();
        if (prev) {
            prev.next = curr;
            curr.prev = prev;
        }
        if (curr.next) {
            stack.push(curr.next);
        }
        if (curr.child) {
            stack.push(curr.child);
            curr.child = null;
        }
        prev = curr;
    }

    return head;
};

// Example usage omitted for brevity

Line Notes

if (!head) return head;Return immediately if list is empty

const stack = [head];Initialize stack with head node

while (stack.length > 0) {Process nodes until stack empty

const curr = stack.pop();Pop node to process in DFS order

if (prev) {Link current node with previous

if (curr.next) {Push next node for later processing

if (curr.child) {Push child node to process next

curr.child = null;Remove child pointer after pushing

prev = curr;Update previous pointer

⏱

Complexity

TimeO(n)

SpaceO(n) due to explicit stack in worst case

Each node is visited once; stack size can grow up to n in worst case of deep nesting.

💡 For n=1000 nodes, this means about 1000 operations and stack size up to 1000 in worst case.

Interview Verdict: Accepted and more robust than recursion for deep nesting

This approach avoids recursion limits and is preferred in interviews for large inputs.

🧠

In-Place Iterative Flattening Without Extra Stack

💡 This approach uses pointer manipulation to flatten the list in place by iterating and splicing child lists directly, saving space by not using an explicit stack.

Intuition

Iterate through the list; when a child is found, splice the entire child list between current node and next node, then continue iteration.

Algorithm

1. Start from head and iterate through the list.
2. When a node with a child is found, find the tail of the child list.
3. Connect the tail's next pointer to the current node's next node if it exists.
4. Splice the child list between current node and next node, update pointers accordingly.
5. Remove the child pointer and continue iteration from the current node's next.

💡 The key is carefully updating pointers to maintain list integrity while flattening in place.

</>

Code

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

def flatten(head):
    curr = head
    while curr:
        if curr.child:
            child = curr.child
            # Find tail of child list
            tail = child
            while tail.next:
                tail = tail.next
            # Connect tail to curr.next
            if curr.next:
                tail.next = curr.next
                curr.next.prev = tail
            # Connect curr to child
            curr.next = child
            child.prev = curr
            curr.child = None
        curr = curr.next
    return head

# Driver code omitted for brevity

Line Notes

curr = headStart iteration from head

while curr:Traverse the list sequentially

if curr.child:Process child list when found

tail = childFind tail of child list to connect next nodes

while tail.next:Traverse to end of child list

if curr.next:Connect tail to next node if exists

curr.next = childSplice child list after current node

child.prev = currMaintain backward link

curr.child = NoneRemove child pointer after splicing

curr = curr.nextMove to next node

class Node {
    public int val;
    public Node prev;
    public Node next;
    public Node child;

    public Node(int val) {
        this.val = val;
    }
}

public class Solution {
    public Node flatten(Node head) {
        Node curr = head;
        while (curr != null) {
            if (curr.child != null) {
                Node child = curr.child;
                Node tail = child;
                while (tail.next != null) {
                    tail = tail.next;
                }
                if (curr.next != null) {
                    tail.next = curr.next;
                    curr.next.prev = tail;
                }
                curr.next = child;
                child.prev = curr;
                curr.child = null;
            }
            curr = curr.next;
        }
        return head;
    }

    // Main method omitted for brevity
}

Line Notes

Node curr = head;Initialize current pointer at head

while (curr != null) {Iterate through list nodes

if (curr.child != null) {Process child list when found

Node tail = child;Find tail of child list

while (tail.next != null) {Traverse to end of child list

if (curr.next != null) {Connect tail to next node if exists

curr.next = child;Splice child list after current node

child.prev = curr;Maintain backward link

curr.child = null;Remove child pointer after splicing

curr = curr.next;Move to next node

class Node {
public:
    int val;
    Node* prev;
    Node* next;
    Node* child;
    Node(int _val) : val(_val), prev(nullptr), next(nullptr), child(nullptr) {}
};

class Solution {
public:
    Node* flatten(Node* head) {
        Node* curr = head;
        while (curr) {
            if (curr->child) {
                Node* child = curr->child;
                Node* tail = child;
                while (tail->next) {
                    tail = tail->next;
                }
                if (curr->next) {
                    tail->next = curr->next;
                    curr->next->prev = tail;
                }
                curr->next = child;
                child->prev = curr;
                curr->child = nullptr;
            }
            curr = curr->next;
        }
        return head;
    }
};

// main() omitted for brevity

Line Notes

Node* curr = head;Start iteration from head

while (curr) {Traverse list nodes

if (curr->child) {Process child list when found

Node* tail = child;Find tail of child list

while (tail->next) {Traverse to end of child list

if (curr->next) {Connect tail to next node if exists

curr->next = child;Splice child list after current node

child->prev = curr;Maintain backward link

curr->child = nullptr;Remove child pointer after splicing

curr = curr->next;Move to next node

class Node {
    constructor(val, prev = null, next = null, child = null) {
        this.val = val;
        this.prev = prev;
        this.next = next;
        this.child = child;
    }
}

var flatten = function(head) {
    let curr = head;
    while (curr) {
        if (curr.child) {
            let child = curr.child;
            let tail = child;
            while (tail.next) {
                tail = tail.next;
            }
            if (curr.next) {
                tail.next = curr.next;
                curr.next.prev = tail;
            }
            curr.next = child;
            child.prev = curr;
            curr.child = null;
        }
        curr = curr.next;
    }
    return head;
};

// Example usage omitted for brevity

Line Notes

let curr = head;Initialize current pointer at head

while (curr) {Iterate through list nodes

if (curr.child) {Process child list when found

let tail = child;Find tail of child list

while (tail.next) {Traverse to end of child list

if (curr.next) {Connect tail to next node if exists

curr.next = child;Splice child list after current node

child.prev = curr;Maintain backward link

curr.child = null;Remove child pointer after splicing

curr = curr.next;Move to next node

⏱

Complexity

TimeO(n^2) in worst case

SpaceO(1) extra space

Finding tail of child list can take O(k) time repeatedly, leading to O(n^2) in worst case of many small child lists.

💡 For n=1000 nodes with many children, this approach may do up to 1,000,000 operations due to repeated tail searches.

Interview Verdict: Accepted but inefficient for large inputs with many children

This approach saves space but can be slow due to repeated tail traversals; better for small or shallow lists.

📊

All Approaches - One-Glance Tradeoffs

💡 In most interviews, the iterative DFS with stack approach balances clarity, robustness, and efficiency, making it the best choice to code.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (Pure Recursion)	O(n)	O(n) recursion stack	Yes (deep recursion)	N/A	Mention only - never code due to stack overflow risk
2. Iterative DFS Using Stack	O(n)	O(n) explicit stack	No	N/A	Preferred approach to code in interviews
3. In-Place Iterative Flattening Without Extra Stack	O(n^2) worst case	O(1)	No	N/A	Good to mention, but avoid coding due to inefficiency

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before interviews. Start by clarifying the problem, then explain the brute force approach, followed by iterative improvements. Practice coding and testing each approach.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Describe the brute force recursive approach and its limitations.Step 3: Explain the iterative DFS approach using a stack to avoid recursion limits.Step 4: Discuss the in-place iterative approach and tradeoffs.Step 5: Code the preferred approach and test with edge cases.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 10min → Test: 7min. Total ~25min

What the Interviewer Tests

The interviewer tests your understanding of linked list pointer manipulation, recursion vs iteration, handling nested structures, and ability to optimize space/time tradeoffs.

Common Follow-ups

• How would you handle very deep nesting without recursion? → Use iterative DFS with stack.
• Can you flatten the list in place without extra space? → Yes, but watch for tail traversal cost.

💡 These follow-ups check your ability to optimize recursion and space usage, common interview extensions.

🔍

Pattern Recognition

When to Use

1) When a linked list has nested child pointers, 2) When flattening requires depth-first traversal, 3) When pointer manipulation is needed, 4) When recursion or stack can be used to manage nested structures.

Signature Phrases

multilevel doubly linked listflatten the listchild pointerdepth-first traversal

NOT This Pattern When

This is not a simple linked list traversal or sorting problem; it requires handling nested pointers and flattening.

Similar Problems

Flatten Binary Tree to Linked List - similar flattening of nested structuresFlatten Nested List Iterator - similar depth-first flattening of nested lists

Practice

1. Given the following Python code snippet implementing the AllOne data structure, what is the output of getMaxKey() after these operations?

all_one = AllOne() all_one.inc('apple') all_one.inc('banana') all_one.inc('apple') all_one.dec('banana') print(all_one.getMaxKey())

easy

A. "" (empty string)

B. "apple"

C. "banana"

D. Raises an exception

Solution

1. Step 1: Trace increments and decrements

   After inc('apple') twice, 'apple' count = 2. 'banana' incremented once then decremented once, so removed.

2. Step 2: Check getMaxKey()

   Max count bucket is 2 with 'apple'. So getMaxKey() returns 'apple'.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Only 'apple' remains with max count 2 [OK]

Hint: Max key is the one with highest count after updates [OK]

Common Mistakes:

• Forgetting to remove 'banana' after dec to zero count

2. Consider the following code snippet implementing the optimal approach to copy a list with random pointers. Given the input list:
Node1(val=1) -> Node2(val=2) -> Node3(val=3), where Node1.random = Node3, Node2.random = Node1, Node3.random = null.
After Step 2 (assigning random pointers), what is the value of copy_curr.random.val when copy_curr points to the copied node of Node2?

easy

A. None (null)

B. 3

C. 1

D. 2

Solution

1. Step 1: Trace Step 1 (interleaving nodes)

   Original list: 1 -> 2 -> 3 becomes 1 -> 1' -> 2 -> 2' -> 3 -> 3'.

2. Step 2: Trace Step 2 (assign random pointers)

   Node2.random = Node1, so copied Node2 (2') random = Node1.next = 1'. Thus, copy_curr.random.val = 1.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   copy_curr.random points to copied Node1 with val=1 [OK]

Hint: Copied node's random points to original.random.next [OK]

Common Mistakes:

• Confusing original and copied nodes when assigning random pointers
• Off-by-one errors in stepping through interleaved list
• Assuming random pointer points to original node's val

3. Given the following Python code for merging two skylines, and the inputs left = [[1, 3], [5, 0]] and right = [[2, 4], [6, 0]], what is the merged skyline returned by mergeSkylines(left, right)?

easy

A. [[1, 3], [2, 4], [5, 0], [6, 0]]

B. [[1, 3], [5, 0], [6, 0]]

C. [[1, 3], [2, 4], [4, 0], [6, 0]]

D. [[1, 3], [2, 4], [4, 0], [5, 0], [6, 0]]

Solution

1. Step 1: Trace first iterations of the merge loop

   Compare left[0]=(1,3) and right[0]=(2,4): 1 < 2, so x=1, h1=3, h2=0, max_h=3 -> merged=[[1,3]]

2. Step 2: Next iterations and final merge

   Next left[1]=(5,0), right[0]=(2,4): 2 < 5, x=2, h2=4, h1=3, max_h=4 -> merged=[[1,3],[2,4]]; then right[1]=(6,0) vs left[1]=(5,0): 5 < 6, x=5, h1=0, h2=4, max_h=4 (no change), then x=6, h2=0, max_h=0 -> merged=[[1,3],[2,4],[4,0],[5,0],[6,0]] after extending remaining points.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Stepwise max height updates match merged skyline [OK]

Hint: Track h1 and h2 updates carefully during merge [OK]

Common Mistakes:

• Off-by-one in indices
• Missing key points when heights change

4. Identify the bug in the following LRU Cache implementation snippet that causes incorrect eviction behavior when capacity is exceeded:

def put(self, key: int, value: int) -> None:
    if key in self.cache:
        self._remove(self.cache[key])
    node = Node(key, value)
    self._add(node)
    self.cache[key] = node
    if len(self.cache) > self.capacity:
        lru = self.head.next  # Bug here
        self._remove(lru)
        del self.cache[lru.key]

medium

A. Evicting the node at head.next instead of tail.prev

B. Removing node from cache before adding new node

C. Not updating the cache dictionary after eviction

D. Not checking if capacity is zero before eviction

Solution

1. Step 1: Understand eviction logic

   Eviction must remove the least recently used node, which is at tail.prev, not head.next.

2. Step 2: Identify bug

   Code incorrectly evicts head.next, which is the most recently used node, causing wrong eviction.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Evicting head.next breaks LRU policy, must evict tail.prev [OK]

Hint: LRU node is at tail.prev, not head.next [OK]

Common Mistakes:

• Evicting MRU instead of LRU
• Forgetting to delete from cache dict
• Not handling zero capacity

5. Consider the following buggy code snippet for merging two skylines. Which line contains the subtle bug that can cause incorrect skyline output?

medium

A. Line where merged.append([x, max_h]) is called unconditionally

B. Line where x, h1 = left[i] inside first if

C. Line where max_h is computed with max(h1, h2)

D. Line where i and j are incremented in the else block

Solution

1. Step 1: Identify difference from correct code

   The bug is that merged.append is called every iteration without checking if height changed, causing redundant points.

2. Step 2: Understand impact of redundant points

   Appending points even when max_h equals previous height leads to unnecessary key points, failing correctness checks.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Correct code appends only if height changes [OK]

Hint: Appending only on height change avoids redundant points [OK]

Common Mistakes:

• Appending every iteration regardless of height change
• Incorrect pointer increments