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. You need to design a data structure that supports adding intervals, removing intervals, and querying whether a given range is fully covered by the added intervals. Which approach guarantees efficient updates and queries with logarithmic time complexity per operation?

easy

A. Use a balanced binary search tree (e.g., TreeMap) to store and merge intervals, enabling logarithmic time operations.

B. Use a brute force list of intervals and scan all intervals for each operation.

C. Use dynamic programming to precompute coverage for all possible ranges.

D. Use a greedy algorithm that always merges intervals only when queried.

Solution

1. Step 1: Understand the problem requirements

   The data structure must support add, remove, and query operations on intervals efficiently.

2. Step 2: Evaluate approaches

   Brute force scanning is O(n) per operation, which is inefficient. DP is not suitable for dynamic interval updates. Greedy merging only on query delays merging and leads to inefficient queries. Balanced BST with interval merging maintains sorted intervals and merges overlapping ones, supporting O(log n) operations.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Balanced BST with merging -> O(log n) per operation [OK]

Hint: Balanced BST with merging enables efficient interval operations [OK]

Common Mistakes:

• Thinking DP or greedy solves dynamic interval updates efficiently

2. Given the following code snippet for SnapshotArray, what is the output of snapshotArr.get(0, 0) after executing all lines shown?

snapshotArr = SnapshotArray(3)
snapshotArr.set(0, 5)
snap_id = snapshotArr.snap()
snapshotArr.set(0, 6)
print(snapshotArr.get(0, 0))

easy

A. 5

B. 6

C. 0

D. Error due to invalid snap_id

Solution

1. Step 1: Trace set and snap operations

   Initially, data[0] = [(-1,0)]. After set(0,5), data[0] = [(-1,0),(0,5)] because snap_id=0. Then snap() increments snap_id to 1 and returns 0. Then set(0,6) appends (1,6) to data[0].

2. Step 2: Trace get(0,0)

   For snap_id=0, bisect_right finds insertion point for (0,inf) in data[0] = [(-1,0),(0,5),(1,6)]. It returns index 2, so i=1. data[0][1] = (0,5), so get returns 5.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Value at snap 0 is 5, not the later set 6 [OK]

Hint: Get returns value at or before snap_id using binary search [OK]

Common Mistakes:

• Returning latest value ignoring snap_id
• Off-by-one in bisect index

3. What is the time complexity of the get and put operations in an optimal LRU Cache implementation using a hash map and a doubly linked list with capacity n?

medium

A. O(n) for get and put due to list traversal

B. O(1) amortized for get and put using hash map and doubly linked list

C. O(log n) due to balancing the linked list

D. O(1) for get but O(n) for put due to eviction

Solution

1. Step 1: Analyze get operation

   Hash map provides O(1) access to node; doubly linked list allows O(1) removal and insertion to update usage order.

2. Step 2: Analyze put operation

   Insertion involves hash map update and linked list insertion/removal, all O(1). Eviction removes tail node in O(1).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Both get and put run in constant time using combined data structures [OK]

Hint: Hash map + doubly linked list -> O(1) get and put [OK]

Common Mistakes:

• Assuming list removal is O(n)
• Confusing amortized with worst-case
• Thinking linked list needs balancing

4. Suppose the Twitter design is extended so that users can post the same tweet multiple times (tweet reuse allowed). Which modification to the optimal approach is necessary to correctly handle this scenario?

hard

A. Allow multiple TweetNode instances with the same tweetId but different timestamps in the linked list and heap.

B. Use a hash set to track unique tweetIds per user to avoid duplicates in the feed.

C. Modify the heap to store tweetIds only once, ignoring repeated posts of the same tweetId.

D. Disallow posting duplicate tweetIds by rejecting posts with existing tweetIds.

Solution

1. Step 1: Understand tweet reuse impact

   Allowing duplicate tweetIds means multiple posts with same id but different times must be treated as distinct tweets.

2. Step 2: Adjust data structures

   Each post creates a new TweetNode with unique timestamp; heap and linked lists handle duplicates naturally by time ordering.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Multiple nodes with same tweetId but different times must be stored separately [OK]

Hint: Treat each post as unique by timestamp, even if tweetId repeats [OK]

Common Mistakes:

• Trying to deduplicate tweets in feed incorrectly
• Rejecting duplicate posts unnecessarily

5. Suppose the data stream allows duplicate numbers to be removed after insertion, requiring support for removeNum(num). Which modification to the balanced two heaps approach is necessary to maintain correct median retrieval?

hard

A. Use a balanced binary search tree instead of heaps to allow efficient removals.

B. Ignore removals and only add numbers, as removals break the heap structure.

C. Rebuild both heaps from scratch after every removal to maintain heap properties.

D. Add a delayed deletion map to mark elements for lazy removal and prune heaps during addNum and findMedian.

Solution

1. Step 1: Understand removal challenges

   Heaps do not support efficient arbitrary removals, so direct removal breaks heap properties.

2. Step 2: Use lazy deletion

   Maintain a delayed deletion map to mark elements for removal and prune them lazily during heap operations, preserving heap structure and efficiency.

3. Step 3: Avoid costly rebuilds

   Rebuilding heaps on every removal is inefficient; ignoring removals is incorrect.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Lazy deletion with pruning maintains correctness and efficiency [OK]

Hint: Lazy deletion map enables efficient removals in heaps [OK]

Common Mistakes:

• Rebuilding heaps on every removal
• Ignoring removals breaks correctness