Wednesday, July 29, 2015

Sort List | Leetcode

Sort a linked list in O(n log n) time using constant space complexity.

---

Solution: Probably the only way to do this using constant memory is to use merge sort. We use the technique of finding the middle of the linked list using a slow pointer and a fast pointer. So we can break down a linked lists into two parts, and then sort each part and merge them together.
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null) return null;
        if (head.next == null) return head;
        
        // Find the middle of the linked list.
        ListNode slow = head;
        ListNode fast = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        
        // Break up the linked list into two parts.
        ListNode first = head;
        ListNode second = slow.next;
        slow.next = null;
        
        // Sort each part separately.
        first = sortList(first);
        second = sortList(second);
        
        // Merge the two linked lists.
        ListNode curr = null;
        while (first != null || second != null) {
            ListNode node;
            if (first == null) {
                node = second;
                second = second.next;
            } else if (second == null) {
                node = first;
                first = first.next;
            } else if (first.val < second.val) {
                node = first;
                first = first.next;
            } else {
                node = second;
                second = second.next;
            }
            if (curr == null) {
                head = curr = node;
            } else {
                curr.next = node;
                curr = node;
            }
        }
        
        return head;
    }
}

Insertion Sort List | Leetcode

Sort a linked list using insertion sort.

---

Solution: For each node in the given linked list, insert it in order into a new linked list. Not easy to get the logic right the first time one writes the code.
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode insertionSortList(ListNode head) {
        if (head == null) return null;

        // Start off a new list reusing the same nodes.        
        ListNode newHead = head;
        head = head.next;
        newHead.next = null;
        
        // Insert each node in order.
        while (head != null) {
            // head.next will be overwritten, so save it first.
            ListNode next = head.next;
            newHead = insertInOrder(newHead, head);
            head = next;
        }
        
        return newHead;
    }
    
    private ListNode insertInOrder(ListNode head, ListNode curr) {
        // Find position at which we should insert curr.
        ListNode prev = null;
        ListNode node = head;
        while (node != null && curr.val > node.val) {
            prev = node;
            node = node.next;
        }
        
        // We might need to insert as the head of the list.
        if (prev == null) {
            curr.next = head;
            return curr;
        }
        
        // Insert as per normal inside the list.
        curr.next = prev.next;
        prev.next = curr;
        return head;
    }
}

Friday, July 24, 2015

LRU Cache | Leetcode

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.

set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

---

Solution: The key here is to choose a data structure, or a group of data structures, that will support an efficient implementation of the LRU cache.

For a cache get and set, we need to support an O(1) time lookup and removal of a given key, which basically means that we would need a hashmap. We also need a way to quickly remove the key from an ordered list and then move it to the front of the ordered list. For this, we can use a doubly-linked list for quick insertions and removals when given any node. The insertion and removal should also require only O(1) time, which means that we need to use the hashmap to point to the doubly-linked list node, and not just to the integer value.

For the doubly-linked list, we need to maintain both the head pointer and tail pointer, so that we can quickly insert at the front and also remove the tail node without needing to go through the entire list.

We also need to maintain the number of elements in the LRU cache so that we can remove the oldest node when we reach the maximum capacity. We use the Java hashmap to maintain the size so that we do not have to roll our own variable.

Most of the code turns out to be manipulation operations around the doubly-linked list. The other parts are relatively straightforward.
public class LRUCache {
    
    private static class ListNode {
        int key;
        int value;
        ListNode prev;
        ListNode next;
        ListNode(int key, int value) { this.key = key; this.value = value; }
    }

    private final int capacity;
    private ListNode head;
    private ListNode tail;
    private Map<Integer, ListNode> map = new HashMap<>();
    
    public LRUCache(int capacity) {
        this.capacity = capacity;
    }
    
    public int get(int key) {
        ListNode node = map.get(key);
        if (node == null) return -1;
        
        // Move this node to the head of the list.
        if (node != head) {
            // (head != tail) must be true at this point.
            node.prev.next = node.next;
            if (tail == node) {
                tail = node.prev;
            } else {
                node.next.prev = node.prev;
            }
            node.prev = null;
            node.next = head;
            head.prev = node;
            head = node;
        }
        
        return node.value;
    }
    
