Miscellaneous

26. Copy List with Random Pointer

1. Problem Description: The problem "Copy List with Random Pointer" on LeetCode can be found at the following link:

• https://leetcode.com/problems/copy-list-with-random-pointer/

The problem asks us to deep copy a linked list with each node containing an additional pointer to a random node within the same list. We need to create a new independent clone of the linked list.

1. Optimized Java Code:

class Node {
    int val;
    Node next;
    Node random;

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

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

        // Step 1: Create a new node for each existing node and insert it between the existing nodes
        Node current = head;
        while (current != null) {
            Node newNode = new Node(current.val);
            newNode.next = current.next;
            current.next = newNode;
            current = newNode.next;
        }

        // Step 2: Set the random pointers for the new nodes based on the original node's random pointers
        current = head;
        while (current != null) {
            if (current.random != null) {
                current.next.random = current.random.next;
            }
            current = current.next.next;
        }

        // Step 3: Separate the original and cloned nodes into two separate lists
        current = head;
        Node clonedHead = head.next;
        Node clonedCurrent = clonedHead;
        while (current != null) {
            current.next = current.next.next;
            if (clonedCurrent.next != null) {
                clonedCurrent.next = clonedCurrent.next.next;
            }
            current = current.next;
            clonedCurrent = clonedCurrent.next;
        }

        return clonedHead;
    }
}

1. Algorithm Explanation and Interview Tips:

• The problem can be solved using the "copy - insert - separate" approach.

• In this approach, we first copy each node in the original linked list and insert it between the existing nodes. This allows us to maintain the original order of nodes while creating a new, independent clone.

• We then set the random pointers of the new nodes by referencing the random nodes of the original nodes.

• Finally, we separate the original and cloned nodes into two separate lists by restoring the original next pointers and adjusting the next pointers of the cloned nodes.

During an interview, it is crucial to explain the algorithm thoroughly and provide a clear step-by-step explanation. Emphasize the importance of maintaining the order, as well as the need to handle the random pointers correctly for a successful clone. Going through the code and discussing the time and space complexity will also showcase your understanding of the problem and your ability to optimize the solution.

27. LRU Cache

1. Problem Description: The LRU Cache problem is a commonly asked interview question in software engineering interviews. The problem requires implementing a data structure that supports two operations - get and put. The get operation retrieves the value corresponding to a key, and the put operation inserts or updates a key-value pair. The cache has a fixed capacity, and if the number of entries exceeds the capacity, the least recently used entry should be evicted.

Problem Link: https://leetcode.com/problems/lru-cache/

1. Java Code (Optimized solution with detailed comments): Below is the optimized Java code for the LRU Cache problem with detailed comments explaining the logic and approach used.

class LRUCache {
    private Map<Integer, Node> cache; // Map to store key-value pairs
    private int capacity; // Capacity of the cache
    private Node head; // Head node of the doubly linked list
    private Node tail; // Tail node of the doubly linked list

    class Node {
        int key;
        int value;
        Node prev;
        Node next;
    }

    public LRUCache(int capacity) {
        this.cache = new HashMap<>();
        this.capacity = capacity;
        head = new Node(); // Create a dummy head node
        tail = new Node(); // Create a dummy tail node
        head.next = tail; // Connect head to tail
        tail.prev = head; // Connect tail to head
    }

    public int get(int key) {
        if (cache.containsKey(key)) {
            Node node = cache.get(key); // Fetch the corresponding node
            moveToHead(node); // Move the accessed node to the head
            return node.value;
        }
        return -1; // Key not present in cache, return -1
    }

    public void put(int key, int value) {
        if (cache.containsKey(key)) {
            Node node = cache.get(key); // Fetch the corresponding node
            node.value = value; // Update the node's value
            moveToHead(node); // Move the updated node to the head
        } else {
            Node newNode = new Node();
            newNode.key = key;
            newNode.value = value;
            cache.put(key, newNode); // Add the new key-value entry to the cache
            addToHead(newNode); // Add the new node to the head of the doubly linked list

            if (cache.size() > capacity) {
                Node tailNode = removeTail(); // Evict the least recently used (tail) node
                cache.remove(tailNode.key); // Remove the evicted node from the cache
            }
        }
    }

    private void addToHead(Node node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }

