Interview Preplinked-list-advancedmediumAmazonGoogleMicrosoft

Design Linked List (Full Implementation)

Choose your preparation mode4 modes available

Try It Solution Trace

Start learning this pattern below

Jump into concepts and practice - no test required

Recommended

Test this pattern10 questions across easy, medium, and hard to know if this pattern is strong

📋

Problem

Imagine building a custom playlist manager where songs can be added, removed, or retrieved at any position efficiently. Designing a linked list from scratch is the foundation for such dynamic data structures.

Design a singly linked list with the following functionalities: - get(index): Get the value of the index-th node in the linked list. If the index is invalid, return -1. - addAtHead(val): Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. - addAtTail(val): Append a node of value val to the last element of the linked list. - addAtIndex(index, val): Add a node of value val before the index-th node in the linked list. If index equals the length of the linked list, the node will be appended to the end. If index is greater than the length, the node will not be inserted. - deleteAtIndex(index): Delete the index-th node in the linked list, if the index is valid.

0 ≤ index ≤ 10^5All values will be in the range [1, 1000]At most 10^4 calls will be made to get, addAtHead, addAtTail, addAtIndex and deleteAtIndex.

Edge cases: get from empty list → returns -1addAtIndex with index greater than length → no insertiondeleteAtIndex with invalid index → no deletion

</>

IDE

class MyLinkedList:

class MyLinkedList:
    def __init__(self):
        # Initialize your data structure here.
        pass
    def get(self, index: int) -> int:
        pass
    def addAtHead(self, val: int) -> None:
        pass
    def addAtTail(self, val: int) -> None:
        pass
    def addAtIndex(self, index: int, val: int) -> None:
        pass
    def deleteAtIndex(self, index: int) -> None:
        pass

class MyLinkedList {
    public MyLinkedList() {
        // Initialize your data structure here.
    }
    public int get(int index) {
        return -1;
    }
    public void addAtHead(int val) {
    }
    public void addAtTail(int val) {
    }
    public void addAtIndex(int index, int val) {
    }
    public void deleteAtIndex(int index) {
    }
}

#include <iostream>
using namespace std;
class MyLinkedList {
public:
    MyLinkedList() {
        // Initialize your data structure here.
    }
    int get(int index) {
        return -1;
    }
    void addAtHead(int val) {
    }
    void addAtTail(int val) {
    }
    void addAtIndex(int index, int val) {
    }
    void deleteAtIndex(int index) {
    }
};

class MyLinkedList {
    constructor() {
        // Initialize your data structure here.
    }
    get(index) {
        return -1;
    }
    addAtHead(val) {
    }
    addAtTail(val) {
    }
    addAtIndex(index, val) {
    }
    deleteAtIndex(index) {
    }
}

0/9

Common Bugs to Avoid

Wrong: get returns -1 even for valid indicesIncorrect index validation or traversal logic stopping early.✅ Ensure traversal continues until index-th node is reached and check for None only after traversal.

Wrong: addAtIndex inserts node even when index > lengthMissing or incorrect boundary check for index in addAtIndex.✅ Add condition: if index > length, do not insert node.

Wrong: deleteAtIndex deletes node at invalid indexNo validation of index before deletion.✅ Check if index < length before deleting node.

Wrong: addAtTail causes TLE on large inputsTraversing entire list to add at tail causing O(n^2) complexity.✅ Maintain a tail pointer to add at tail in O(1) time.

Wrong: get returns wrong values after deleteAtIndexPointer updates after deletion are incorrect causing list corruption.✅ Update next pointers correctly and maintain list integrity after deletion.

✓

Test Cases

t1_01basic

Input["addAtHead(1)","addAtTail(3)","addAtIndex(1, 2)","get(1)","deleteAtIndex(1)","get(1)"]

Expected[null,null,null,2,null,3]

After adding 1 at head and 3 at tail, list is [1,3]. Adding 2 at index 1 makes list [1,2,3]. get(1) returns 2. Deleting index 1 removes 2, list becomes [1,3]. get(1) now returns 3.

t1_02basic

Input["addAtHead(5)","addAtHead(10)","addAtTail(15)","get(0)","get(2)","deleteAtIndex(1)","get(1)"]

Expected[null,null,null,10,15,null,15]

Start with empty list. addAtHead(5) -> [5], addAtHead(10) -> [10,5], addAtTail(15) -> [10,5,15]. get(0) returns 10, get(2) returns 15. deleteAtIndex(1) removes 5, list becomes [10,15]. get(1) returns 15.

Practice

(1/5)

1. You are given a singly linked list where each node contains a binary digit (0 or 1). The linked list represents a binary number with the head as the most significant bit. Which approach guarantees an optimal solution to convert this linked list to its decimal integer value?

easy

A. Iteratively accumulate the decimal value by shifting the current value left by 1 and OR-ing with the current node's bit.

B. Use a greedy approach to pick bits that maximize the decimal value at each step.

C. Traverse the list to build a string of bits, then parse the string as a binary number.

D. Apply dynamic programming to store intermediate decimal values for sublists.

3. Identify the bug in the following code snippet implementing the odd-even linked list rearrangement:

def oddEvenList(head):
    if not head or not head.next:
        return head
    odd = head
    even = head.next
    even_head = even
    while even and even.next:
        odd.next = even.next
        odd = odd.next
        even.next = odd.next
        even = even.next
    # Missing termination of even list
    odd.next = even_head
    return head

What is the consequence of the missing line and how to fix it?

medium

A. The function does not handle empty lists; fix by adding a check for head == None at the start

B. The odd pointer is not updated correctly inside the loop; fix by moving 'odd = odd.next' after even pointer updates

C. The even_head pointer is lost; fix by initializing even_head after the loop instead of before

D. The even list is not terminated with null, causing a cycle; fix by adding 'if even: even.next = None' before linking odd.next

Design Linked List (Full Implementation)

Start learning this pattern below

Practice

Solution

Step 1: Understand the problem constraints

Step 2: Identify the optimal approach

Final Answer:

Quick Check:

Solution

Step 1: Analyze Step 3 separation loop

Step 2: Identify fix

Final Answer:

Quick Check:

Solution

Step 1: Understand pointer termination

Step 2: Fix by terminating even list

Final Answer:

Quick Check:

Solution

Step 1: Understand cycle impact on weaving approach

Step 2: Identify necessary modification

Step 3: Evaluate other options

Final Answer:

Quick Check:

Solution

Step 1: Understand node reuse implications

Step 2: Modify algorithm to track visited nodes

Step 3: Evaluate other options

Final Answer:

Quick Check: