Wednesday, June 1, 2016

WordNet - Princeton Part II - Programming Assignment 1


http://coursera.cs.princeton.edu/algs4/assignments/wordnet.html
WordNet is a semantic lexicon for the English language that is used extensively by computational linguists and cognitive scientists; for example, it was a key component in IBM's Watson. WordNet groups words into sets of synonyms called synsets and describes semantic relationships between them. One such relationship is the is-a relationship, which connects a hyponym (more specific synset) to a hypernym (more general synset). For example, animal is a hypernym of both bird and fishbird is a hypernym of eaglepigeon, and seagull.
The WordNet digraph. Your first task is to build the wordnet digraph: each vertex v is an integer that represents a synset, and each directed edge v→w represents that w is a hypernym of v. The wordnet digraph is a rooted DAG: it is acyclic and has one vertex—the root—that is an ancestor of every other vertex. However, it is not necessarily a tree because a synset can have more than one hypernym. A small subgraph of the wordnet digraph is illustrated below.

The WordNet input file formats. We now describe the two data files that you will use to create the wordnet digraph. The files are in CSV format: each line contains a sequence of fields, separated by commas.
  • List of noun synsets. The file synsets.txt lists all the (noun) synsets in WordNet. The first field is the synset id (an integer), the second field is the synonym set (or synset), and the third field is its dictionary definition (or gloss). For example, the line
    36,AND_circuit AND_gate,a circuit in a computer that fires only when all of its inputs fire  
    
    means that the synset { AND_circuitAND_gate } has an id number of 36 and it's gloss is a circuit in a computer that fires only when all of its inputs fire. The individual nouns that comprise a synset are separated by spaces (and a synset element is not permitted to contain a space). The S synset ids are numbered 0 through S − 1; the id numbers will appear consecutively in the synset file.

  • List of hypernyms. The file hypernyms.txt contains the hypernym relationships: The first field is a synset id; subsequent fields are the id numbers of the synset's hypernyms. For example, the following line
    164,21012,56099
    
    means that the the synset 164 ("Actifed") has two hypernyms: 21012 ("antihistamine") and 56099 ("nasal_decongestant"), representing that Actifed is both an antihistamine and a nasal decongestant. The synsets are obtained from the corresponding lines in the file synsets.txt.

    164,Actifed,trade name for a drug containing an antihistamine and a decongestant...
    21012,antihistamine,a medicine used to treat allergies...
    56099,nasal_decongestant,a decongestant that provides temporary relief of nasal...
    
WordNet data type. Implement an immutable data type WordNet with the following API:
public class WordNet {

   // constructor takes the name of the two input files
   public WordNet(String synsets, String hypernyms)

   // returns all WordNet nouns
   public Iterable<String> nouns()

   // is the word a WordNet noun?
   public boolean isNoun(String word)

   // distance between nounA and nounB (defined below)
   public int distance(String nounA, String nounB)

   // a synset (second field of synsets.txt) that is the common ancestor of nounA and nounB
   // in a shortest ancestral path (defined below)
   public String sap(String nounA, String nounB)

   // do unit testing of this class
   public static void main(String[] args)
}
Corner cases.  All methods and the constructor should throw a java.lang.NullPointerException if any argument is null. The constructor should throw a java.lang.IllegalArgumentException if the input does not correspond to a rooted DAG. The distance() and sap() methods should throw a java.lang.IllegalArgumentException unless both of the noun arguments are WordNet nouns.
Performance requirements.  Your data type should use space linear in the input size (size of synsets and hypernyms files). The constructor should take time linearithmic (or better) in the input size. The method isNoun()should run in time logarithmic (or better) in the number of nouns. The methods distance() and sap() should run in time linear in the size of the WordNet digraph. For the analysis, assume that the number of nouns per synset is bounded by a constant.
Shortest ancestral path. An ancestral path between two vertices v and w in a digraph is a directed path from v to a common ancestor x, together with a directed path from w to the same ancestor x. A shortest ancestral path is an ancestral path of minimum total length. For example, in the digraph at left (digraph1.txt), the shortest ancestral path between 3 and 11 has length 4 (with common ancestor 1). In the digraph at right (digraph2.txt), one ancestral path between 1 and 5 has length 4 (with common ancestor 5), but the shortest ancestral path has length 2 (with common ancestor 0).

SAP data type. Implement an immutable data type SAP with the following API:
public class SAP {

   // constructor takes a digraph (not necessarily a DAG)
   public SAP(Digraph G)

