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;

    }

} 

High Five Scores

Given a list of Result objects which include the id and score of students. Each student will have at least five scores. Calculate the average score of the highest five scores of each student.

/*
Use hashmap to store each student's id and average score. Use priorityqueue to ensure the highest five scores of each student. 

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

import java.util.*;

class Result{
    int id;
    int value;
    public Result(int id, int value){
        this.id = id;
        this.value = value;
    }
}
public class Solution {
    public static Map<Integer, Double> getHighFive(Result[] results){
        if (results == null || results.length == 0) {
            return null;
        }
        Map<Integer, PriorityQueue<Integer>> map = new HashMap<>();
        for (Result result : results) {
            int id = result.id;
            int value = result.value;
            if (!map.containsKey(id)) {
                PriorityQueue<Integer> minheap = new PriorityQueue<>(6);
                minheap.add(value);
                map.put(id, minheap);
            } else {
                map.get(id).add(value);
                if (map.get(id).size() > 5) {
                    map.get(id).poll();
                }
            }
        }
        Map<Integer, Double> resultMap = new HashMap<>();
        for (Map.Entry<Integer, PriorityQueue<Integer>> entry : map.entrySet()) {
            PriorityQueue<Integer> pq = entry.getValue();
            double mark = 0;
            while (!pq.isEmpty()) {
                mark += pq.poll();
            }
            mark = mark / 5.0;
            resultMap.put(entry.getKey(), mark);
        }
        return resultMap;
    }

    public static void main(String[] args) {
        Result r1 = new Result(1, 1);
        Result r2 = new Result(1, 7);
        Result r3 = new Result(1, 7);
        Result r4 = new Result(1, 6);
        Result r5 = new Result(1, 6);
        Result r6 = new Result(1, 6);

        Result r7 = new Result(2, 6);
        Result r8 = new Result(2, 6);
        Result r9 = new Result(2, 7);
        Result r10 = new Result(2, 6);
        Result r11 = new Result(2, 6);
        Result[] arr = {r1, r2, r3, r4, r5, r6, r7, r8, r9, r10, r11};
        Map<Integer, Double> res = getHighFive(arr);

        System.out.println(res.get(1) + " " +res.get(2));
    }
}

Order Dependency

Given a list of OrderDependency, one OrderDependency includes two Order, like[pre, cur], Order pre must be done first, then Order cur can be done. Return a list of Order according to the given OrderDependency. If it is impossible to complete all the Order, return an empty list.

For example:
Given: [["0", "1"], ["1", "2"],["2", "3"],["3", "4"]], return: ["0", "1", "2", "3"].

/*
This problem can be reduce to the topological sort problem. 
Use one hashmap to store each Order and its in-degrees. Use another hashmap to store the Orders pointed by one pre Order. After the initialization, find Orders with 0 in-degrees, they are the fist Orders that should be completed. And then use bfs to find the other Orders level by level that with 0 in-degrees.

The trap here is that there will be some different Orders but have the same orderName. We should consider they are the same. So, we should make orderName be the key when using hashmap.

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

import java.util.*;

class Order{
    String orderName;
    public Order(String string){
        this.orderName = string;
    }
}
class OrderDependency{
    Order cur;
    Order pre;
    public OrderDependency(Order pre, Order cur){
        this.pre = pre;
        this.cur = cur;
    }
}
public class Solution {
    public static List<Order> solution(List<OrderDependency>                                                 orderDependencies) {
        List<Order> ans = new ArrayList<>();
        if (orderDependencies == null || 
            orderDependencies.size() == 0) {
            return ans;
        } 
        Map<String, Integer> inMap = new HashMap<>();
        Map<String, List<String>> outMap = new HashMap<>();
        for (OrderDependency od : orderDependencies) {
            Order cur = od.cur;
            Order pre = od.pre;
            String curName = cur.orderName;
            String preName = pre.orderName;
            if (!inMap.containsKey(curName)) {
                inMap.put(curName, 1);
            } else {
                inMap.put(curName, inMap.get(curName) + 1);
            }
            if (!inMap.containsKey(preName)) {
                inMap.put(preName, 0);
            }

            if (!outMap.containsKey(preName)) {
                List<String> list = new ArrayList<>();
                list.add(curName);
                outMap.put(preName, list);
            } else {
                outMap.get(preName).add(curName);
            }
        }
        Queue<String> queue = new LinkedList<>();
        for (Map.Entry<String, Integer> entry : inMap.entrySet()) {
            if (entry.getValue() == 0) {
                queue.add(entry.getKey());
                ans.add(new Order(entry.getKey()));
            }
        }
        while (!queue.isEmpty()) {
            String preName = queue.poll();
            if (!outMap.containsKey(preName)) {
                continue;
            }
            for (String curName : outMap.get(preName)) {
                inMap.put(curName, inMap.get(curName) - 1);
                if (inMap.get(curName) == 0) {
                    ans.add(new Order(curName));
                    queue.add(curName);
                }
            }
        }
        if (ans.size() != inMap.size()) {
            return new ArrayList<Order>();
        }
        return ans;       
    }

    public static void main(String[] args) {
        Order o1 = new Order("A");
        Order o2 = new Order("A");
        Order o3 = new Order("C");
        Order o4 = new Order("B");
        Order o5 = new Order("C");
        Order o6 = new Order("A");
        Order o7 = new Order("B");
        Order o8 = new Order("C");
        Order o9 = new Order("D");
        OrderDependency od1 = new OrderDependency(o1, o3);
        OrderDependency od2 = new OrderDependency(o2, o7);
        OrderDependency od3 = new OrderDependency(o3, o9);
        OrderDependency od4 = new OrderDependency(o4, o3);
        OrderDependency od5 = new OrderDependency(o6, o9);
        OrderDependency od6 = new OrderDependency(o8, o9);
        OrderDependency od7 = new OrderDependency(o2, o5);

        OrderDependency od8 = new OrderDependency(o1, o4);
        OrderDependency od9 = new OrderDependency(o4, o3);
        OrderDependency od10 = new OrderDependency(o3, o9);
        OrderDependency od11 = new OrderDependency(o9, o2);

        List<OrderDependency> list = new ArrayList<>();
        list.add(od1);
        list.add(od2);
        list.add(od3);
        list.add(od4);
        list.add(od5);
        list.add(od6);
        list.add(od7);

        List<OrderDependency> list2 = new ArrayList<>();
        list2.add(od8);
        list2.add(od9);
        list2.add(od10);
        list2.add(od11);

        List<Order> res = solution(list);
        List<Order> res2 = solution(list2);

        System.out.println("res: should print: A -> B -> C -> D");
        for (int i = 0; i < res.size(); i++) {
            System.out.print(res.get(i).orderName);
            if (i+1 < res.size()){
                System.out.print(" -> ");
            }
        }
        System.out.println("");
        System.out.println("res2: should print nothing, because of                               the cycle in the graph");
        for (int i = 0; i < res2.size(); i++) {
            System.out.print(res2.get(i).orderName);
            if (i+1 < res2.size()){
                System.out.print(" -> ");
            }
        }
    }
}

Copy List with Random Pointer

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

/**
 * Definition for singly-linked list with a random pointer.
 * class RandomListNode {
 *     int label;
 *     RandomListNode next, random;
 *     RandomListNode(int x) { this.label = x; }
 * };
 */

