Sliding Window Maximum

Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

For example,
Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.

Window position                Max
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

Therefore, return the max sliding window as [3,3,5,5,6,7].

/*

We scan the array from 0 to n-1, keep "promising" elements in the deque. The algorithm is amortized O(n) as each element is put and polled once.

At each i, we keep "promising" elements, which are potentially max number in window [i-(k-1),i] or any subsequent window. This means

1. If an element in the deque and it is out of i-(k-1), we discard them. We just need to poll from the head, as we are using a deque and elements are ordered as the sequence in the array
2. Now only those elements within [i-(k-1),i] are in the deque. We then discard elements smaller than a[i] from the tail. This is because if a[x] <a[i] and x<i, then a[x] has no chance to be the "max" in [i-(k-1),i], or any other subsequent window: a[i] would always be a better candidate.
3. As a result elements in the deque are ordered in both sequence in array and their value. At each step the head of the deque is the max element in [i-(k-1),i]

time:O(n), space:O(n)

*/

public class Solution {

    public int[] maxSlidingWindow(int[] nums, int k) {

        if (nums == null || nums.length == 0 || k <= 0) {

            return new int[0];

        }

        int len = nums.length;

        int[] res = new int[nums.length - k + 1];

        int index = 0;

        Deque<Integer> q = new ArrayDeque<>();

        for (int i = 0; i < len; i++) {

            while (!q.isEmpty() && q.peek() < i - k + 1) {

                q.poll();

            }

            while (!q.isEmpty() && nums[q.peekLast()] < nums[i]) {

                q.pollLast();

            }

            q.offer(i);

            if (i >= k - 1) {

                res[index++] = nums[q.peek()];

            }

        }

        return res;

    }

}

Reverse Second Half Linked List

Given a linked list, reverse the second half linked list. If the list length is odd, then the middle list node also should be reversed.

For example:
Given:  1 -> 2 -> 3 -> null;
Return: 1 -> 3 -> 2 -> null;

Given:  1 -> 2 -> 3 -> 4 -> null;
Return: 1 -> 2 -> 4 -> 3 -> null;

/*
First compute the size of list to determine the middle list node.

time:O(n), space:O(1)
*/

import java.util.*;

class ListNode {
    int val;
    ListNode next;
    public ListNode(int val) {
        this.val = val;
        next = null;
    }
}

public class Solution {
    public static ListNode reverseHalfList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        int size = calSize(head);
        ListNode middle = getMidNode(head, size);
        middle.next = reverse(middle.next);
        return head;
    }
    public static int calSize(ListNode head) {
        int size = 0;
        while (head != null) {
            head = head.next;
            size++;
        }
        return size;
    }
    public static ListNode getMidNode(ListNode head, int size) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode slow = (size & 1) == 0 ? head : dummy;
        ListNode fast = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
    public static ListNode reverse(ListNode head) {
        ListNode newHead = null;
        while (head != null) {
            ListNode temp = head.next;
            head.next = newHead;
            newHead = head;
            head = temp;
        }
        return newHead;
    }

    public static void main(String[] args) {
        ListNode n1 = new ListNode (1);
        ListNode n2 = new ListNode (2);
        ListNode n3 = new ListNode (3);
        ListNode n4 = new ListNode (4);
        ListNode n5 = new ListNode (5);
        ListNode n6 = new ListNode (6);
        ListNode n7 = new ListNode (7);
        n1.next = n2;
        n2.next = n3;
        n3.next = n4;
        
        n5.next = n6;
        n6.next = n7;
        ListNode ans1 = reverseHalfList(n1);
        ListNode ans2 = reverseHalfList(n5);
        while (ans1 != null) {
            System.out.print(ans1.val + " ");
            ans1 = ans1.next;
        }
        System.out.println(" ");
        while (ans2 != null) {
            System.out.print(ans2.val + " ");
            ans2 = ans2.next;
        }
    }
}

Maze

Given a matrix filled with '1's and '0's and only one '9'. Suppose 0 means one can not pass through it and 1 means one can pass. If one can only start at point (0,0), can s/he arrives at the point filled with '9'? (One can only move either up or down or left or right at any point in time.) 

/*
This problem is similar to "Number of Islands", we can use either DFS or BFS to traverse each point start from (0,0) until arriving at 9 or the next paths all being blocked. 
*/