   // length of shortest ancestral path between v and w; -1 if no such path
   public int length(int v, int w)

   // a common ancestor of v and w that participates in a shortest ancestral path; -1 if no such path
   public int ancestor(int v, int w)

   // length of shortest ancestral path between any vertex in v and any vertex in w; -1 if no such path
   public int length(Iterable<Integer> v, Iterable<Integer> w)

   // a common ancestor that participates in shortest ancestral path; -1 if no such path
   public int ancestor(Iterable<Integer> v, Iterable<Integer> w)

   // do unit testing of this class
   public static void main(String[] args)
}

Corner cases.  All methods should throw a java.lang.NullPointerException if any argument is null. All methods should throw a java.lang.IndexOutOfBoundsException if any argument vertex is invalid—not between 0 and G.V() - 1.
Performance requirements.  All methods (and the constructor) should take time at most proportional to E + V in the worst case, where E and V are the number of edges and vertices in the digraph, respectively. Your data type should use space proportional to E + V.
Test client. The following test client takes the name of a digraph input file as as a command-line argument, constructs the digraph, reads in vertex pairs from standard input, and prints out the length of the shortest ancestral path between the two vertices and a common ancestor that participates in that path:
public static void main(String[] args) {
    In in = new In(args[0]);
    Digraph G = new Digraph(in);
    SAP sap = new SAP(G);
    while (!StdIn.isEmpty()) {
        int v = StdIn.readInt();
        int w = StdIn.readInt();
        int length   = sap.length(v, w);
        int ancestor = sap.ancestor(v, w);
        StdOut.printf("length = %d, ancestor = %d\n", length, ancestor);
    }
}
Here is a sample execution:
% more digraph1.txt             % java SAP digraph1.txt
13                              3 11
11                              length = 4, ancestor = 1
 7  3                            
 8  3                           9 12
 3  1                           length = 3, ancestor = 5
 4  1
 5  1                           7 2
 9  5                           length = 4, ancestor = 0
10  5
11 10                           1 6
12 10                           length = -1, ancestor = -1
 1  0
 2  0
Measuring the semantic relatedness of two nouns. Semantic relatedness refers to the degree to which two concepts are related. Measuring semantic relatedness is a challenging problem. For example, most of us agree that George Bush and John Kennedy (two U.S. presidents) are more related than are George Bush and chimpanzee (two primates). However, not most of us agree that George Bush and Eric Arthur Blair are related concepts. But if one is aware that George Bush and Eric Arthur Blair (aka George Orwell) are both communicators, then it becomes clear that the two concepts might be related.
We define the semantic relatedness of two wordnet nouns A and B as follows:
  • distance(A, B) = distance is the minimum length of any ancestral path between any synset v of A and any synset w of B.
This is the notion of distance that you will use to implement the distance() and sap() methods in the WordNet data type.
Outcast detection. Given a list of wordnet nouns A1A2, ..., An, which noun is the least related to the others? To identify an outcast, compute the sum of the distances between each noun and every other one:
di   =   dist(AiA1)   +   dist(AiA2)   +   ...   +   dist(AiAn)
and return a noun At for which dt is maximum.
Implement an immutable data type Outcast with the following API:
public class Outcast {
   public Outcast(WordNet wordnet)         // constructor takes a WordNet object
   public String outcast(String[] nouns)   // given an array of WordNet nouns, return an outcast
   public static void main(String[] args)  // see test client below
}
Assume that argument to outcast() contains only valid wordnet nouns (and that it contains at least two such nouns).
The following test client takes from the command line the name of a synset file, the name of a hypernym file, followed by the names of outcast files, and prints out an outcast in each file:
public static void main(String[] args) {
    WordNet wordnet = new WordNet(args[0], args[1]);
    Outcast outcast = new Outcast(wordnet);
    for (int t = 2; t < args.length; t++) {
        In in = new In(args[t]);
        String[] nouns = in.readAllStrings();
        StdOut.println(args[t] + ": " + outcast.outcast(nouns));
    }
}
http://coursera.cs.princeton.edu/algs4/checklists/wordnet.html

