Monday, April 25, 2016

LeetCode 207 - Course Schedule I


https://leetcode.com/problems/course-schedule/
Related: LeetCode 210 - Course Schedule II
There are a total of n courses you have to take, labeled from 0 to n - 1.
Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]
Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?
For example:
2, [[1,0]]
There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.
2, [[1,0],[0,1]]
There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.
Note:
The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.

  • Topological sorting
  • Like all graph search algorithm: O(E+V)
  • 题目等价为:检测图中是否有环
X. Topological Sort
https://leetcode.com/discuss/34699/my-java-bfs-solution
Use Map<Integer, ArrayList<Integer>>
public boolean canFinish(int numCourses, int[][] prerequisites) { Map<Integer, ArrayList<Integer>> map = new HashMap<Integer, ArrayList<Integer>>(); int[] indegree = new int[numCourses]; Queue<Integer> queue = new LinkedList<Integer>(); int count = numCourses; for (int i = 0; i < numCourses; i++) { map.put(i, new ArrayList<Integer>()); } for (int i = 0; i < prerequisites.length; i++) { map.get(prerequisites[i][0]).add(prerequisites[i][1]); indegree[prerequisites[i][1]]++; } for (int i = 0; i < numCourses; i++) { if (indegree[i] == 0) { queue.offer(i); } } while (!queue.isEmpty()) { int current = queue.poll(); for (int i : map.get(current)) { if (--indegree[i] == 0) { queue.offer(i); } } count--; } return count == 0; }
https://leetcode.com/discuss/37134/java-ac-solution-with-top-sort
Use hashset - not really better
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        Set<Integer> zeroDegree = new HashSet<>();
        int[] degree = new int[numCourses];
        for (int row = 0; row < prerequisites.length; row++)
            degree[prerequisites[row][0]]++;
        for (int i = 0; i < degree.length; i++)
            if (degree[i] == 0) zeroDegree.add(i);
        if (zeroDegree.isEmpty()) return false;
        while (!zeroDegree.isEmpty()) {
            Iterator<Integer> it = zeroDegree.iterator();
            int course = it.next();
            zeroDegree.remove(course);
            for (int row = 0; row < prerequisites.length; row++) {
                int[] edge = prerequisites[row];
                if (edge[1] == course) {
                    degree[edge[0]]--;
                    if (degree[edge[0]] == 0) zeroDegree.add(edge[0]);
                }
            }
        }
        for (int i = 0; i < degree.length; i++)
            if (degree[i] != 0) return false;
        return true;
    }
not efficient
https://leetcode.com/discuss/35578/easy-bfs-topological-sort-java
http://www.programcreek.com/2014/05/leetcode-course-schedule-java/
https://leetcode.com/discuss/82347/java-easy-version-to-understand
public boolean canFinish(int numCourses, int[][] prerequisites) {
    if(prerequisites == null){
        throw new IllegalArgumentException("illegal prerequisites array");
    }
 
    int len = prerequisites.length;
 
    if(numCourses == 0 || len == 0){
        return true;
    }
 
    // counter for number of prerequisites
    int[] pCounter = new int[numCourses];
    for(int i=0; i<len; i++){
        pCounter[prerequisites[i][0]]++;
    }
 
    //store courses that have no prerequisites
    LinkedList<Integer> queue = new LinkedList<Integer>();
    for(int i=0; i<numCourses; i++){
        if(pCounter[i]==0){
            queue.add(i);
        }
    }
 
    // number of courses that have no prerequisites
    int numNoPre = queue.size();
 
    while(!queue.isEmpty()){
        int top = queue.remove();
        for(int i=0; i<len; i++){
            // if a course's prerequisite can be satisfied by a course in queue
            if(prerequisites[i][1]==top){//not efficient
                pCounter[prerequisites[i][0]]--;
                if(pCounter[prerequisites[i][0]]==0){
                    numNoPre++;
                    queue.add(prerequisites[i][0]);
                }
            }
        }
    }
 
    return numNoPre == numCourses;
}

https://leetcode.com/discuss/39456/java-dfs-and-bfs-solution
public boolean canFinish(int numCourses, int[][] prerequisites) { ArrayList[] graph = new ArrayList[numCourses]; int[] degree = new int[numCourses]; Queue queue = new LinkedList(); int count=0; for(int i=0;i<numCourses;i++) graph[i] = new ArrayList(); for(int i=0; i<prerequisites.length;i++){ degree[prerequisites[i][1]]++; graph[prerequisites[i][0]].add(prerequisites[i][1]); } for(int i=0; i<degree.length;i++){ if(degree[i] == 0){ queue.add(i); count++; } } while(queue.size() != 0){ int course = (int)queue.poll(); for(int i=0; i<graph[course].size();i++){ int pointer = (int)graph[course].get(i); degree[pointer]--; if(degree[pointer] == 0){ queue.add(pointer); count++; } } } if(count == numCourses) return true; else return false; }

X. Using
https://discuss.leetcode.com/topic/13854/easy-bfs-topological-sort-java