/*
Use hashmap to implement deep copy.
time:O(n),  space:O(n)
*/

public class Solution {
    public RandomListNode copyRandomList(RandomListNode head) {
        if (head == null) {
            return null;
        }
        Map<RandomListNode, RandomListNode> map = copyNode(head);
        copyRandom(head, map);
        return map.get(head);
    }
    public Map<RandomListNode, RandomListNode> copyNode                                                       (RandomListNode head) {
        Map<RandomListNode, RandomListNode> map = new HashMap<>();
        RandomListNode dummy = new RandomListNode(-1);
        RandomListNode tail = dummy;
        while (head != null) {
            map.put(head, new RandomListNode(head.label));
            tail.next = map.get(head);
            tail = tail.next;
            head = head.next;
        }
        return map;
    }
    public void copyRandom(RandomListNode head, 
                      Map<RandomListNode, RandomListNode> map) {
        while (head != null) {
            if (head.random == null) {
                map.get(head).random = null;
            } else {
                map.get(head).random = map.get(head.random);
            }
            head = head.next;
        }
    }
}


/*
Use constant space to implement deep copy.
1 -> 1 -> 2 -> 2 -> null, deep copy each node and follow the original node.

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

public class Solution {
    public RandomListNode copyRandomList(RandomListNode head) {
        if (head == null) {
            return null;
        }      
        copyNode(head);
        copyRandom(head);
        return copyNext(head);
       
    }
    public void copyNode(RandomListNode head) {
        while (head != null) {
            RandomListNode tmp = new RandomListNode(head.label);
            tmp.next = head.next;
            head.next = tmp;
            head = tmp.next;
        }
    }
    public void copyRandom(RandomListNode head) {
        while (head != null) {
            if (head.random == null) {
                head.next.random = null;
            } else {
                head.next.random = head.random.next;
            }
            head = head.next.next;
        }
    }
    public RandomListNode copyNext(RandomListNode head) {
        RandomListNode dummy = new RandomListNode(0);
        RandomListNode tail = dummy;
        while (head != null) {
            tail.next = head.next;
            tail = tail.next;
            head.next = tail.next;
            head = head.next;
        }
        return dummy.next;
    }
}

Group Anagrams

Given an array of strings, group anagrams together.

For example, given: ["eat", "tea", "tan", "ate", "nat", "bat"], 
Return:

[
  ["ate", "eat","tea"],
  ["nat","tan"],
  ["bat"]
]

Note: All inputs will be in lower-case.

/*

Use a hashmap to gather anagrams, key is sorted string, value is a list that involves the original unsorted string which is same as the key after sorted. 

time:O(Nklogk), space:O(N), N: the number of strings; k: the average length of strings.

*/