/*
In BFS, there is a tricky way to convert the 2D coordinate into 1D number. And use dx = {1, 0, -1, 0},dy = {0, 1, 0, -1} in the code to avoid redundancy.

BFS: time:O(n^2), space:O(n^2)
*/

import java.util.*;

public class Solution {
    public static int Maze(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || 
            matrix[0] == null || matrix[0].length == 0) {
            return 0;
        }
        if (matrix[0][0] == 0) {
            return 0;
        }
        if (matrix[0][0] == 9) {
            return 1;
        }
        int m = matrix.length;
        int n = matrix[0].length;
        Queue<Integer> queue = new LinkedList<>();
        queue.add(0);
        matrix[0][0] = 0;
        int[] dx = {1, 0, -1, 0};
        int[] dy = {0, 1, 0, -1};
        while (!queue.isEmpty()) {
            int tmp = queue.poll();
            int x = tmp / n;
            int y = tmp % n;
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (nx < 0 || nx >= m || ny < 0 || ny >= n) {
                    continue;
                }
                if (matrix[nx][ny] == 0) {
                    continue;
                }
                if (matrix[nx][ny] == 9) {
                    return 1;
                }
                queue.add(nx * n + ny);
                matrix[nx][ny] = 0;
            }
        }
        return 0;
    }

    public static void main(String[] args) {
        int[][] matrix = {{1,1,1},{0,0,1},{9,0,1}};
        int res = Maze(matrix);
        System.out.print(res);
    }

}

//DFS: time:O(n^2), space:O(1)

import java.util.*;

public class Solution {

    public static int Maze(int[][] matrix) {

        if (matrix == null || matrix[0] == null) {

            return 0;

        }

        return dfs(matrix, 0, 0);

    }

    public static int dfs(int[][] matrix, int x, int y) {

        if (x < 0 || x >= matrix.length || 

            y < 0 || y >= matrix[0].length) {

            return 0;

        }

        if (matrix[x][y] == 9) {

            return 1;

        }

        if (matrix[x][y] == 1) {

            matrix[x][y] = 0;

            if (dfs(matrix, x + 1, y) == 1 || 

                dfs(matrix, x, y + 1) == 1 ||

                dfs(matrix, x - 1, y) == 1 || 

                dfs(matrix, x, y - 1) == 1) {

                return 1;

            };

        }

        return 0;

    }

    public static void main(String[] args) {

        int[][] matrix = {{1,1,1},{0,0,1},{9,0,1}};

        int res = Maze(matrix);

        System.out.print(res);

    }

}

Day Change

Given an int array 'days', and a number n representing number of days, suppose the numbers at the left of days[0] and at the right of days[days.length - 1] are both 0. Every day, the number in days array will be changed in such rule: array[i] = array[i + 1] == array[i - 1] ? 0 : 1. Return the array after n days. 

For example:
Given: days = [1,0,1,1], n = 1
Return: [0,0,1,1]

/*
Everyday, the change of each number only depends on the previous unchanged number at the left and right. The change in today of each number will not influence the next number.

time:O(n), space:O(n)
*/

import java.util.*;

public class Solution {
    public static int[] dayChange(int[] days, int n) {
        if (days == null || days.length == 0 || n <= 0) {
            return days;
        }
        if (days.length == 1) {
            days[0] = 0;
            return days;
        }
        int[] res = new int[days.length];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < days.length; j++) {
                if (j + 1 == days.length) {
                    res[j] = days[j - 1] == 0 ? 0 : 1;
                } else {
                    if (j == 0) {
                        res[j] = days[j + 1] == 0 ? 0 : 1;
                    } else {
                        res[j] = days[j + 1] == days[j - 1] ? 0 : 1;
                    }
                }
            }
            int[] tmp = res;
            res = days;
            days =tmp;
        }
        return days;
    }

    public static void main(String[] args) {
        int[] days = {0,1,0,1,1,0};
        int[] res = dayChange(days, 2);
        for(int i : res) {
            System.out.print(i + " ");
        }
    }
}

Binary search tree minimum sum from root to leaf

Given a binary search tree, return the minimum sum from root to leaf.

/*
DFS,  search every path from root to leaf and compare the sum with the minimum sum. 

time:O(n), space:O(1)
*/

