sort map by value

Class ValueComparator implements Comparator<String> {
    HashMap<String, Integer> map = new HashMap<String, Integer>();
    public ValueComparator(HashMap<String, Integer> map){
        this.map.putAll(map);
    }
    int compare(String key1, String key2){
        if(map.get(key1) < map.get(key2)){
            return 1;
        } else {
            return -1;
        }
    }
}
...
Comparator<String> comparator = new ValueComparator(originalMap);
TreeMap<String, Integer> result = new TreeMap<String, Integer>(comparator);
result.putAll(orignalMap);
return result;

java-sort-map-by-value

Advertisements

Inorder Successor in BST

public TreeNode inorderSuccessor(TreeNode root, TreeNode target) {
    if(root == null){
        return root;
    }
    TreeNode parent = null;
    TreeNode cur = root;
    while(cur != null && cur.val != target.val){
        if(cur.val > target.val){
            parent = cur;
            cur = cur.left;
        } else {
            cur = cur.right;
        }
    }
    if(cur == null){
        return null;
    }
    if(cur.right == null){
        return parent;
    }
    cur = cur.right;
    while(cur.left != null){
        cur = cur.left;
    }
    return cur;
}

 inorder-successor-in-bst

Meeting Rooms II

public int minMeetingRooms(Interval[] intervals) {
    if(intervals == null || intervals.length == 0){
        return 0;
    }
    Arrays.sort(intervals, new Comparator<Interval>(){
        public int compare(Interval a, Interval b){
            return a.start - b.start;
        }
    });
    PriorityQueue<Integer> queue = new PriorityQueue<>();
    int count = 1;
    queue.offer(intervals[0].end);
    for(int i = 1; i < intervals.length; i++){
        if(intervals[i].start < queue.peek()){
            count++;
        } else {
            queue.poll();
        }
        queue.offer(intervals[i].end);
    }
    return count;
}

meeting-rooms-II-java

Meeting Rooms

public boolean canAttendMeetings(Interval[] intervals){
    Arrays.sort(intervals, new Comparator<Interval>{
        public int compare(Interval a, Interval b){
            return a.start - b.start;
        }
    });
    for(int i = 0; i < intervals.length - 1; i++){
        if(intervals[i].end > intervals[i + 1].start){
            return false;
        }
    }
    return true;
}

leetcode-meeting-rooms-java

Top K Frequent Elements

/*Given a non-empty array of integers, return the k most frequent elements.

For example,
Given [1,1,1,2,2,3] and k = 2, return [1,2]
*/
public class Solution {
public List<Integer> topKFrequent(int[] nums, int k){
    //count the frequency for each element
    HashMap<Integer, Integer> map = new HashMap<>();
    for(int n : nums){
        if(map.containsKey(n)){
            int temp = map.get(n);
            map.put(n, temp + 1);
        } else {
            map.put(n, 1);
        }
    }
    // create a min heap
    PriorityQueue<Pair> queue = new PriorityQueue<>(new Comparator<Pair>(){
        public int compare(Pair a, Pair b){
            return a.count - b.count;
        }
    });
    //maintain a heap of size k
    for(Map.Entry<Integer, Integer> entry : map.entrySet()){
        Pair temp = new Pair(entry.getKey(), entry.getValue());
        queue.offer(temp);
        if(queue.size() > k){
            queue.poll();
        }
    }
    //get all elements from the heap
    List<Integer> res = new ArrayList<>();
    while(!queue.isEmpty()){
        Pair temp = queue.poll();
        res.add(temp.num);
    }
    Collections.reverse(res);
    return res;
}   
}
class Pair {
    int num;
    int count;
    Pair(int num, int count){
        this.num = num;
        this.count = count;
    }
}

Reference:top-k-frequent-elements

Implement a cyclic buffer

import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

public class BoundedBuffer {
    private final String[] buffer;
    private final int capacity;

    private int front;
    private int rear;
    private int count;

    private final Lock lock = new ReentrantLock();
    private final Condition notFull = lock.newCondition();
    private final Condition notEmpty = lock.newCondition();

    public BoundedBuffer(int capacity){
        this.capacity = capacity;
        buffer = new String[capacity];
    }