    private void removeNode(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void moveToHead(Node node) {
        removeNode(node);
        addToHead(node);
    }

    private Node removeTail() {
        Node tailNode = tail.prev;
        removeNode(tailNode);
        return tailNode;
    }
}

1. Algorithm and Thought Process: The LRU Cache problem can be solved using a combination of a HashMap and a doubly linked list. The HashMap will be used for quick access to the nodes, and the doubly linked list will be used to keep track of the least recently used nodes.

In the constructor, we initialize the cache as a HashMap, set the capacity, and create dummy head and tail nodes for the doubly linked list. We connect the head and tail nodes to form an empty list.

The get operation checks if the key is present in the cache. If it is, we retrieve the corresponding node from the cache, move it to the head of the doubly linked list (since it is the most recently used), and return its value. If the key is not present, we return -1.

The put operation first checks if the key is already present in the cache. If it is, we update the node's value, move it to the head of the doubly linked list, and continue. If the key is not present, we create a new node with the key and value, add it to the head of the doubly linked list, and put it in the cache. If the cache size exceeds the capacity, we remove the least recently used (tail) node from the doubly linked list and the cache.

To maintain the order of recently used nodes, we define helper methods - addToHead, removeNode, moveToHead, and removeTail. These methods handle the addition, removal, and movement of nodes within the doubly linked list.

During an interview, it is important to explain the algorithm and how it is implemented. Emphasize the time and space complexity of the solution and discuss any trade-offs that were made. Additionally, mentioning alternative approaches and their pros and cons can showcase a deeper understanding of the problem.

28. Design HashMap

1. Problem description: The problem is to design a HashMap data structure from scratch. The task is to implement the following four methods of the HashMap class:

• put(key, value): Insert a key-value pair into the HashMap. If the key already exists, update its value.

• get(key): Return the value associated with a given key. If the key does not exist, return -1.

• remove(key): Remove the key-value pair from the HashMap. If the key does not exist, do nothing.

Problem link: Design HashMap

1. Optimized Java code for Design HashMap (with detailed comments):

class MyHashMap {
    
    // A nested class to represent the nodes of the HashMap
    class Node {
        int key;
        int value;
        Node next;
        
        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
    
    private final int SIZE = 10000; // The size of the HashMap array
    private Node[] array; // Array to store the nodes
    
    /** Initialize your data structure here. */
    public MyHashMap() {
        array = new Node[SIZE];
    }
    
    /** value will always be non-negative. */
    public void put(int key, int value) {
        int index = getIndex(key); // Get the index in the array for the given key
        Node prev = find(index, key); // Find the previous node of the given key
        
        // If a node with the key already exists, update its value
        if (prev.next != null) {
            prev.next.value = value;
        } else {
            prev.next = new Node(key, value); // Create a new node with the key-value pair
        }
    }
    
    /** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
    public int get(int key) {
        int index = getIndex(key); // Get the index in the array for the given key
        Node prev = find(index, key); // Find the previous node of the given key
        
        // If a node with the key exists, return its value
        if (prev.next != null) {
            return prev.next.value;
        }
        
        return -1; // If no node exists with the key, return -1
    }
    
    /** Removes the mapping of the specified value key if this map contains a mapping for the key */
    public void remove(int key) {
        int index = getIndex(key); // Get the index in the array for the given key
        Node prev = find(index, key); // Find the previous node of the given key
        
        // If a node with the key exists, remove it
        if (prev.next != null) {
            prev.next = prev.next.next;
        }
    }
    
    // Helper method to get the index in the array for a given key
    private int getIndex(int key) {
        return key % SIZE;
    }
    
    // Helper method to find the previous node of a given key
    private Node find(int index, int key) {
        if (array[index] == null) {
            array[index] = new Node(-1, -1);
            return array[index];
        }
        
        Node prev = array[index];
        while (prev.next != null && prev.next.key != key) {
            prev = prev.next;
        }
        
        return prev;
    }
}

1. Detailed description of the algorithm and interview thought process:

• The HashMap is implemented as an array with a fixed size of 10000. Each element of the array represents a LinkedList of nodes, where each node contains a key-value pair.

• To store a key-value pair in the HashMap, the put() method is used. It follows the following steps:

  • Calculate the index in the array for the given key using the getIndex() helper method.

  • Find the previous node of the given key using the find() helper method. If there is no previous node, create one with a key-value pair.

  • If a previous node is found, update its value with the given value. If no previous node is found, create a new node with the key-value pair.

• To retrieve a value from the HashMap, the get() method is used. It follows the following steps:

  • Calculate the index in the array for the given key using the getIndex() helper method.

  • Find the previous node of the given key using the find() helper method. If a previous node is found, return its value. If no previous node is found, return -1.

• To remove a key-value pair from the HashMap, the remove() method is used. It follows the following steps:

  • Calculate the index in the array for the given key using the getIndex() helper method.