https://segmentfault.com/a/1190000005345079
整个作业可以分为三大部分:选择合适的结构存储结构复杂的词典及其网络关系(基本功),实现正确高效的广度优先遍历计算SAP(难点),和在此基础上一层一层更细致的优化(进阶);
本次也是checklist优化部分唯一标注optional的作业,因为的确实现起来有难度;分布如上所注。
词典(synsets)为ID与单词的多对多关系(一词多号,一号多词,释义仅供参考无需读取),上下位关系(hypernyms)是以ID为单位的树形结构(图中的箭头关系),可以明显看出hypernyms使用有向图表示,synsets存储方式取决于访问需求,因程序中正反都会使用(以词求号,以号求词,求词存在),我选择了空间换时间:
    private ArrayList<LinkedList<String>> synset; // 以号求词(获取SAP中的ancestor对应的单词)
    private HashMap<String, LinkedList<Integer>> ids; // 以词求号(获取索引单词的ID以计算SAP)
    private HashSet<String> nouns; // 求词存在(API需求功能)
    private SAP sap; // 有向图
文件读取过程稍繁琐,编程习惯要良好,保持谨慎不会错。
接着是SAP的实现,这里周旋的余地很大,一定要认真思考问题本质,并多考虑一些特殊情况检测自己的想法,再开始下手去做,并如checklist所强调,不要轻易尝试直接实现优化版本,因为细节繁琐不易考虑周全,而可能带来的潜在问题非常多,每实现一部分都要做周全的测试确保无误才行。(尽管最终成功的优化,也可能仅仅是几行的改变而已)
这里要提到的点(细节):
  • 在checklist提到的三个优化选择中,我选择了相对保守,但工作良好的优化方式:每次的搜索初始化使用HashMap构造函数;正确实现了两端同步运行的BFS,并提供了提前结束的出口;只缓存了单个ID(单个节点与单个节点)的查询结果;
  • 对单ID缓存的存储方式,我的symbol table使用了一种很直接的无重合又简单的hash计策:给定查询ID为v与w,总ID数为V,则查询结果的编号记为:
    (V-1)+(V-2)+(V-3)+...+v+(w-v),化简后为(V-1)v-(vv+v)/2+w。
  • 提前结束BFS的出口开始时没有考虑清楚,就暂时没有添加,提交的版本拿到了103.12;后来仔细思考,发现了这部分余地,仅增加了一行代码,分数便提高了不少;
  • SAP同时支持DAG与DCG(有环图),仔细分析如下这个特殊情况可能有助思考:(给定节点1与8,求其SAP)
     (Made with Graphviz)
  • BFS如由节点1先开始,则轮到第4次迭代时,节点1遍历,发现共同祖先节点5,路径距离为4+3=7,但此时不能停止搜索;实际SAP的共同祖先为1,路径距离为0+4=4,是在第4次迭代的节点8遍历部分被发现的。
public class BreadthFirstDirectedPaths {
    private static final int INFINITY = Integer.MAX_VALUE;
    private boolean[] marked;  // marked[v] = is there an s->v path?
    private int[] edgeTo;      // edgeTo[v] = last edge on shortest s->v path
    private int[] distTo;      // distTo[v] = length of shortest s->v path
    public BreadthFirstDirectedPaths(Digraph G, int s) {
        marked = new boolean[G.V()];
        distTo = new int[G.V()];
        edgeTo = new int[G.V()];
        for (int v = 0; v < G.V(); v++)
            distTo[v] = INFINITY;
        bfs(G, s);
    }
    public BreadthFirstDirectedPaths(Digraph G, Iterable<Integer> sources) {
        marked = new boolean[G.V()];
        distTo = new int[G.V()];
        edgeTo = new int[G.V()];
        for (int v = 0; v < G.V(); v++)
            distTo[v] = INFINITY;
        bfs(G, sources);
    }

    // BFS from single source
    private void bfs(Digraph G, int s) {
        Queue<Integer> q = new Queue<Integer>();
        marked[s] = true;
        distTo[s] = 0;
        q.enqueue(s);
        while (!q.isEmpty()) {
            int v = q.dequeue();
            for (int w : G.adj(v)) {
                if (!marked[w]) {
                    edgeTo[w] = v;
                    distTo[w] = distTo[v] + 1;
                    marked[w] = true;
                    q.enqueue(w);
                }
            }
        }
    }