    public void set(int key, int value) {
        // Check existing node for key.
        ListNode node = map.get(key);
        
        if (node != null) {
            // Reuse this node.
            node.value = value;
                
            // Short-circuit when key is already the head node.
            if (node == head) return;
            
            // Remove the old node for key.
            node.prev.next = node.next;
            if (tail == node) {
                tail = node.prev;
            } else {
                node.next.prev = node.prev;
            }
        } else if (map.size() == capacity) {
            // Remove the last node if we have reached capacity.
            map.remove(tail.key);
            
            // Reuse the tail node.
            node = tail;
            node.key = key;
            node.value = value;
            map.put(key, node);

            // Short-circuit if this is the only node in the list.
            if (head == tail) return;
            
            // Remove tail node.
            tail = tail.prev;
            tail.next = null;
        } else {
            // Create a new node as there is none we could reuse.
            node = new ListNode(key, value);
            map.put(key, node);
        }

        // Place the node at the head.
        node.prev = null;
        node.next = head;
        if (head != null) {
            head.prev = node;
        } else {
            tail = node;
        }
        head = node;
    }
}

Binary Tree Postorder Traversal | Leetcode

Given a binary tree, return the postorder traversal of its nodes' values.

For example:
Given binary tree {1,#,2,3},
   1
    \
     2
    /
   3
return [3,2,1].

Note: Recursive solution is trivial, could you do it iteratively?

---

Solution: Use a stack to hold the nodes. For each node we pop, check if this is a leaf node. If so, add its value to the answer list. If not, push a new fake leaf node with the popped node's value, push the right node, and then push the left node. This will simulate the postorder traversal.
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        if (root == null) return Collections.emptyList();
        
        List<Integer> answer = new ArrayList<>();
        LinkedList<TreeNode> stack = new LinkedList<>();
        stack.add(root);
        
        do {
            TreeNode node = stack.pop();
            if (node.left == null && node.right == null) {
                answer.add(node.val);
                continue;
            }
            stack.push(new TreeNode(node.val));
            if (node.right != null) stack.push(node.right);
            if (node.left != null) stack.push(node.left);
        } while (!stack.isEmpty());
        
        return answer;
    }
}

Binary Tree Preorder Traversal | Leetcode

Given a binary tree, return the preorder traversal of its nodes' values.

For example:
Given binary tree {1,#,2,3},
   1
    \
     2
    /
   3
return [1,2,3].

Note: Recursive solution is trivial, could you do it iteratively?

---

Solution: Use a stack to hold the nodes. After popping each node, first add the value to the answer, then push the right node, then push the left node.
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        if (root == null) return Collections.emptyList();

        List<Integer> answer = new ArrayList<>();
        LinkedList<TreeNode> stack = new LinkedList<>();
        stack.push(root);

        do {
            TreeNode node = stack.pop();
            answer.add(node.val);
            if (node.right != null) stack.push(node.right);
            if (node.left != null) stack.push(node.left);
        } while (!stack.isEmpty());

        return answer;
    }
}

Reorder List | Leetcode

Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

You must do this in-place without altering the nodes' values.

For example,
Given {1,2,3,4}, reorder it to {1,4,2,3}.

---

Solution:
1. Break list into two halves (use fast & slow pointers to find the middle node).
2. Reverse the second half.
3. Merge the two halves back together.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void reorderList(ListNode head) {
        if (head == null || head.next == null) return;
        
        // Find the middle of the list.
        ListNode slow = head;
        ListNode fast = head;
        
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode mid = slow.next;
        
        // Terminate the first half of the list.
        slow.next = null;
        
        // Reverse the second half of the list.
        ListNode prev = null;
        ListNode curr = mid;
        
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        
        // Merge the two halves together.
        ListNode first = head;
        ListNode second = prev;
        
        while (first != null && second != null) {
            if (first != null) {
                ListNode temp = first.next;
                first.next = second;
                first = temp;
            }
            if (second != null) {
                ListNode temp = second.next;
                second.next = first;
                second = temp;
            }
        }
    }
}

Linked List Cycle II | Leetcode

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Follow up:
Can you solve it without using extra space?

---

Solution: Maintain two pointers slow and fast, where slow advances by one node at a time, and fast advances by two nodes at a time. When they meet, reset slow to the head of the list. Then advance both slow and fast by one node at a time until they meet at the beginning of the cycle.
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        do {
            if (fast == null || fast.next == null) return null;
            fast = fast.next.next;
            slow = slow.next;
        } while (fast != slow);
        
        slow = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        
        return slow;
    }
}