public class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> ans = new ArrayList<>();
        if (strs == null || strs.length == 0) {
            return ans;
        }
        Map<String, List<String>> map = new HashMap<>();
        for (String str : strs) {
            char[] chars = str.toCharArray();
            Arrays.sort(chars);
            String newstr = String.valueOf(chars);
            if (map.containsKey(newstr)) {
                map.get(newstr).add(str);
            } else {
                List<String> list = new ArrayList<>();
                list.add(str);
                map.put(newstr, list);
            }
        }
        for (List<String> list : map.values()) {
            ans.add(list);
        }
        return ans;
    }
}

Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution.
Example:Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

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

public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        if (numbers == null || numbers.length == 0) {
            return new int[0];
        }
        int[] res = new int[2];
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < numbers.length; i++) {
            if (map.containsKey(target - numbers[i])) {
                res[0] = map.get(target - numbers[i]);
                res[1] = i;
                break;
            }
            map.put(numbers[i], i);
        }
        return res;
    }
}


/* follow-up1: if the input array is already sorted. */

// two pointers, time:O(n), space:O(1)

public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        if (numbers == null || numbers.length == 0) {
            return new int[0];
        }
        int[] res = new int[2];
        int left = 0;
        int right = numbers.length - 1;
        while (left < right) {
            int sum = numbers[left] + numbers[right];
            if (sum < target) {
                left++;
            } else if (sum > target) {
                right--;
            } else {
                res[0] = left;
                res[1] = right;
                break;
            }
        }
        return res;
    }
}

/*
In the method of two pointers, when the sum is smaller or bigger than the target, the left pointer only pluses one or the right pointer only minuses one. Here we can do some optimization. When the sum is smaller than the target, the left pointer actually can point to the smallest number which equals to or bigger than (target - numbers(right)). When the sum is bigger than the target, the right pointer can point to the biggest number which equals to or smaller than (target - numbers(left)). Because it is the sorted array, we can use binary search to implement this. 

binary search, time:O(logN), space:O(1)
*/

public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        if (numbers == null || numbers.length == 0) {
            return new int[0];
        }
        int[] ans = new int[2];
        int left = 0;
        int right = numbers.length - 1;
        while (left < right) {
            int sum = numbers[left] + numbers[right];
            if (sum < target) {
                left = binarySearch(numbers, target - 
                       numbers[right], left + 1, right - 1);
            } else if (sum > target) {
                right = binarySearch(numbers, target -                                       numbers[left], left + 1, right - 1);
            } else {
                ans[0] = left;
                ans[1] = right;
                break;
            }
        }
        return ans;
    }
    public int binarySearch(int[] nums, int target, 
                            int left, int right) {
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid;
            } else if (nums[mid] > target){
                right = mid;
            } else {
                return mid;
            }
        }
        if (nums[left] >= target) {
            return left;
        }
        return right;
    } 
}


/* follow-up2: if the input array has duplicate numbers, return the indices of two numbers of all the possibilities.
such as: nums = [1,3,5,2,2,3], target = 5,
return:[[1,3],[1,4],[3,5],[4,5]]

Use HashMap, key is number, value is List<Integer> which stores the indices of numbers. And the indices of duplicate numbers will be stored in the same List. 

time:O(n^2), space:O(n)
*/
public class Solution {
    public List<List<Integer>> twoSum(int[] nums, int target) {
List<List<Integer>> ans = new ArrayList<>();
if (nums == null || nums.length == 0) {
           return ans;
}
Map<Integer, List<Integer>> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(target - nums[i])) {
               for (Integer index : map.get(target - nums[i])){
                   List<Integer> list = new ArrayList<>();
                  list.add(index);
                  list.add(i);
                  ans.add(list);
               }
           }
           if (map.containsKey(nums[i])) {
map.get(nums[i]).add(i);
           } else {
List<Integer> list = new ArrayList<>();
list.add(i);
map.put(nums[i], list);
           }
}
return ans;
    }
}