    public void deposit(String data) throws InterruptedException {
        lock.lock();
        try {
            while(count == capacity){
                notFull.await();
            }
            buffer[rear] = data;
            rear = (rear + 1) % capacity;
            count++;
            notEmpty.signal();
        } final {
            lock.unlock();
        }
    }
    public void fetch() throws InterruptedException {
        lock.lock();
        try {
            while(count == 0){
                notEmpty.await();
            }
            String result = buffer[front];
            front = (front + 1) % capacity;
            count--;
            notFull.signal();
            return result;
        } final {
            lock.unlock();
        }
    }
}

Reference: https://baptiste-wicht.com/posts/2010/09/java-concurrency-part-5-monitors-locks-and-conditions.html

Design a blocking queue

By blocking queue it means if the queue is empty, the dequeue thread should be blocked until some other thread enqueue anything. If the queue is full then the enqueue thread gets blocked until the dequeue thread dequeue anything from the queue.

public interface FixedSizeBlockingQueue<E> {

   // only initialize this queue once and throws Exception if the user is trying to initialize it multiple t times.
   public void init(int capacity) throws Exception;

   // throws Exception if the queue is not initialized
   public void push(E obj) throws Exception;

   // throws Exception if the queue is not initialized
   public E pop() throws Exception;

   // implement an atomic putList function which can put a list of object atomically. By atomically it mean the objs in the list should be next to each other in the queue. The size of the list could be larger than the queue capacity.
   // throws Exception if the queue is not initialized
   public void pushList(List<E> objs) throws Exception;
}
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

public class BoundedBlockingQueue<E> {
    private int capacity;
    private Queue<E> queue;
    private Lock lock = new ReentrantLock();
    private Lock pushLock = new ReentrantLock();
    private Condition notFull = lock.newCondition();
    private Condition notEmpty = lock.newCondition();

    public void init(int capacity) throws Exception {
        lock.lock();
        try {
            if(queue == null){
                queue = new LinkedList<>();
                capacity = capacity;
            } else {
                throw new Exception();
            }
        } finally {
            lock.unlock();
        }
    }

    public void push(E obj) throws Exception {
        pushLock.lock();
        lock.lock();
        try {
            while(capacity == queue.size()){
                notFull.await();
            }
            queue.add(obj);
            notEmpty.signal();
        } finally {
            lock.unlock();
            pushLock.unlock();
        }
    }

    public E pop() throws Exception {
        lock.lock();
        try {
            while(queue.size() == 0){
                notEmpty.await();
            }
            notFull.signal();
            return queue.poll():
        } finally {
            lock.unlock();
        }
    }
    public void pushList(List<E> objs) throws Exception {
        pushLock.lock();
        lock.lock();
        try {
            for(E obj : objs){
                while(queue.size == capacity){
                    notFull.await();
                }
                notEmpty.signal();
                queue.push(obj);
            }
        } finally {
            lock.unlock();
            pushLock.unlock();
        }
    }
}

reference: http://baozitraining.org/blog/design-and-implement-a-blocking-queue/

largest closed loop

/*
     * A zero-indexed array A consisting of N different integers is given. The
     * array contains all integers in the range [0..N−1]. Sets S[K] for 0 ≤ K &lt;
     * N are defined as follows: S[K] = { A[K], A[A[K]], A[A[A[K]]], ... }. Sets
     * S[K] are finite for each K.
     *
     * Write a function:
     *
     * class Solution { public int solution(int[] A); }
     *
     * that, given an array A consisting of N integers, returns the size of the
     * largest closed loop set S[K] for this array. The function should return 0 if the
     * array is empty.
     */
    /*
     * changed value
     */
public int largestClosedLoopSet(int[] A){
    if(A == null || A.length == 0){
        return 0;
    }
    int res = 1;
    int count = 0;
    for(int i = 0; i < A.length; i++){
        count = 0;
        while(A[i] >= 0 && A[i] < A.length){
            count++;
            int nextIndex = A[i];
            // reset A[i] to prevent future repeat iteration.
            A[i] = -1;
            i = inextIndex;
        }
        res = Math.max(res, count);
    }
return res;
}