    // BFS from multiple sources
    private void bfs(Digraph G, Iterable<Integer> sources) {
        Queue<Integer> q = new Queue<Integer>();
        for (int s : sources) {
            marked[s] = true;
            distTo[s] = 0;
            q.enqueue(s);
        }
        while (!q.isEmpty()) {
            int v = q.dequeue();
            for (int w : G.adj(v)) {
                if (!marked[w]) {
                    edgeTo[w] = v;
                    distTo[w] = distTo[v] + 1;
                    marked[w] = true;
                    q.enqueue(w);
                }
            }
        }
    }
    public boolean hasPathTo(int v) {
        return marked[v];
    }
    public int distTo(int v) {
        return distTo[v];
    }
    public Iterable<Integer> pathTo(int v) {
        if (!hasPathTo(v)) return null;
        Stack<Integer> path = new Stack<Integer>();
        int x;
        for (x = v; distTo[x] != 0; x = edgeTo[x])
            path.push(x);
        path.push(x);
        return path;
    }
}
public class SAP 
{
// constructor takes a digraph (not necessarily a DAG)
    private Digraph digraph;
    
    public SAP(Digraph G)
    {
        this.digraph = new Digraph(G);
                
    }
        
// length of shortest ancestral path between v and w; -1 if no such path
    public int length(int v, int w)
    {
        if (!isValidVertex(v) || !isValidVertex(w))
            throw new java.lang.IndexOutOfBoundsException();
        int[] result = findAncestorAndDist(v, w);
        return result[1];
    }
    
    //private String vertexRepresent(int
    
    private boolean isValidVertex(int v)
    {
        return (v >= 0 && v < this.digraph.V());
    }
// a common ancestor of v and w that participates in a shortest ancestral path;
//-1 if no such path
    public int ancestor(int v, int w)
    {
        if (!isValidVertex(v) || !isValidVertex(w))
            throw new java.lang.IndexOutOfBoundsException();
        
        int[] result = findAncestorAndDist(v, w);
        
        return result[0];
    }
    
    private int[] findAncestorAndDist(Iterable<Integer> v, Iterable<Integer> w)
    {
        BreadthFirstDirectedPaths bpdsV = new BreadthFirstDirectedPaths(digraph, v);
        BreadthFirstDirectedPaths bpdsW = new BreadthFirstDirectedPaths(digraph, w);
        
        int root = -1;
        int distance = Integer.MAX_VALUE;
        
        for (int i = 0; i < this.digraph.V(); i++)
        {
            if (bpdsV.hasPathTo(i) && bpdsW.hasPathTo(i) && bpdsV.distTo(i) 
                    + bpdsW.distTo(i) < distance)
            {
                root = i;
                distance = bpdsV.distTo(i) + bpdsW.distTo(i);
                
            }
        }
        if (distance == Integer.MAX_VALUE)
            distance = -1;
        int[] result = {root, distance};
        return result;
    }
    private int[] findAncestorAndDist(int v, int w)
    {
        BreadthFirstDirectedPaths bpdsV = new BreadthFirstDirectedPaths(digraph, v);
        BreadthFirstDirectedPaths bpdsW = new BreadthFirstDirectedPaths(digraph, w);
        
        int root = -1;
        int distance = Integer.MAX_VALUE;
        
        for (int i = 0; i < this.digraph.V(); i++)
        {
            
            if (bpdsV.hasPathTo(i) && bpdsW.hasPathTo(i) && bpdsV.distTo(i) 
                    + bpdsW.distTo(i) < distance)
            {
                root = i;
                distance = bpdsV.distTo(i) + bpdsW.distTo(i);
                
            }
        }
        if (distance == Integer.MAX_VALUE)
            distance = -1;
        int[] result = {root, distance};
        return result;
    }
    
// length of shortest ancestral path between any vertex in v and any vertex in w;
//-1 if no such path
    public int length(Iterable<Integer> v, Iterable<Integer> w)
    {
        int[] result = findAncestorAndDist(v, w);
        return result[1];
    }
        
// a common ancestor that participates in shortest ancestral path; -1 if no such path
    public int ancestor(Iterable<Integer> v, Iterable<Integer> w)
    {
        for (int i :v)
        {
            if (!isValidVertex(i))
                throw new java.lang.IndexOutOfBoundsException();
        }
        for (int i :w)
        {
            if (!isValidVertex(i))
                throw new java.lang.IndexOutOfBoundsException();
        }    
        
        int[] result = findAncestorAndDist(v, w);
        
        return result[0];
    }
}
private Map<Integer, Integer> getAncestors(int v) {
  Queue<Integer> vQ = new Queue<Integer>();
  Map<Integer, Integer> vM = new HashMap<Integer, Integer>();
  vQ.enqueue(v);
  vM.put(v, 0);
  while (!vQ.isEmpty()) {
    int head = vQ.dequeue();
    int currentDist = vM.get(head);
    for (Integer w : G.adj(head)) {
      if (!vM.containsKey(w) || vM.get(w) > currentDist + 1) {
        vQ.enqueue(w);
        vM.put(w, currentDist + 1);
      }
    }
  }
  return vM;
}