Could you provide the Time complexity for your solution using adjacent matrix?`
while (!queue.isEmpty()) {
        int course = queue.poll();
        count++;
        for (int i=0; i<numCourses; i++) {
            if (matrix[course][i] != 0) {
                if (--indegree[i] == 0)
                    queue.offer(i);
            }
        }
    }
For this part, I kind of guess it is not O(V^2) instead of O(V+E) because you always scan from i=0 to numCourses to check whether the matrix[course][i] is 0 or not.
Is this solution memory-efficient? The matrix seems to be a big overhead.

public boolean canFinish(int numCourses, int[][] prerequisites) {
    int[][] matrix = new int[numCourses][numCourses]; // i -> j
    int[] indegree = new int[numCourses];
    
    for (int i=0; i<prerequisites.length; i++) {
        int ready = prerequisites[i][0];
        int pre = prerequisites[i][1];
        if (matrix[pre][ready] == 0)
            indegree[ready]++; //duplicate case
        matrix[pre][ready] = 1;
    }
    
    int count = 0;
    Queue<Integer> queue = new LinkedList();
    for (int i=0; i<indegree.length; i++) {
        if (indegree[i] == 0) queue.offer(i);
    }
    while (!queue.isEmpty()) {
        int course = queue.poll();
        count++;
        for (int i=0; i<numCourses; i++) {
            if (matrix[course][i] != 0) {
                if (--indegree[i] == 0)
                    queue.offer(i);
            }
        }
    }
    return count == numCourses;
}
I rewrote the code, I think that would be O(V + E)
    // O(V + E)
    List<Integer>[] matrix = new List[numCourses];
    int[] indegree = new int[numCourses];

    // E part
    for (int[] pre : prerequisites) {
        int preCourse = pre[1];
        int readyCourse = pre[0];
        List<Integer> list = matrix[preCourse];
        if (list == null) {
         list = new LinkedList<>();   
         matrix[preCourse] = list;
        }
        list.add(readyCourse);
        indegree[readyCourse]++;
    }
    
    Queue<Integer> queue = new LinkedList<>();
    for (int i=0; i<numCourses; i++) {
        if (indegree[i] == 0) queue.offer(i);
    }
    int count = 0;
    // V part
    while (!queue.isEmpty()) {
        int vertex = queue.poll();
        count++;
        List<Integer> adjacent = matrix[vertex];
        if (adjacent == null) continue;
        for (int neighbor : adjacent) {
            indegree[neighbor]--;
            if (indegree[neighbor] == 0)
                queue.offer(neighbor);
        }
    }
    return count == numCourses;
https://leetcode.com/discuss/71444/explained-java-12ms-iterative-solution-based-algorithm-clrs
Not efficient to use ArrayList as a queue.
X. DFS
https://leetcode.com/discuss/65901/concise-java-solutions-based-on-bfs-and-dfs-with-explanation
To do memorization and pruning, a HashMap is used to save the previous results for the specific node.
HashMap<Integer, Boolean>memo = new HashMap<Integer, Boolean>();//Memorization HashMap for DFS pruning 
public boolean canFinish(int n, int[][] edges) {         
    if (edges.length != 0) { 
        HashMap<Integer, HashSet<Integer>> neighbors = new HashMap<Integer, HashSet<Integer>>(); // Neighbors of each node
        HashSet<Integer>curPath = new HashSet<Integer>(); // Nodes on the current path
        for (int i = 0; i < edges.length; i++) {// Convert graph presentation from edge list to adjacency list 
            if (!neighbors.containsKey(edges[i][1])) 
                neighbors.put(edges[i][1], new HashSet<Integer>());            
            neighbors.get(edges[i][1]).add(edges[i][0]);
        }

        for (int a[] : edges) // The graph is possibly not connected, so need to check every node.
            if (hasCycle(neighbors, a[0], -1, curPath))// Use DFS method to check if there's cycle in any curPath
                return false;
    } 
    return true;
}     

boolean hasCycle(HashMap<Integer, HashSet<Integer>> neighbors, int kid, int parent, HashSet<Integer>curPath) {
    if (memo.containsKey(kid)) return memo.get(kid);
    if (curPath.contains(kid)) return true;// The current node is already in the set of the current path        
    if (!neighbors.containsKey(kid)) return false;     

    curPath.add(kid);
    for (Integer neighbor : neighbors.get(kid)) {
        boolean hasCycle = hasCycle(neighbors, neighbor, kid, curPath);// DFS
        memo.put(kid, hasCycle);                
        if (hasCycle) return true;
    }
    curPath.remove(kid);        
    return false;
}
http://buttercola.blogspot.com/2015/08/leetcode-course-schedule.html
Use an array to mark if the node has been visited before. Here is a small trick to save some time. Instead of using a boolean array, we use an integer array int[] visited. 
visited = -1, means this node has been visited. 
visited = 1, means this node has been validated which does not include a circle. Thus if we saw that a node has been validated, we don't need to calculate again to find out the circle starting from this node. e.g. [0, 1] [1, 2] [2, 3] [3, 4]. For the node 0, we have already validated 2 3 and 4 do not have a circle. Thus we don't need to calculate for the node 2 3 4 again.
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        if (numCourses <= 0) {
            return true;
        }
         
        if (prerequisites == null || prerequisites.length == 0) {
            return true;
        }
         
        // First transform the edge list to adj. list
        Map<Integer, List<Integer>> adjList = new HashMap<>();
        for (int[] edge : prerequisites) {
            if (adjList.containsKey(edge[0])) {
                List<Integer> neighbors = adjList.get(edge[0]);
                neighbors.add(edge[1]);
                adjList.put(edge[0], neighbors);
            } else {
                List<Integer> neighbors = new ArrayList<Integer>();
                neighbors.add(edge[1]);
                adjList.put(edge[0], neighbors);
            }
        }
         
        int[] visited = new int[numCourses];
        // Check if the graph contains a circle, if yes, return false.
        for (int i = 0; i < numCourses; i++) {
            if (hasCircles(i, visited, adjList)) {
                return false;
            }
        }
         
        return true;
    }
     
    private boolean hasCircles(int vertexId, int[] visited, Map<Integer, List<Integer>> adjList) {
        if (visited[vertexId] == -1) {
            return true;
        }
         
        if (visited[vertexId] == 1) {
            return false;
        }
         
        visited[vertexId] = -1;// wrong
         
        List<Integer> neighbors = adjList.get(vertexId);
        if (neighbors != null) {
            for (int neighbor : neighbors) {
                if (hasCircles(neighbor, visited, adjList)) {
                    return true;
                }
            }
        }
         
        visited[vertexId] = 1;
         
        return false;
    }

public boolean canFinish(int numCourses, int[][] prerequisites) {
    if(prerequisites == null){
        throw new IllegalArgumentException("illegal prerequisites array");
    }
 
    int len = prerequisites.length;
 
    if(numCourses == 0 || len == 0){
        return true;
    }
 
    //track visited courses
    int[] visit = new int[numCourses];
 
    // use the map to store what courses depend on a course 
    HashMap<Integer,ArrayList<Integer>> map = new HashMap<Integer,ArrayList<Integer>>();
    for(int[] a: prerequisites){
        if(map.containsKey(a[1])){
            map.get(a[1]).add(a[0]);
        }else{
            ArrayList<Integer> l = new ArrayList<Integer>();
            l.add(a[0]);
            map.put(a[1], l);
        }
    }
 
    for(int i=0; i<numCourses; i++){
        if(!canFinishDFS(map, visit, i))
            return false;
    }
 
    return true;
}
 
private boolean canFinishDFS(HashMap<Integer,ArrayList<Integer>> map, int[] visit, int i){
    if(visit[i]==-1) 
        return false;
    if(visit[i]==1) 
        return true;
 
    visit[i]=-1;
    if(map.containsKey(i)){
        for(int j: map.get(i)){
            if(!canFinishDFS(map, visit, j)) 
                return false;
        }
    }
 
    visit[i]=1;
 
    return true;
}

http://happycoding2010.blogspot.com/2015/10/leetcode-207-course-schedule.html
 public class Solution {  
   public boolean canFinish(int numCourses, int[][] prerequisites) {  
     int V=numCourses;  
     List<Integer>[] adj=new List[V];  
     for (int v=0; v<V; v++) adj[v]=new LinkedList<>();  
     for (int i=0; i<prerequisites.length; i++) adj[prerequisites[i][1]].add(prerequisites[i][0]);  
     boolean[] marked=new boolean[V];  
     boolean[] onStack=new boolean[V];  
     boolean[] hasCycle=new boolean[1];  
     for (int v=0; v<V; v++)  
       if(!marked[v]) dfs(v,adj,V,marked,onStack,hasCycle);  
     return !hasCycle[0];  
   }  
   private void dfs(int v, List<Integer>[] adj, int V, boolean[] marked, boolean[] onStack, boolean[] hasCycle) {  
     marked[v]=true;  
     onStack[v]=true;  
     for (int w: adj[v]) {  
       if (hasCycle[0]) return;  
       else if (!marked[w]) dfs(w,adj,V,marked,onStack,hasCycle);  
       else if (onStack[w]) hasCycle[0]=true;  
     }  
     onStack[v]=false;  
   }  
 } 

http://sgq626.blogspot.com/2015/07/leetcode-207leetcode-210-course.html
这个题目很容易分析出来是check if a directed graph has a cycle.

但是给的graph是 a list of edges, 如果只给定一些edges我们是无法对graph进行遍历的,所以我们可以建立一个adjacent list, 并且带上一个state记录每个node的状态。

这个题目里面的adjacent list 可以用map来做, 然后对map做DFS遍历。
采用的是DFS + mark visitIII -> 3 states
但是需要注意的是,需要对graph里面的每个Node进行遍历,才能遍历到所有的可能。
 这个题目里面没有 sanity check !!! 面试的时候要跟面试官商量sanity check的问题。  
    bool dfs(map<int, vector<int>> &nmap, int start, vector<int> &M) {
        //base case
        if (M[start] == 1) return true;//has visited
        if (M[start] == -1) {
            return false;
        }
        M[start] = -1; //visiting node
        //expand 
        for (int i = 0; i < nmap[start].size();i++) {
           if(dfs(nmap, nmap[start][i], M) == false) return false;
        }
        M[start] = 1; //mark visit
        return true;
    }
    //to check if a directed graph has a cycle or not 
    bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
        //map
        map<int, vector<int>> nmap;
        for (int i = 0; i < prerequisites.size(); i++) {
            nmap[prerequisites[i].second].push_back(prerequisites[i].first);//prere->course
        }
        //use map to do dfs + visit
        vector<int> M(numCourses, 0); //unvisited
        for (int i = 0; i < numCourses;i++) {
            if (dfs(nmap, i, M) == false) return false;
        }

        return true;
    }

http://felixzhang00.github.io/2015/05/07/2015-05-07-LeetCode%E7%AC%AC207%E9%A2%98--Course%20Schedule/
public boolean canFinish(int numCourses, int[][] prerequisites) {
      Digraph G = new Digraph(numCourses);
      for (int i = 0; i < prerequisites.length; i++) {
          for (int j = 0; j < prerequisites[i].length; j++) {
              G.addEdge(prerequisites[i][j], prerequisites[i][++j]);
          }
      }
      DirectedCycle dag = new DirectedCycle(G);
      return !dag.hasCycle();
}
判断有向图中是否有环

用一个数组boolean[] onStack保存递归调用期间栈上的所有顶点.

onStack[v]=true,记录顶点v出现在这次dfs中,在这次dfs结束后,是onStack[v]=false

在递归执行dfs的过程中,记录当前下当前顶点在递归调用栈中,这样以后的递归调用栈只要判断它的相连点是否在之前的递归调用栈中出现过,就能判断是否有环。
private class DirectedCycle {
    private boolean[] marked;        // marked[v] 顶点v是否被访问过
    private boolean[] onStack;       //保存递归调用期间栈上的所有顶点。 onStack[v] = ?顶点v是否在栈中
    private boolean hasCycle;       // 有向图中是否环
    public DirectedCycle(Digraph G) {
        marked = new boolean[G.V()];
        onStack = new boolean[G.V()];
        hasCycle = false;
        for (int v = 0; v < G.V(); v++)   //对图中每一个没有被访问过的点做深度优先遍历
            if (!marked[v]) dfs(G, v);
    }
    /**
     * 从v顶点开始做深度优先遍历
     */
    private void dfs(Digraph G, int v) {
        onStack[v] = true;
        marked[v] = true;
        for (int w : G.adj(v)) {        //遍历所有顶点v的相连点
            if (hasCycle) return;       //如果已经找到一个环就不再dfs
            else if (!marked[w]) {      //对每一个未访问过的点继续dfs
                dfs(G, w);
            } else if (onStack[w]) {    //顶点w在之前的递归调用栈中,并且已经被访问过,构成环
                hasCycle = true;
            }
        }
        onStack[v] = false;             //顶点v所有的相连点遍历结束,顶点v退出当前调用栈
    }
    public boolean hasCycle() {
        return hasCycle;
    }
}
private class Digraph {
    private final int V;
    private ArrayList<Integer>[] adj;
    public Digraph(int V) {
        this.V = V;
        adj = (ArrayList<Integer>[]) new ArrayList[V];
        for (int v = 0; v < V; v++) {
            adj[v] = new ArrayList<Integer>();
        }
    }
    public void addEdge(int v, int w) {
        adj[v].add(w);
    }
    public int V() {
        return V;
    }
    public Iterable<Integer> adj(int v) {
        return adj[v];
    }
}
X. Not efficient
https://leetcode.com/discuss/39456/java-dfs-and-bfs-solution
i second this. I may be wrong, but the worst case runtime could be n^2 since you are not checking if any nodes are visited in the main for loop (the one in the canFinish function). This means you may be doing repeated searches. Imagine 1->2->3->4->5, when checking node (1) in the main loop, you'll be go through 2 - 5, but when you r checking node(2) in the main loop, you'll go through 3 - 5 again.
The run time for this DFS solution is O(V + E^2). In the worst case described above by OBOBOB90 the algorithm needs to iterate over each course (which is O(V)), plus V^2 time to iterate over the course dependencies (O(E^2)).
It is possible though to implement DFS algorithm with O(E) runtime
public boolean canFinish(int numCourses, int[][] prerequisites) { ArrayList[] graph = new ArrayList[numCourses]; for(int i=0;i<numCourses;i++) graph[i] = new ArrayList(); boolean[] visited = new boolean[numCourses]; for(int i=0; i<prerequisites.length;i++){ graph[prerequisites[i][1]].add(prerequisites[i][0]); } for(int i=0; i<numCourses; i++){ if(!dfs(graph,visited,i)) return false; } return true; } private boolean dfs(ArrayList[] graph, boolean[] visited, int course){ if(visited[course]) return false; else visited[course] = true;; for(int i=0; i<graph[course].size();i++){ if(!dfs(graph,visited,(int)graph[course].get(i))) return false; } visited[course] = false; return true; }

OO:
https://leetcode.com/discuss/35035/oo-easy-to-read-java-solution

Build Order:
You are given a list of projects and a list of dependencies (which is a list of pairs of
projects, where the second project is dependent on the first project). All of a project's dependencies
must be built before the project is. Find a build order that will allow the projects to be built. If there
is no valid build order, return an error.
Project[] findBuildOrder(String[] projects, String[][] dependencies) {
        Graph graph= buildGraph(projects, dependencies);
        return orderProjects(graph.getNodes());
}

/* Build the graph, adding the edge (a, b) if b is dependent on a. Assumes a pair
 * is listed in "build order". The pair (a, b) in dependencies indicates that b
 * depends on a and a must be built before b. */
Graph buildGraph(String[] projects, String[][] dependencies) {
        Graph graph= new Graph();
        for (String project : projects) {
                graph.createNode(project);
        }

        for (String[] dependency : dependencies) {
                String first= dependency[0];
                String second= dependency[l];
                graph.addEdge(first, second);
        }

        return graph;
}

/* Return a list of the projects a correct build order.*/
Project[] orderProjects(Arraylist<Project> projects) {
        Project[] order = new Project[projects.size()];// if there are a lot of projects: use queue to remove already processed nodes

        /* Add "roots" to the build order first.*/
        int endOfList = addNonDependent(order, projects, 0);

        int toBeProcessed = 0;
        while (toBeProcessed < order.length) {
                Project current= order[toBeProcessed];

                /* We have a circular dependency since there are no remaining projects with
                 * zero dependencies. */
                if (current== null) {
                        return null;
                }

                /* Remove myself as a dependency. */
                Arraylist<Project> children = current.getChildren();
                for (Project child : children) {
                        child.decrementDependencies();
                }

                /* Add children that have no one depending on them. */
                endOfList = addNonDependent(order, children, endOfList);
                toBeProcessed++;
        }

        return order;
}

/* A helper function to insert projects with zero dependencies into the order
 * array, starting at index offset. */
int addNonDependent(Project[] order, Arraylist<Project> projects, int offset) {
        for (Project project: projects) {
                if (project.getNumberDependencies() == 0) {
                        order[offset] = project;
                        offset++;
                }
        }
        return offset;
}

public class Graph {
private Arraylist<Project> nodes= new Arraylist<Project>();
private HashMap<String, Project> map = new HashMap<String, Project>();

public Project getOrCreateNode(String name) {
        if (!map.containsKey(name)) {
                Project node = new Project(name);
                nodes.add(node);
                map.put(name, node);
        }

        return map.get(name);
}

public void addEdge(String startName, String endName) {
        Project start = getOrCreateNode(startName);
        Project end= getOrCreateNode(endName);
        start.addNeighbor(end);
}

public Arraylist<Project> getNodes() {
        return nodes;
}
}

public class Project {
private Arraylist<Project> children = new Arraylist<Project>();
private HashMap<String, Project> map= new HashMap<String, Project>();
private String name;
private int dependencies = 0;

public Project(String n) {
        name n;
}

public void addNeighbor(Project node) {
        if (!map.containsKey(node.getName())) {
                children.add(node);
                map.put(node.getName(), node);
                node.incrementDependencies();
        }
}

public void incrementDependencies() {
        dependencies++;
}
public void decrementDependencies() {
        dependencies--;
}

public String getName() {
        return name;
}
public Arraylist<Project> getChildren() {
        return children;
}
public int getNumberDependencies() {
        return dependencies;
}
}

Stack<Project> findBuildOrder(String[] projects, String[][] dependencies) {
        Graph graph= buildGraph(projects, dependencies);
        return orderProjects(graph.getNodes());
}

Stack<Project> orderProjects(ArrayList<Project> projects) {
        Stack<Project> stack = new Stack<Project>();
        for (Project project: projects) {
                if (project.getState() == Project.State.BLANK) {
                        if (!doDFS(project, stack)) {
                                return null;
                        }
                }
        }
        return stack;
}

boolean doDFS(Project project, Stack<Project> stack) {
        if (project.getState() == Project.State.PARTIAL) {
                return false; // Cycle
        }

        if (project.getState() == Project.State.BLANK) {
                project.setState(Project.State.PARTIAL);
                ArrayList<Project> children = project.getChildren();
                for (Project child : children) {
                        if (!doDFS(child, stack)) {

                        }
                        return false;
                }
                project.setState(Project.State.COMPLETE);
                stack.push(project);
        }
        return true;
}
/* Essentially equivalent to earlier solution, with state info added and
 * dependency count removed. */
public class Project {
public enum State {COMPLETE, PARTIAL, BLANK};
private State state = State.BLANK;
public State getState() {
        return state;
}
public void setState(State st) {
        state = st;
}
/* Duplicate code removed for brevity*/
}


No comments:

Post a Comment

Labels

GeeksforGeeks (959) Algorithm (811) LeetCode (630) to-do (595) Classic Algorithm (334) Review (327) Classic Interview (299) Dynamic Programming (262) Google Interview (224) LeetCode - Review (224) Tree (146) POJ (137) Difficult Algorithm (136) EPI (127) Different Solutions (118) Bit Algorithms (110) Cracking Coding Interview (110) Smart Algorithm (109) Math (91) HackerRank (85) Lintcode (83) Binary Search (73) Graph Algorithm (73) Interview Corner (61) Greedy Algorithm (59) List (58) Binary Tree (56) DFS (54) Algorithm Interview (53) Codility (52) ComProGuide (52) Advanced Data Structure (51) LeetCode - Extended (47) USACO (46) Geometry Algorithm (44) BFS (43) Data Structure (42) Mathematical Algorithm (42) ACM-ICPC (41) Interval (38) Jobdu (38) Recursive Algorithm (38) Stack (38) String Algorithm (38) Binary Search Tree (37) Knapsack (37) Codeforces (36) Introduction to Algorithms (36) Matrix (36) Must Known (36) Beauty of Programming (35) Sort (35) Array (33) prismoskills (33) Segment Tree (32) Space Optimization (32) Trie (32) Union-Find (32) Backtracking (31) HDU (31) Google Code Jam (30) Permutation (30) Puzzles (30) Array O(N) (29) Data Structure Design (29) Company-Zenefits (28) Microsoft 100 - July (28) to-do-must (28) Random (27) Sliding Window (26) GeeksQuiz (25) Logic Thinking (25) hihocoder (25) High Frequency (23) Palindrome (23) Algorithm Game (22) Company - LinkedIn (22) Graph (22) Queue (22) DFS + Review (21) Hash (21) TopCoder (21) Binary Indexed Trees (20) Brain Teaser (20) CareerCup (20) Company - Twitter (20) Pre-Sort (20) Company-Facebook (19) UVA (19) Probabilities (18) Codercareer (16) Company-Uber (16) Game Theory (16) Heap (16) Shortest Path (16) String Search (16) Topological Sort (16) Tree Traversal (16) itint5 (16) Follow Up (15) Iterator (15) Merge Sort (15) O(N) (15) Difficult (14) Number (14) Number Theory (14) Post-Order Traverse (14) Priority Quieue (14) Amazon Interview (13) BST (13) Basic Algorithm (13) Bisection Method (13) Codechef (13) Majority (13) mitbbs (13) Combination (12) Computational Geometry (12) KMP (12) Long Increasing Sequence(LIS) (12) Modify Tree (12) Reconstruct Tree (12) Reservoir Sampling (12) 尺取法 (12) AOJ (11) DFS+Backtracking (11) Fast Power Algorithm (11) Graph DFS (11) LCA (11) LeetCode - DFS (11) Ordered Stack (11) Princeton (11) Tree DP (11) 挑战程序设计竞赛 (11) Binary Search - Bisection (10) Company - Microsoft (10) Company-Airbnb (10) Euclidean GCD (10) Facebook Hacker Cup (10) HackerRank Easy (10) Reverse Thinking (10) Rolling Hash (10) SPOJ (10) Theory (10) Tutorialhorizon (10) X Sum (10) Coin Change (9) Lintcode - Review (9) Mathblog (9) Max-Min Flow (9) Stack Overflow (9) Stock (9) Two Pointers (9) Book Notes (8) Bottom-Up (8) DP-Space Optimization (8) Divide and Conquer (8) Graph BFS (8) LeetCode - DP (8) LeetCode Hard (8) Prefix Sum (8) Prime (8) System Design (8) Tech-Queries (8) Use XOR (8) 穷竭搜索 (8) Algorithm Problem List (7) DFS+BFS (7) Facebook Interview (7) Fibonacci Numbers (7) Game Nim (7) HackerRank Difficult (7) Hackerearth (7) Interval Tree (7) Linked List (7) Longest Common Subsequence(LCS) (7) Math-Divisible (7) Miscs (7) O(1) Space (7) Probability DP (7) Radix Sort (7) Simulation (7) Suffix Tree (7) Xpost (7) n00tc0d3r (7) 蓝桥杯 (7) Bucket Sort (6) Catalan Number (6) Classic Data Structure Impl (6) DFS+DP (6) DP - Tree (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Level Order Traversal (6) Manacher (6) Minimum Spanning Tree (6) One Pass (6) Programming Pearls (6) Quick Select (6) Rabin-Karp (6) Randomized Algorithms (6) Sampling (6) Schedule (6) Suffix Array (6) Threaded (6) Time Complexity (6) reddit (6) AI (5) Art Of Programming-July (5) Big Data (5) Brute Force (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Crazyforcode (5) DFS+Cache (5) DP-Multiple Relation (5) DP-Print Solution (5) Dutch Flag (5) Fast Slow Pointers (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Inversion (5) Java (5) Kadane - Extended (5) Kadane’s Algorithm (5) Matrix Chain Multiplication (5) Microsoft Interview (5) Morris Traversal (5) Pruning (5) Quick Partition (5) Quora (5) SPFA(Shortest Path Faster Algorithm) (5) Subarray Sum (5) Traversal Once (5) TreeMap (5) jiuzhang (5) to-do-2 (5) 单调栈 (5) 树形DP (5) 1point3acres (4) Anagram (4) Approximate Algorithm (4) Backtracking-Include vs Exclude (4) Brute Force - Enumeration (4) Chess Game (4) Company-Amazon (4) Consistent Hash (4) Convex Hull (4) Cycle (4) DP-Include vs Exclude (4) Dijkstra (4) Distributed (4) Eulerian Cycle (4) Flood fill (4) Graph-Classic (4) HackerRank AI (4) Histogram (4) Kadane Max Sum (4) Knapsack - Mixed (4) Knapsack - Unbounded (4) Left and Right Array (4) MinMax (4) Multiple Data Structures (4) N Queens (4) Nerd Paradise (4) Parallel Algorithm (4) Practical Algorithm (4) Pre-Sum (4) Probability (4) Programcreek (4) Quadtrees (4) Quick Sort (4) Spell Checker (4) Stock Maximize (4) Subsets (4) Sudoku (4) Sweep Line (4) Symbol Table (4) TreeSet (4) Triangle (4) Water Jug (4) Word Ladder (4) algnotes (4) fgdsb (4) 最大化最小值 (4) A Star (3) Abbreviation (3) Algorithm - Brain Teaser (3) Algorithm Design (3) Anagrams (3) B Tree (3) Big Data Algorithm (3) Binary Search - Smart (3) Caterpillar Method (3) Coins (3) Company - Groupon (3) Company - Indeed (3) Cumulative Sum (3) DP-Fill by Length (3) DP-Two Variables (3) Dedup (3) Dequeue (3) Dropbox (3) Easy (3) Edit Distance (3) Expression (3) Finite Automata (3) Forward && Backward Scan (3) Github (3) GoLang (3) Include vs Exclude (3) Joseph (3) Jump Game (3) Knapsack-多重背包 (3) LeetCode - Bit (3) LeetCode - TODO (3) Linked List Merge Sort (3) LogN (3) Maze (3) Min Cost Flow (3) Minesweeper (3) Missing Numbers (3) NP Hard (3) Online Algorithm (3) Pascal's Triangle (3) Pattern Match (3) Project Euler (3) Rectangle (3) Scala (3) SegmentFault (3) Stack - Smart (3) State Machine (3) Streaming Algorithm (3) Subset Sum (3) Subtree (3) Transform Tree (3) Two Pointers Window (3) Warshall Floyd (3) With Random Pointer (3) Word Search (3) bookkeeping (3) codebytes (3) Activity Selection Problem (2) Advanced Algorithm (2) AnAlgorithmADay (2) Application of Algorithm (2) Array Merge (2) BOJ (2) BT - Path Sum (2) Balanced Binary Search Tree (2) Bellman Ford (2) Binomial Coefficient (2) Bit Mask (2) Bit-Difficult (2) Bloom Filter (2) Book Coding Interview (2) Branch and Bound Method (2) Clock (2) Codesays (2) Company - Baidu (2) Complete Binary Tree (2) DFS+BFS, Flood Fill (2) DP - DFS (2) DP-3D Table (2) DP-Classical (2) DP-Output Solution (2) DP-Slide Window Gap (2) DP-i-k-j (2) DP-树形 (2) Distributed Algorithms (2) Divide and Conqure (2) Doubly Linked List (2) GoHired (2) Graham Scan (2) Graph - Bipartite (2) Graph BFS+DFS (2) Graph Coloring (2) Graph-Cut Vertices (2) Hamiltonian Cycle (2) Huffman Tree (2) In-order Traverse (2) Include or Exclude Last Element (2) Information Retrieval (2) Interview - Linkedin (2) Invariant (2) Islands (2) Knuth Shuffle (2) LeetCode - Recursive (2) Linked Interview (2) Linked List Sort (2) Longest SubArray (2) Lucene-Solr (2) MST (2) MST-Kruskal (2) Master Theorem (2) Math-Remainder Queue (2) Matrix Power (2) Minimum Vertex Cover (2) Negative All Values (2) Number Each Digit (2) Numerical Method (2) Object Design (2) Order Statistic Tree (2) Palindromic (2) Parentheses (2) Parser (2) Peak (2) Programming (2) Range Minimum Query (2) Reuse Forward Backward (2) Robot (2) Rosettacode (2) Scan from right (2) Search (2) Shuffle (2) Sieve of Eratosthenes (2) SimHash (2) Simple Algorithm (2) Skyline (2) Spatial Index (2) Stream (2) Strongly Connected Components (2) Summary (2) TV (2) Tile (2) Traversal From End (2) Tree Sum (2) Tree Traversal Return Multiple Values (2) Word Break (2) Word Graph (2) Word Trie (2) Young Tableau (2) 剑指Offer (2) 数位DP (2) 1-X (1) 51Nod (1) Akka (1) Algorithm - How To (1) Algorithm - New (1) Algorithm Series (1) Algorithms Part I (1) Analysis of Algorithm (1) Array-Element Index Negative (1) Array-Rearrange (1) Auxiliary Array (1) Auxiliary Array: Inc&Dec (1) BACK (1) BK-Tree (1) BZOJ (1) Basic (1) Bayes (1) Beauty of Math (1) Big Integer (1) Big Number (1) Binary (1) Binary Tree Variant (1) Bipartite (1) Bit-Missing Number (1) BitMap (1) BitMap index (1) BitSet (1) Bug Free Code (1) BuildIt (1) C/C++ (1) CC Interview (1) Cache (1) Calculate Height at Same Recusrion (1) Cartesian tree (1) Check Tree Property (1) Chinese (1) Circular Buffer (1) Code Quality (1) Codesolutiony (1) Company - Alibaba (1) Company - Palantir (1) Company - WalmartLabs (1) Company-Apple (1) Company-Epic (1) Company-Salesforce (1) Company-Snapchat (1) Company-Yelp (1) Compression Algorithm (1) Concurrency (1) Convert BST to DLL (1) Convert DLL to BST (1) Custom Sort (1) Cyclic Replacement (1) DFS-Matrix (1) DP - Probability (1) DP Fill Diagonal First (1) DP-Difficult (1) DP-End with 0 or 1 (1) DP-Fill Diagonal First (1) DP-Graph (1) DP-Left and Right Array (1) DP-MaxMin (1) DP-Memoization (1) DP-Node All Possibilities (1) DP-Optimization (1) DP-Preserve Previous Value (1) DP-Print All Solution (1) Database (1) Detect Negative Cycle (1) Directed Graph (1) Do Two Things at Same Recusrion (1) Domino (1) Dr Dobb's (1) Duplicate (1) Equal probability (1) External Sort (1) FST (1) Failure Function (1) Fraction (1) Front End Pointers (1) Funny (1) Fuzzy String Search (1) Game (1) Generating Function (1) Generation (1) Genetic algorithm (1) GeoHash (1) Geometry - Orientation (1) Google APAC (1) Graph But No Graph (1) Graph Transpose (1) Graph Traversal (1) Graph-Coloring (1) Graph-Longest Path (1) Gray Code (1) HOJ (1) Hanoi (1) Hard Algorithm (1) How Hash (1) How to Test (1) Improve It (1) In Place (1) Inorder-Reverse Inorder Traverse Simultaneously (1) Interpolation search (1) Interview (1) Interview - Easy (1) Interview - Facebook (1) Isomorphic (1) JDK8 (1) K Dimensional Tree (1) Knapsack - Fractional (1) Knapsack - ZeroOnePack (1) Knight (1) Kosaraju’s algorithm (1) Kruskal (1) Kruskal MST (1) Kth Element (1) Least Common Ancestor (1) LeetCode - Binary Tree (1) LeetCode - Coding (1) LeetCode - Detail (1) LeetCode - Related (1) LeetCode Diffcult (1) Linked List Reverse (1) Linkedin (1) Linkedin Interview (1) Local MinMax (1) Logic Pattern (1) Longest Common Subsequence (1) Longest Common Substring (1) Longest Prefix Suffix(LPS) (1) Manhattan Distance (1) Map && Reverse Map (1) Math - Induction (1) Math-Multiply (1) Math-Sum Of Digits (1) Matrix - O(N+M) (1) Matrix BFS (1) Matrix Graph (1) Matrix Search (1) Matrix+DP (1) Matrix-Rotate (1) Max Min So Far (1) Median (1) Memory-Efficient (1) MinHash (1) MinMax Heap (1) Monotone Queue (1) Monto Carlo (1) Multi-Reverse (1) Multiple DFS (1) Multiple Tasks (1) Next Successor (1) Offline Algorithm (1) PAT (1) Partition (1) Path Finding (1) Patience Sort (1) Persistent (1) Pigeon Hole Principle (1) Power Set (1) Pratical Algorithm (1) Probabilistic Data Structure (1) Proof (1) Python (1) Queue & Stack (1) RSA (1) Ranking (1) Rddles (1) ReHash (1) Realtime (1) Recurrence Relation (1) Recursive DFS (1) Recursive to Iterative (1) Red-Black Tree (1) Region (1) Regular Expression (1) Resources (1) Reverse Inorder Traversal (1) Robin (1) Selection (1) Self Balancing BST (1) Similarity (1) Sort && Binary Search (1) String Algorithm. Symbol Table (1) String DP (1) String Distance (1) SubMatrix (1) Subsequence (1) System of Difference Constraints(差分约束系统) (1) TSP (1) Ternary Search Tree (1) Test (1) Thread (1) TimSort (1) Top-Down (1) Tournament (1) Tournament Tree (1) Transform Tree in Place (1) Tree Diameter (1) Tree Rotate (1) Trie + DFS (1) Trie and Heap (1) Trie vs Hash (1) Trie vs HashMap (1) Triplet (1) Two Data Structures (1) Two Stacks (1) USACO - Classical (1) USACO - Problems (1) UyHiP (1) Valid Tree (1) Vector (1) Wiggle Sort (1) Wikipedia (1) Yahoo Interview (1) ZOJ (1) baozitraining (1) codevs (1) cos126 (1) javabeat (1) jum (1) namic Programming (1) sqrt(N) (1) 两次dijkstra (1) 九度 (1) 二进制枚举 (1) 夹逼法 (1) 归一化 (1) 折半枚举 (1) 枚举 (1) 状态压缩DP (1) 男人八题 (1) 英雄会 (1) 逆向思维 (1)

Popular Posts