K closest points

/*
 * Find the K closest points to the origin in 2D plane, given an array containing N points.
 * You can assume K is much smaller than N and N is very large.
 * You need only use standard math operators (addition, subtraction, multiplication, and division).
 */
import java.util.*;

class Point {
    double x;
    double y;
    public Point(double x, double y) {
        this.x = x;
        this.y = y;
    }
}
public class Solution {
private static double distance(Point a, Point b) {
        return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
    }
public static Point[] closestPoint(Point[] array, final Point origin, int k) {
        if (k >= array.length) {
        // return array;
        k = array.length;
        }
        if (k <= 0) {
        return new Point[0];
        }
        Point[] res = new Point[k];
        PriorityQueue<Point> maxHeap = new PriorityQueue<>(k + 1, new Comparator<Point>() {
            @Override
            public int compare(Point a, Point b) {
                return Double.compare(distance(b, origin), distance(a, origin));
            }
        });
        for(Point p : array) {
        maxHeap.offer(p);
        if (maxHeap.size() > k) {
        maxHeap.poll();
        }
        }
        for(int i = k - 1; i >= 0; i--) {
        res[i] = maxHeap.poll();
        }
        return res;
    }

    public static void main(String[] args) {
        Point origin = new Point(0, 0);
        Point[] input = new Point[]{new Point(0, 2), new Point(1, 1), new Point(-1, 0), new Point(2, 0), new Point(3, 0)};
        Point[] output = closestPoint(input, origin, 3);
        System.out.println("input");
        for(Point i : input) System.out.print("("+i.x+", "+i.y+") ");
        System.out.println("");
        System.out.println("output");
        for(Point i : output) System.out.print("("+i.x+", "+i.y+") ");
    }
}

Four Integers

Given four integers, make F(S) = abs(S[0]-S[1])+abs(S[1]-S[2])+abs(S[2]-S[3]) to be largest.


import java.util.*;

public class Solution {
    public static int[] fourInteger(int A, int B, int C, int D) {
        int[] ans = {A, B, C, D};
        Arrays.sort(ans);
        swap(ans, 0, 1);
        swap(ans, 2, 3);
        swap(ans, 0, 3);
        return ans;
    }
    private static void swap(int[] array, int i, int j) {
        array[i] ^= array[j];
        array[j] ^= array[i];
        array[i] ^= array[j];
    }

    public static void main(String[] args) {
        int[] ans = fourInteger(1,2,3,4);
        for (Integer i : ans) {
            System.out.print(i + " ");
        }

    }
}

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);
    }
}

Linked List Cycle II

Given a linked list, return the node where the cycle begins.

If there is no cycle, return null.

For example:

Given -21->10->4->5, tail connects to node index 1，return 10

/**
 * Definition for ListNode.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int val) {
 *         this.val = val;
 *         this.next = null;
 *     }
 * }
 */ 

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

public class Solution {
    public ListNode detectCycle(ListNode head) { 
        if (head == null) {
            return head;
        }
        ListNode slow = head;
        ListNode fast = head.next;
        while (slow != fast) {
            if (fast == null || fast.next == null) {
                return null;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        while (head != slow.next) {
            head = head.next;
            slow = slow.next;
        }
        return head;
    }
}

Insert into Cycle Linked List

Insert a new list node into a sorted cycle linked list.

/*
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 insertCycleLinkedList(ListNode head, 
                                                 int val) {
        ListNode curr = new ListNode(val);
        if (head == null) {
            curr.next = curr;
            return curr;
        }
        ListNode node = head;
        do {
            if (val >= node.val && val <= node.next.val) {
                break;
            } 
            if (node.val >= node.next.val && 
                (val >= node.val || val <= node.next.val)) {
                break;
            }
            node = node.next;
        } while (node != head);
        
        curr.next = node.next;
        node.next = curr;
        return curr;
    }

    public static void main(String[] args) {
        ListNode n1 = new ListNode (1);
        ListNode n2 = new ListNode (1);
        ListNode n3 = new ListNode (1);
        n1.next = n2;
        n2.next = n3;
        n3.next = n1;
        ListNode ans = insertCycleLinkedList(n1, 2);
        ListNode tmp = ans;
        do {
            System.out.print(tmp.val + " ");
            tmp = tmp.next;
        } while (tmp != ans);
    }
}

Rotate Matrix

Given a matrix and a flag, if flag = 1, rotate the matrix by 90 degrees clockwise. If flag = 0, rotate the matrix by 90 degrees counterclockwise.


/*
First transpose the matrix and then rotate it.
time:O(m*n), space:O(1)
*/

import java.util.*;

public class Solution {
    public static int[][] rotateMatrix(int[][] matrix, int flag) {
        if (matrix == null || matrix.length == 0 || 
            matrix[0] == null || matrix[0].length == 0) {
            return matrix;
        }
        if (flag != 0 && flag != 1) {
            return matrix;
        }
        int[][] res = transpose(matrix);
        return rotate(res, flag);
    }
    public static int[][] transpose(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] res = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                res[i][j] = matrix[j][i];
            }
        }
        return res;
    }
    public static int[][] rotate(int[][] matrix, int flag) {
        int m = matrix.length;
        int n = matrix[0].length;
        if (flag == 1) {
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n / 2; j++) {
                    swap(matrix, i, j, i , n - 1 - j);
                }
            }
        } else {
            for (int i = 0; i < m / 2; i++) {
                for (int j = 0; j < n; j++) {
                    swap(matrix, i, j, m - 1- i, j);
                }
            }
        }
        return matrix;
    }
    public static void swap(int[][] matrix, int a, int b, 
                                            int c, int d) {
        int tmp = matrix[a][b];
        matrix[a][b] = matrix[c][d];
        matrix[c][d] = tmp;
    }

    public static void main(String[] args) {
        int[][] matrix = {{1,2,3,4},{5,6,7,8},{9,10,11,12}};
        int[][] res = rotateMatrix(matrix, 0);
        for (int i = 0; i < res.length; i++) {
            for (int j = 0; j < res[0].length; j++) {
                System.out.print(res[i][j]+" ");
            }
            System.out.println(" ");
        }
    }
}