// length of shortest ancestral path between v and w; -1 if no such path
public int length(int v, int w) {
  if (v < 0 || v >= G.V())
    throw new IndexOutOfBoundsException();
  if (w < 0 || w >= G.V())
    throw new IndexOutOfBoundsException();
  Map<Integer, Integer> ancestorV = getAncestors(v);
  Map<Integer, Integer> ancestorW = getAncestors(w);
  int dist = -1;
  for (Entry<Integer, Integer> items : ancestorV.entrySet()) {
    if (ancestorW.containsKey(items.getKey())) {
      int currentDist = ancestorW.get(items.getKey())
          + items.getValue();
      if (dist < 0 || currentDist < dist)
        dist = currentDist;
    }
  }
  return dist;
}

// a common ancestor of v and w that participates in a shortest ancestral
// path; -1 if no such path
public int ancestor(int v, int w) {
  Map<Integer, Integer> ancestorV = getAncestors(v);
  Map<Integer, Integer> ancestorW = getAncestors(w);
  if (v < 0 || v >= G.V())
    throw new IndexOutOfBoundsException();
  if (w < 0 || w >= G.V())
    throw new IndexOutOfBoundsException();
  int dist = -1, anc = -1;
  for (Entry<Integer, Integer> items : ancestorV.entrySet()) {
    if (ancestorW.containsKey(items.getKey())) {
      int currentDist = ancestorW.get(items.getKey())
          + items.getValue();
      if (dist < 0 || currentDist < dist) {
        dist = currentDist;
        anc = items.getKey();
      }
    }
  }
  return anc;
}

// length of shortest ancestral path between any vertex in v and any vertex
// in w; -1 if no such path
public int length(Iterable<Integer> v, Iterable<Integer> w)
    throws IndexOutOfBoundsException {
  int dist = -1;
  for (Integer eV : v) {
    for (Integer eW : w) {
      int currentDist = length(eV, eW);
      if (currentDist > 0 && (dist < 0 || currentDist < dist))
        dist = currentDist;
    }
  }
  return dist;
}

// a common ancestor that participates in shortest ancestral path; -1 if no
// such path
public int ancestor(Iterable<Integer> v, Iterable<Integer> w)
    throws IndexOutOfBoundsException {
  int dist = -1, anc = -1;
  for (Integer eV : v) {
    for (Integer eW : w) {
      int currentDist = length(eV, eW);
      if (currentDist > 0 && (dist < 0 || currentDist < dist)) {
        dist = currentDist;
        anc = ancestor(eV, eW);
      }
    }
  }
  return anc;
}

public class WordNet 
{
    //private Digraph digraph;
    private Hashtable<String, Bag<Integer>> words;
    private ArrayList<String> synsets;
    private SAP sap;
    //private int numSynsets
    
    public WordNet(String synsets, String hypernyms)
    {
        this.words = new Hashtable<String, Bag<Integer>>();
        this.synsets = new ArrayList<String>();
        
        int numSynsets = parseSynsets(synsets);        
        Digraph digraph = parseHypernyms(hypernyms, numSynsets);
        
        this.sap = new SAP(digraph); 
        
    }
     
    private Digraph parseHypernyms(String hypernyms, int numSynsets)
    {
        Digraph digraph = new Digraph(numSynsets);
        In hyper = new In(hypernyms);
        while (!hyper.isEmpty())
        {
            String[] s = hyper.readLine().split(",");
            //if (s.length < 2) 
                //throw new java.lang.IllegalArgumentException();
            int from = Integer.parseInt(s[0]);
            for (int i = 1; i < s.length; i++)
            {
                int to = Integer.parseInt(s[i]);
                digraph.addEdge(from, to);
            }
        }
        hyper.close();
        
        // check if graph has a cycle
        DirectedCycle dc = new DirectedCycle(digraph);
        if (dc.hasCycle())
            throw new java.lang.IllegalArgumentException("Cycle detected");
        // check if one root
        int roots = 0;
        for (int v = 0; v < numSynsets; v++)
        {
            
            if (!digraph.adj(v).iterator().hasNext())
                roots++;
        }
        if (roots > 1)
            throw new java.lang.IllegalArgumentException("Multiple roots: "+roots);
        return digraph;
    }
    