import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) {
        this.val = val;
        left = right = null;
    }
}
public class Solution {
    public static int minPathSum(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int[] min = {Integer.MAX_VALUE};
        dfs(root, root.val, min);
        return min[0];
    }
    public static void dfs(TreeNode root, int sum, int[] min) {
        if (root.left == null && root.right == null) {
            min[0] = Math.min(min[0], sum);
            return;
        }
        if (root.left != null) {
            sum += root.left.val;
            dfs(root.left, sum, min);
            sum -= root.left.val;
        }
        if (root.right != null) {
            sum += root.right.val;
            dfs(root.right, sum, min);
            sum -= root.right.val;
        }
    }

    public static void main(String[] args) {
        TreeNode a = new TreeNode(1);
        TreeNode b = new TreeNode(2);
        TreeNode c = new TreeNode(3);
        TreeNode d = new TreeNode(-2);
        TreeNode e = new TreeNode(-5);
        TreeNode f = new TreeNode(-4);
        a.left = b;
        a.right = c;
        b.left = d;
        c.left = e;
        c.right = f;
        int min = minPathSum(a);
        System.out.println(min);
    }
}

LRU Cache Miss

Implement LRU cache, and count the miss number which is not in the cache before added to the cache. 

import java.util.*;

class ListNode {
    int key;
    ListNode prev, next;
    public ListNode(int key) {
        this.key = key;
        prev = next = null;
    }
}
public class Solution {
    public static int cacheMiss(int[] array, int size) {
        if (array == null || array.length == 0 || size <= 0) {
            return 0;
        }
        Map<Integer, ListNode> cache = new HashMap<>();
        ListNode head = new ListNode(-1);
        ListNode tail = new ListNode(-1);
        head.next = tail;
        tail.prev = head;
        int count = 0;
        for (int i = 0; i < array.length; i++) {
            ListNode newNode = new ListNode(array[i]);
            if (!cache.containsKey(array[i])) {
                if (cache.size() == size) {
                    cache.remove(head.next.key);
                    head.next = head.next.next;
                    head.next.prev = head;
                }
                count++;
            } else {
                ListNode node = cache.get(array[i]);
                node.prev.next = node.next;
                node.next.prev = node.prev;
            }
            newNode.prev = tail.prev;
            newNode.next = tail;
            tail.prev = newNode;
            newNode.prev.next = newNode;
            cache.put(array[i], newNode);
        }
        return count;
    }

    public static void main(String[] args) {
        int[] A = {1,2,3,1,4,3};
        int res = cacheMiss(A, 3);
        System.out.println(res);
    }
}

LRU Cache

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.

/*

LinkedHashMap = DoublyLinkedList + HashMap.

Newest node append to tail and eldest node remove from head.

Notice: 

1. When use DoublyLinkedList, ListNode head and tail should be initialized at first.

2. In the ListNode, key should be added. 

*/

public class Solution {

    private class ListNode {

        ListNode prev;

        ListNode next;

        int key;

        int value;

        public ListNode(int key, int value) {

            this.key = key;

            this.value = value;

            prev = null;

            next = null;

        }

    }

    

    private int capacity;

    private Map<Integer, ListNode> map = new HashMap<>();

    private ListNode head = new ListNode(-1, -1);

    private ListNode tail = new ListNode(-1, -1);

    

    public Solution(int capacity) {

        this.capacity = capacity;

        head.next = tail;

        tail.prev = head;

    }

    public int get(int key) {

        if (!map.containsKey(key)) {

            return -1;

        }

        ListNode temp = map.get(key);

        temp.prev.next = temp.next;

        temp.next.prev = temp.prev;

        moveToTail(temp);

        

        return map.get(key).value;

    }

    public void set(int key, int value) {

        if (get(key) != -1) {

            map.get(key).value = value;

            return;

        }

        if (map.size() == capacity) {

            //This is why key should be added to the ListNode.

            map.remove(head.next.key);  

            head.next = head.next.next;

            head.next.prev = head;

        }

        

        ListNode node = new ListNode(key, value);

        map.put(key, node);

        moveToTail(node);

    }

    

    private void moveToTail(ListNode node) {

        node.prev = tail.prev;

        node.next = tail;

        tail.prev = node;

        node.prev.next = node;

    }

}