Greatest Common Divisor

Given an array of Integers, return the greatest common divisor of all the numbers in the array.

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

import java.util.*;

public class Solution {
    public static int gcd(int[] A) {
        if (A == null || A.length <= 1) {
            return 0;
        }
        int num = A[0];
        for (int i = 1; i < A.length; i++) {
            num = calGCD(num, A[i]);
            if (num == 1) {
                return 1;
            }
        }
        return num;
    }
    public static int calGCD(int a, int b) {
        while (a % b != 0) {
            int k = a % b;
            a = b;
            b = k;
        }
        return b;
    }

    public static void main(String[] args) {
        int[] A = {2,3,6,7};
        int res = gcd(A);
        System.out.print(res);
        
    }
}

Window Sum

Given a list of integers, and a window size k, the window slides from left to right. Calculate the sum of integers in the window in each slide.

For example:
Given: A = [1,2,2,-3,4,0,3], k = 3. 
Return: [5, 1, 3, 1, 7]

/*
Two pointers, maintain a window whose size is k.
time:O(n), space:O(1)
*/

import java.util.*;

public class Solution {
    public static List<Integer> GetSum(List<Integer> A, int k) {
        ArrayList<Integer> res  = new ArrayList<>();
        if (A == null || A.size() == 0 || k <= 0) {
            return res;
        }
        int i = 0, j = 0;
        int sum = 0;
        for (i = 0; i < A.size() - k + 1; i++) {
            while (j < A.size() && j - i < k) {
                sum += A.get(j);
                j++;
            }
            res.add(sum);
            sum -= A.get(i);
        }
        return res;
    }

    public static void main(String[] args) {
        List<Integer> A = new ArrayList<>();
        A.add(1);
        A.add(1);
        A.add(2);
        A.add(-4);
        A.add(5);
        A.add(0);
        List<Integer> ans = GetSum(A, 7);
        for (Integer i : ans) {
            System.out.print(i + " ");
        }
    }
}

Subtree

You have two every large binary trees: T1, with millions of nodes, and T2, with hundreds of nodes. Create an algorithm to decide if T2 is a subtree of T1.

Example

T2 is a subtree of T1 in the following case:

       1                3
      / \              / 
T1 = 2   3      T2 =  4
        /
       4

T2 isn't a subtree of T1 in the following case:

       1               3
      / \               \
T1 = 2   3       T2 =    4
        /
       4

/**
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */

//time:O(mn), space:O(1)

public class Solution {
    public boolean isSubtree(TreeNode T1, TreeNode T2) {
        if (T2 == null) {
            return true;
        }
        if (T1 == null) {
            return false;
        }
        if (identical(T1, T2)) {
            return true;
        }
        if (isSubtree(T1.left, T2) || isSubtree(T1.right, T2)) {
            return true;
        }
        return false;
    }
    
    public boolean identical(TreeNode root1, TreeNode root2) {
        if (root1 == null || root2 == null) {
            return root1 == root2;
        }
        if (root1.val != root2.val) {
            return false;
        }
        return identical(root1.left, root2.left) && 
               identical(root1.right, root2.right);
    }
}

Merge Two Sorted Lists

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */

/*
time:O(n), space:O(1)
*/
public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        ListNode dummy = new ListNode(0);
        ListNode curr = dummy;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                curr.next = l1;
                l1 = l1.next;
            } else {
                curr.next = l2;
                l2 = l2.next;
            }
            curr = curr.next;
        }
        if (l1 != null) {
            curr.next = l1;
        }
        if (l2 != null) {
            curr.next = l2;
        }
        return dummy.next;
    }
}

Check Valid Parentheses

Given a string only with '(' and ')'. If it is a valid parentheses string, return the number of valid parentheses pairs. One '(' and one ')' is one pair. Otherwise, return -1. 

import java.util.*;

public class Solution {
    public static int validParentheses(String word) {
        if (word == null || word.length() == 0) {
            return 0;
        }
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < word.length(); i++) {
            if (word.charAt(i) == '(') {
                stack.push('(');
            } else if (word.charAt(i) == ')') {
                if (stack.isEmpty() || stack.pop() != '(') {
                    return -1;
                } 
            } else {
                return -1;
            }
        }
        if (!stack.isEmpty()) {
            return -1;
        }
        return word.length() / 2;
    }

    public static void main(String[] args) {
        int res = validParentheses("(())");
        System.out.println(res);
    }
}