    private int parseSynsets(String synsetsFN)
    {
        int count = 0;        
        
        In syns = new In(synsetsFN);
        
        while (!syns.isEmpty())
        {
            String[] s = syns.readLine().split(",");
            if (s.length < 2) 
                throw new java.lang.IllegalArgumentException();
            int id = Integer.parseInt(s[0]);
            
            this.synsets.add(id, s[1]);
            
            String[] wordsArray = s[1].split(" ");
            
            
            for (String w: wordsArray)
            {
                Bag bag;
                if (this.words.containsKey(w)) bag = this.words.get(w);
                else bag = new Bag<Integer>();
                bag.add(id);
                this.words.put(w, bag);
            }
            count++;
            
        }
        
        syns.close();
        return count;
    }
// the set of nouns (no duplicates), returned as an Iterable
    public Iterable<String> nouns()
    {
        return Collections.list(this.words.keys());
    }
    
// is the word a WordNet noun?
    public boolean isNoun(String word)
    {
        return this.words.containsKey(word);
    }
    
// distance between nounA and nounB (defined below)
    public int distance(String nounA, String nounB)
    {
        if (!isNoun(nounA) || !isNoun(nounB))
            throw new java.lang.IllegalArgumentException();
        Bag<Integer> v = this.words.get(nounA);
        Bag<Integer> w = this.words.get(nounB);
        return this.sap.length(v, w);
    }
    
// a synset (second field of synsets.txt) that is 
// the common ancestor of nounA and nounB
// in a shortest ancestral path (defined below)
    public String sap(String nounA, String nounB)
    {
        if (!isNoun(nounA) || !isNoun(nounB))
            throw new java.lang.IllegalArgumentException();
        Bag<Integer> v = this.words.get(nounA);
        Bag<Integer> w = this.words.get(nounB);
        int root = this.sap.ancestor(v, w);
        return this.synsets.get(root);
    }
}

No comments:

Post a Comment

Labels

GeeksforGeeks (976) Algorithm (811) LeetCode (654) to-do (599) Review (362) Classic Algorithm (334) Classic Interview (298) Dynamic Programming (263) Google Interview (233) LeetCode - Review (233) Tree (146) POJ (137) Difficult Algorithm (136) EPI (127) Different Solutions (119) Bit Algorithms (110) Cracking Coding Interview (110) Smart Algorithm (109) Math (91) HackerRank (85) Lintcode (83) Binary Search (73) Graph Algorithm (73) Greedy Algorithm (61) Interview Corner (61) Binary Tree (58) List (58) DFS (56) Algorithm Interview (53) Advanced Data Structure (52) Codility (52) ComProGuide (52) LeetCode - Extended (47) USACO (46) Geometry Algorithm (45) BFS (43) Data Structure (42) Mathematical Algorithm (42) ACM-ICPC (41) Jobdu (39) Interval (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) Space Optimization (34) Array (33) Trie (33) prismoskills (33) Backtracking (32) Segment Tree (32) Union-Find (32) 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 (27) GeeksQuiz (25) Logic Thinking (25) hihocoder (25) High Frequency (23) Palindrome (23) Algorithm Game (22) Company - LinkedIn (22) Graph (22) Hash (22) Queue (22) DFS + Review (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) Follow Up (17) Codercareer (16) Company-Uber (16) Game Theory (16) Heap (16) Shortest Path (16) String Search (16) Topological Sort (16) Tree Traversal (16) itint5 (16) Iterator (15) Merge Sort (15) O(N) (15) Bisection Method (14) Difficult (14) Number (14) Number Theory (14) Post-Order Traverse (14) Priority Quieue (14) Amazon Interview (13) BST (13) Basic Algorithm (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) Divide and Conquer (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) Graph BFS (8) LeetCode - DP (8) LeetCode Hard (8) Prefix Sum (8) Prime (8) Suffix Tree (8) System Design (8) Tech-Queries (8) Time Complexity (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) 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) Kadane’s Algorithm (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) 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) Matrix Chain Multiplication (5) Microsoft Interview (5) Morris Traversal (5) Pruning (5) Quadtrees (5) Quick Partition (5) Quora (5) SPFA(Shortest Path Faster Algorithm) (5) Subarray Sum (5) Sweep Line (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) Quick Sort (4) Spell Checker (4) Stock Maximize (4) Subsets (4) Sudoku (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) Master Theorem (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) 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) Parent-Only Tree (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