  • Find the previous node of the given key using the find() helper method. If a previous node is found, remove the node by updating the previous node's next reference.

• During an interview, it is important to understand the problem requirements and constraints before starting to solve it. Understanding the problem statement and requirements helps in designing an appropriate data structure and algorithm. In this case, the HashMap is implemented using an array of linked lists. The getIndex() method helps in distributing the key-value pairs evenly across the array. The find() method helps in finding the previous node of a given key, which is essential for updating, retrieving, and removing key-value pairs efficiently. It is also important to handle edge cases, like key-value pairs that do not exist in the HashMap or when removing a key-value pair that is not present. Implementing and testing each method individually before proceeding to the next one helps in ensuring correctness.

29. Flatten a Multilevel Doubly Linked List

1. Problem Description: The problem "Flatten a Multilevel Doubly Linked List" asks us to flatten a given multilevel doubly linked list. A multilevel doubly linked list is a linked list where each node has a value, a next pointer, and a child pointer. The child pointer can connect to another doubly linked list. Our task is to flatten the multilevel linked list in such a way that all the nodes appear in a single-level linked list (in the same order as they appeared in the input list), with all the child pointers set to null.

Problem Link: https://leetcode.com/problems/flatten-a-multilevel-doubly-linked-list/

1. Optimized Java Code: Here is the optimized Java code for the problem "Flatten a Multilevel Doubly Linked List" with detailed comments:

// Definition for a Node.
class Node {
    public int val;
    public Node prev;
    public Node next;
    public Node child;
};

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

1. Algorithm and Interview Approach:

The algorithm to solve this problem is straightforward. We need to iterate through the linked list and whenever we encounter a node with a child pointer, we need to flatten the child linked list and connect the flattened list to the current node.

Here is a step-by-step breakdown of the algorithm:

1. If the given head node is null, return null.

2. Start with a current pointer initialized to the head node.

3. Iterate through the linked list using the current pointer.

4. For each node:

   • Check if the current node has a child pointer.

   • If the child pointer is null, move to the next node (curr = curr.next).

   • If the child pointer is not null:

     • Store the child node in a separate variable (child = curr.child).

     • Find the last node in the child linked list by iterating through the child nodes (while loop).

     • Connect the last node of the child linked list to the next node of the current node (child.next = curr.next).

     • If curr.next is not null, update the previous pointer of the next node (curr.next.prev = child).

     • Connect the current node to the child linked list by updating the next and previous pointers (curr.next = curr.child, curr.child.prev = curr).

     • Set the child pointer of the current node to null (curr.child = null).

5. After iterating through the entire linked list, return the head.

During an interview, it is important to think through the problem by discussing possible approaches and analyzing time and space complexity. The above approach has a time complexity of O(N), where N is the number of nodes in the linked list, as we iterate through each node only once. The space complexity is O(1) as we utilize only a constant amount of additional space.

It is also crucial to write clean and readable code with proper variable names and comments to enhance code understanding. This helps the interviewer follow the thought process and evaluate the problem-solving skills.

30. Split Linked List in Parts

1. Problem Description: Given a singly linked list and an integer k, you need to split the linked list into k parts evenly while maintaining the relative order of nodes in each part. If there are leftover nodes after splitting, the first few parts should have one more node than the last few parts.

Link to the problem on LeetCode: Split Linked List in Parts

1. Optimized Java Code:

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode[] splitListToParts(ListNode root, int k) {
        // Step 1: Find the length of the linked list
        int length = 0;
        ListNode current = root;
        while (current != null) {
            length++;
            current = current.next;
        }
        
        // Step 2: Calculate the base size and the size of the extra nodes
        int baseSize = length / k;
        int extra = length % k;
        
        // Step 3: Split the linked list into k parts
        ListNode[] result = new ListNode[k];
        current = root;
        for (int i = 0; i < k && current != null; i++) {
            result[i] = current;
            int size = baseSize + (extra > 0 ? 1 : 0); // calculate size of each part
            extra--;
            
            // move current pointer to the end of each part
            for (int j = 0; j < size - 1; j++) {
                current = current.next;
            }
            
            // break the link between parts
            ListNode next = current.next;
            current.next = null;
            current = next;
        }
        
        return result;
    }
}

1. Detailed Description and Algorithm:

• In this problem, we need to split a linked list into k parts while maintaining the relative order of nodes.

• The first step is to determine the length of the linked list. We can do this by iterating through the linked list and counting the number of nodes.

• Next, we calculate the base size, which is the number of nodes that each part should have, and the number of extra nodes. The base size is obtained by dividing the length by k, and the extra is obtained by taking the modulo of length and k.

• We initialize an array 'result' of size k to store the head nodes of each part.

• We iterate through the linked list again, this time splitting it into k parts. For each part, we set the current node as the head of that part (result[i] = current).

• We calculate the size of each part, which is the base size plus one extra node if available. We then decrement the extra count.

• We move the current pointer to the end of the current part by iterating size - 1 times.

• After reaching the end of each part, we break the link between parts by setting the 'next' pointer of the current node to null.

• Finally, we return the 'result' array containing the head nodes of the splitted parts.

During the interview process, it's important to explain the algorithm step by step, mentioning the intuition behind each step, and discussing the time and space complexity of the solution. Additionally, you can provide examples and walk through the code to demonstrate how it works in practice.