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

Advertisements

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

Detect Cycle of Undirected Graph

reference: http://www.programcreek.com/2014/05/graph-valid-tree-java/


//DFS
public boolean validTree(int n, int[][] edges) {
    HashMap<Integer, ArrayList<Integer>> map = new HashMap<>();
    for(int i = 0; i < n; i++){
        ArrayList<Integer> list = new ArrayList<>();
        map.put(i, list);
    }
    for(int i = 0; i < edges.length; i++){
        map.get(edges[i][0]).add(edges[i][1]);
        map.get(edges[i][1]).add(edges[i][0]);
    }
    boolean[] visited = new boolean[n];
   if(!dfs(0, -1, map, visited)){
       return false;
   }
    for(int i = 0; i < n; i++){
        if(!visited[i]){
            return false;
        }
    }
    return true;
}
private boolean dfs(int cur, int parent, HashMap<Integer, ArrayList<Integer>> map, boolean[] visited){
    if(visited[cur]){
        return false;
    }
    visited[cur] = true;
    ArrayList<Integer> neighbors = map.get(cur);
    for(int nb : neighbors){
        if(nb != parent && !dfs(nb, cur, map, visited)){
            return false;
        }
    }
    return true;
}
//BFS
public boolean validTree(int n, int[][] edges) {
    if(edges == null || edges.length != n - 1){
        return false;
    }
    HashMap<Integer, ArrayList<Integer>> map = new HashMap<>();
    for(int i = 0; i < n; i++){
        ArrayList<Integer> list = new ArrayList<>();
        map.put(i, list);
    }
    for(int i = 0; i < edges.length; i++){
        map.get(edges[i][0]).add(edges[i][1]);
        map.get(edges[i][1]).add(edges[i][0]);
    }
    boolean[] visited = new boolean[n];
    Queue<Integer> queue = new LinkedList<>();
    queue.offer(0);
    while(!queue.isEmpty()){
        int cur = queue.poll();
        if(visited[cur]){
            return false;
        } else {
            visited[cur] = true;
            ArrayList<Integer> neighbors = map.get(cur);
            for(int nb : neighbors){
                if(!visited[nb]){
                    queue.offer(nb);
                }
            }
        }
    }
    for(int i = 0; i < n; i++){
        if(!visited[i]){
            return false;
        }
    }
    return true;
}
class UnionFind {
    // map of node and its parent
    HashMap<Integer, Integer> parent_map = new HashMap<>();
    UnionFind(int n){
        for(int i = 0; i < n; i++){
            parent_map.put(i, i);
        }
    }
    // find the root of x and compress the path
    int compressed_find(int x){
        int parent =  parent_map.get(x);
        while(parent !=  parent_map.get(parent)){
            parent =  parent_map.get(parent);
        }
        // here parent equals root of x
        int temp = -1;
        int fa =  parent_map.get(x);
        while(fa != parent){
            temp =  parent_map.get(fa);
            parent_map.put(fa, parent);
            fa = temp;
        }
        return parent;
    }
    void union(int a, int b){
        int root_a = compressed_find(a);
        int root_b = compressed_find(b);
        if(root_a != root_b){
            parent_map.put(root_a, root_b);
        }
    }
}
public boolean validTree(int n, int[][] edges) {
    // Write your code here
    if(n - 1 != edges.length){
        return false;
    }
    
    UnionFind uf = new UnionFind(n);
    for(int i = 0; i < edges.length; i++){
        //check if there is cycle
        if(uf.compressed_find(edges[i][0]) == uf.compressed_find(edges[i][1])){
            return false;
        }
        uf.union(edges[i][0], edges[i][1]);
    }
    return true;
}