Topological Sorting

Need to be on Directed Acyclic Graph


// DFS
public ArrayList<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph) {
    ArrayList<DirectedGraphNode> res = new ArrayList<>();
    if(graph == null || graph.size() == 0){
        return res;
    }
    HashSet<DirectedGraphNode> visited = new HashSet<>();
    for(DirectedGraphNode n : graph){
        if(!visited.contains(n)){
            dfs(res, n, visited);
        }
    }
    return res;
}
private void dfs(ArrayList<DirectedGraphNode> res, DirectedGraphNode node, HashSet<DirectedGraphNode> visited){
    visited.add(node);
    for(DirectedGraphNode n : node.neighbors){
        if(!visited.contains(n)){
            dfs(res, n, visited);   
        }
    }
    res.add(0, node);
}
// BFS
public ArrayList<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph) {
    ArrayList<DirectedGraphNode> res = new ArrayList<>();
    if(graph == null || graph.size() == 0){
        return res;
    }
    // map of node to indegree
    HashMap<DirectedGraphNode, Integer> map = new HashMap<>();
    for(DirectedGraphNode n : graph){
        for(DirectedGraphNode n_nb : n.neighbors){
            if(map.containsKey(n_nb)){
                int indegree = map.get(n_nb);
                map.put(n_nb, ++indegree);
            } else {
                map.put(n_nb, 1);
            }
        }
    }
    Queue<DirectedGraphNode> queue = new LinkedList<>();
    for(DirectedGraphNode n : graph){
        if(!map.containsKey(n)){
            //add node with 0 indgree to queue
            queue.offer(n);
            res.add(n);
        }
    }
    while(!queue.isEmpty()){
        DirectedGraphNode n = queue.poll();
        for(DirectedGraphNode n_nb : n.neighbors){
            if(map.containsKey(n_nb)){
                int indegree = map.get(n_nb);
                map.put(n_nb, --indegree);
                if(indegree == 0){
                    res.add(n_nb);
                    queue.offer(n_nb);
                }
            }
        }
    }
    return res;
}

Detect Cycle of Directed Graph

leetcode: Course Schedule


//DFS
public boolean canFinish(int numCourses, int[][] prerequisites) {
   ArrayList[] graph = new ArrayList[numCourses];
   boolean[] visited = new boolean[numCourses];
   for(int i = 0; i < numCourses; i++){
       graph[i] = new ArrayList<Integer>();
   }
   for(int i = 0; i < prerequisites.length; i++){
        int pre = prerequisites[i][1];
        int post = prerequisites[i][0];
       graph[pre].add(post);
   }
   for(int i = 0; i < numCourses; i++){
       if(!dfs(graph,visited,i)){
           return false;
       }
   }
   return true;
}

private boolean dfs(ArrayList[] graph, boolean[] visited, int cur){
    //true- no cycle // fasle - with cycle
    if(visited[cur]){
        return false;
    }
    visited[cur] = true; 
    for(int i = 0; i < graph[cur].size(); i++){
        if(!dfs(graph, visited, (int)graph[cur].get(i))){
            return false;
        }
    }
    visited[cur] = false;
    return true;
}
// BFS
public boolean canFinish(int numCourses, int[][] prerequisites) {
   ArrayList[] graph = new ArrayList[numCourses];
   for(int i = 0; i < numCourses; i++){
       graph[i] = new ArrayList();
   }
   int[] indegree = new int[numCourses];
   
   for(int i =0; i < prerequisites.length; i++){
       int post = prerequisites[i][0];
       int pre = prerequisites[i][1];
      graph[pre].add(post);
      indegree[post]++;
   }
   
   int count = 0;
   Queue<Integer> queue = new LinkedList<Integer>();
   for(int i = 0; i < indegree.length; i++){
       if(indegree[i]==0){
           //vertex without pre
           queue.offer(i);
       }
   }
   while(!queue.isEmpty()){
       int course = queue.poll();
       count++;
       for(int i : graph[course]){
               if(--indegree[i] == 0){
                   queue.offer(i);
               }
       }
   }
   return count == numCourses;
}