LeetCode 187 - Repeated DNA Sequences


The Code Sniper: 187. Repeated DNA Sequences Leetcode
All DNA is composed of a series of nucleotides abbreviated as A, C, G, and T, for example: "ACGAATTCCG". When studying DNA, it is sometimes useful to identify repeated sequences within the DNA.
Write a function to find all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule.
Example:
Input: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"

Output: ["AAAAACCCCC", "CCCCCAAAAA"]
X. Bit 
public List<String> findRepeatedDnaSequences(String s) {
    Set<Integer> words = new HashSet<>();
    Set<Integer> doubleWords = new HashSet<>();
    List<String> rv = new ArrayList<>();
    char[] map = new char[26];
    //map['A' - 'A'] = 0;
    map['C' - 'A'] = 1;
    map['G' - 'A'] = 2;
    map['T' - 'A'] = 3;

    for(int i = 0; i < s.length() - 9; i++) {
        int v = 0;
        for(int j = i; j < i + 10; j++) {
            v <<= 2;
            v |= map[s.charAt(j) - 'A'];
        }
        if(!words.add(v) && doubleWords.add(v)) {
            rv.add(s.substring(i, i + 10));
        }
    }
    return rv;
}
X. Rolling hash(bit)
Improve time complexity from O(kn) to O(n)
    public List<String> findRepeatedDnaSequences(String s) {
     if(s.length() < 11) return new ArrayList<>();
        Set<Integer> words1 = new HashSet<>();
        Set<Integer> words2 = new HashSet<>();
        List<String> res = new ArrayList<>();
        char[] map = new char[26];
        map['A' - 'A'] = 0;
        map['C' - 'A'] = 1;
        map['G' - 'A'] = 2;
        map['T' - 'A'] = 3;
        int val = 0;
        
        for(int i = 0; i < 10; i++){  // first value
      val = val << 2;
      val = val | map[s.charAt(i) - 'A'];
  }
  words1.add(val);

        for(int i = 1; i < s.length() - 9; i++){ 
      val &= ~(3 << 18);
      val = val << 2;
      val = val | map[s.charAt(i+9) - 'A'];
         if(!words1.add(val) && words2.add(val)){
          res.add(s.substring(i, i + 10));
         }
        }
        return res;
    } 
https://leetcode.com/problems/repeated-dna-sequences/discuss/53952/20-ms-solution-(C%2B%2B)-with-explanation
    public List<String> findRepeatedDnaSequences(String s) {
        if (s.length() < 10) {
            return Collections.emptyList();
        }
        List<String> ret = new ArrayList<String>();
        Map<Character, Integer> map = new HashMap<>();
        map.put('A', 0);
        map.put('C', 1);
        map.put('G', 2);
        map.put('T', 3);
        
        Set<Integer> set1 = new HashSet<>();
        Set<Integer> set2 = new HashSet<>();
        int hash = 0;
        for (int i = 0; i < 10; i++) {
            hash = hash << 2;
            hash |= map.get(s.charAt(i));
        }
        
        set1.add(hash);
        int mask = (1 << 20) - 1;
        System.out.println(Integer.toBinaryString(mask));
        for (int i = 10; i < s.length(); i++) {
            hash = (hash << 2) & mask;
            hash |= map.get(s.charAt(i));
            
            if (!set1.contains(hash)) {
                set1.add(hash);
                continue;
            }
            
            if(!set2.contains(hash)) {
                ret.add(s.substring(i - 9, i + 1));
                set2.add(hash);
            }
        }
        
        return ret;
    }
https://leetcode.com/problems/repeated-dna-sequences/discuss/53902/Short-Java-"rolling-hash"-solution
The idea is to use rolling hash technique or in case of string search also known as Rabin-Karp algorithm. As our alphabet A consists of only 4 letters we can be not afraid of collisions. The hash for a current window slice could be found in a constant time by subtracting the former first character times size of the A in the power of 9 and updating remaining hash by the standard rule: hash = hash*A.size() + curr_char.
    private static final Map<Character, Integer> A = new HashMap<>();
    static { A.put('A',0); A.put('C',1); A.put('G',2); A.put('T',3); }
    private final int A_SIZE_POW_9 = (int) Math.pow(A.size(), 9);

    public List<String> findRepeatedDnaSequences(String s) {
        Set<String> res = new HashSet<>();
        Set<Integer> hashes = new HashSet<>();
        for (int i = 0, rhash = 0; i < s.length(); i++) {
            if (i > 9) rhash -= A_SIZE_POW_9 * A.get(s.charAt(i-10));
            rhash = A.size() * rhash + A.get(s.charAt(i));
            if (i > 8 && !hashes.add(rhash)) res.add(s.substring(i-9,i+1));
        }
        return new ArrayList<>(res);
    }

Rolling hash and hashtable. 
Since there are only 4 possible letters, we can build a rolling hash with base of 5 and calculate hashcode for each 10-letter-long subsequences.
If we define code('A'):1, code('C'):2; code('G'):3; code('T'):4, Then the hashcode for the first 10-letter-long sequence will be 1*5^0+1*5^1+1*5^2+...2*5^5+...2*5^9. The advantage of rolling hash method is that we don't need to recalculate the hash code from the beginning of the next 10-letter-long sequence, we can calculate the hash code hc[i] based on last hash code hc[i-1]. hc[i]=hc[i-1]/5+code(s.charAt(i))*5^9. It is guranteed that unique DNA sequence will have unique hashcode. By using a hashtable, we can see whether the sequence is occurred more than once.
public List<String> findRepeatedDnaSequences(String s) {  
     List<String> res=new ArrayList<String>();  
     if(s==null || s.length()<10) return res;  
     HashMap<Integer,Integer> map=new HashMap<Integer,Integer>();  
     int hashCode=0;  
     int base=1;  
     for(int i=0;i<10;i++){  
       hashCode+=getCode(s.charAt(i))*base;  
       base*=5;  
     }  
    map.put(hashCode,1);  
    base=base/5;  
    for(int i=10;i<s.length();i++){  
      hashCode=hashCode/5+getCode(s.charAt(i))*base;  
      if(!map.containsKey(hashCode)) map.put(hashCode,1);  
      else{  
        if(map.get(hashCode)==1) {  
          res.add(s.substring(i-9,i+1));  
          map.put(hashCode,2);  
        }  
      }  
    }  
    return res;  
   }  
   public int getCode(char c){  
     switch (c){  
     case 'A': return 1;  
     case 'C': return 2;  
     case 'G': return 3;  
     case 'T': return 4;  
     default: return 0;  
     }  
   }

https://zyfu0408.gitbooks.io/interview-preparation/content/bit-manipulation/storer-information-by-bit.html
A C G T4个character能够用0，1，2，3这个四个数字表示，也就是00，01，01，和11，每个只占用了2位，DNA sequence是10个连续的character，也就是能用20位来表达。一个int能够包含32位，因此我们可以用int来表示DNA sequence
    public List<String> findRepeatedDnaSequences(String s) {
        List<String> result = new ArrayList<String>();
        if (s == null || s.length() < 10) {
            return result;
        }

        Map<Character, Integer> map = new HashMap<Character, Integer>();
        map.put('A', 0);
        map.put('C', 1);
        map.put('G', 2);
        map.put('T', 3);

        Set<Integer> dna = new HashSet<Integer>();
        for (int i = 9; i < s.length(); i++) {
            int k = 0, num = 0;
            for (int j = i - 9; j <= i; j++) {
                int n = map.get(s.charAt(j));
                num |= n << k;
                k += 2;
            }
            if (dna.contains(num)) {
                String str = s.substring(i - 9, i + 1);
                if (!result.contains(str)) {
                    result.add(str);
                }
            }
            dna.add(num);
        }
        return result;
    }
https://leetcode.com/discuss/25399/clean-java-solution-hashmap-bits-manipulation
public List<String> findRepeatedDnaSequences(String s) { Set<Integer> words = new HashSet<>(); Set<Integer> doubleWords = new HashSet<>(); List<String> rv = new ArrayList<>(); char[] map = new char[26]; //map['A' - 'A'] = 0; map['C' - 'A'] = 1; map['G' - 'A'] = 2; map['T' - 'A'] = 3; for(int i = 0; i < s.length() - 9; i++) { int v = 0; for(int j = i; j < i + 10; j++) { v <<= 2; v |= map[s.charAt(j) - 'A']; } if(!words.add(v) && doubleWords.add(v)) { rv.add(s.substring(i, i + 10)); } } return rv; }
Improve a little bit. Maintain a size 10 window rather than loop through every time.
public List<String> findRepeatedDnaSequences(String s) { List<String> result = new ArrayList<>(); Set<Integer> word = new HashSet<>(); Set<Integer> secondWord = new HashSet<>(); int[] map = new int[26]; map['C' - 'A'] = 1; map['G' - 'A'] = 2; map['T' - 'A'] = 3; int value = 0; for (int i = 0; i < s.length(); i++) { value <<= 2; value |= map[s.charAt(i) - 'A']; value &= 0xfffff;//?? if (i < 9) { continue; } if (!word.add(value) && secondWord.add(value)) { result.add(s.substring(i - 9, i + 1)); } } return result; }
https://leetcode.com/discuss/46948/accepted-java-easy-to-understand-solution
public List<String> findRepeatedDnaSequences(String s) {
    List<String> list = new ArrayList<String>();
    if (s == null || s.length() < 10) return list;
    HashMap<Integer, Boolean> map = new HashMap<Integer, Boolean>();

    for (int i = 0; i + 10 <= s.length(); i++ ) {
        int hash = stringToHash(s.substring(i, i + 10));
        if (map.containsKey(hash)) {
            if (!map.get(hash)) {
                list.add(s.substring(i, i + 10));
                map.put(hash, true);
            }
        } else {
            map.put(hash, false);
        }
    }
    return list;
}

private int stringToHash (String s) {
    String numberBuilder = "";
    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) == 'A') numberBuilder += "0";
        if (s.charAt(i) == 'C') numberBuilder += "1"; // add else
        if (s.charAt(i) == 'G') numberBuilder += "2";
        if (s.charAt(i) == 'T') numberBuilder += "3";
    }
    return Integer.parseInt(numberBuilder, 4);
}
Thanking for the suggestions by TWiStErRob at el. the stringToHash function can be implemented to be more efficient. Here TWiStErRob's code for it
private int stringToHash(String s) {
    int numberBuilder = 0;
    for (int i = 0; i < s.length(); i++) {
        numberBuilder *= 4;
             if (s.charAt(i) == 'A') numberBuilder += 0;
        else if (s.charAt(i) == 'C') numberBuilder += 1;
        else if (s.charAt(i) == 'G') numberBuilder += 2;
        else if (s.charAt(i) == 'T') numberBuilder += 3;
    }
    return numberBuilder;
}

private int stringToHash(String s) { int numberBuilder = 0; for (int i = 0; i < s.length(); i++) { numberBuilder <<= 2; if (s.charAt(i) == 'A') numberBuilder |= 0b00; else if (s.charAt(i) == 'C') numberBuilder |= 0b01; else if (s.charAt(i) == 'G') numberBuilder |= 0b10; else if (s.charAt(i) == 'T') numberBuilder |= 0b11; } return numberBuilder; }
http://betterpoetrythancode.blogspot.com/2015/02/repeated-dna-sequences-leetcode-bit.html
Idea: Create a HashMap<bit representation of substring, appeared times>. For each 10 letter window, calculate its bit representation as the key. Then slide the window from left to right, if the key shows up exactly twice, append the substring to the result.

Time: O(n) Space: O(n)
// substring is not efficient.
   public List<String> findRepeatedDnaSequences(String s) {  
     List<String> result=new ArrayList<String>();  
     HashMap<Integer,Integer> computed=new HashMap<Integer,Integer>();  
     for(int i=0;i<=s.length()-10;i++)  
     {  
       String sub=s.substring(i,i+10);  // slow
       int key=getKey(sub);  
       if(computed.containsKey(key))  
       {  
         computed.put(key,computed.get(key)+1);  
         if(computed.get(key)==2)  
           result.add(sub);  
       }  
       else  
         computed.put(key,1);  
     }  
     return result;  
   }  
   public int getKey(String s)  
   {  
     int result=0;  
     for(int i=s.length()-1;i>=0;i--)  
     {  
       int b=0;  
       switch(s.charAt(i))  
       {  
         case 'A':  
           b|=0;  
           break;  
         case 'T':  
           b|=1;  
           break;  
         case 'G':  
           b|=2;  
           break;  
         case 'C':  
           b|=3;  
           break;  
       }  
       result=b|result;  
       result=result<<2;  
     }  
     return result;  
   }
https://codesolutiony.wordpress.com/2015/02/10/repeated-dna-sequences/
    public List<String> findRepeatedDnaSequences(String s) {
        List<String> result = new ArrayList<String>();
        Map<Character, Integer> map = new HashMap<Character, Integer>();
        map.put('A', 0);
        map.put('C', 1);
        map.put('G', 2);
        map.put('T', 3);
        if (s == null || s.length() < 10) {
            return new ArrayList<String>();
        }
        Set<Integer> unique = new HashSet<Integer>();
        Set<Integer> set = new HashSet<Integer>();
        for (int i = 0; i + 10 <= s.length(); i++) {
            int value = 0;
            for (int index = i; index < i+10; index++) {
                value = (value << 2) | map.get(s.charAt(index));
            }
            if (set.contains(value) && !unique.contains(value)) {
                result.add(s.substring(i, i+10));
                unique.add(value);
            } else {
                set.add(value);
            }
        }
        return result;
    }

    public List<String> findRepeatedDnaSequences(String s) {
        Set<String> result = new HashSet<String>();
        if (s == null || s.length() < 10) {
            return new ArrayList<String>();
        }
        int targetHash = 0, resHash = 0, base = 7, multiplies = 1;
        for (int i = 0; i < 10; i++) {
            targetHash = targetHash * base + s.charAt(i);
            multiplies *= base;
        }
        multiplies /= base;
        Set<Integer> set = new HashSet<Integer>();
        set.add(targetHash);
        for (int i = 1; i + 10 <= s.length(); i++) {
            targetHash = (targetHash - multiplies * s.charAt(i-1)) * base + s.charAt(i + 9);
            if (set.contains(targetHash)) {
                result.add(s.substring(i, i+10));
            } else {
                set.add(targetHash);
            }
        }
        return new ArrayList<String>(result);
    }
http://www.programcreek.com/2014/03/leetcode-repeated-dna-sequences-java/
http://likesky3.iteye.com/blog/2236004
此题思路是容易想到的，遍历输入字符串的每个长度为10的substring，利用HashMap 检查其出现次数，出现两次或者以上的则加入到结果中。 
实现时仅当某个substring第二次出现时加入结果可避免结果中出现重复字符串。但直接实现会得到Memory Limit Exceed，就是程序内存开销太大了。 
此题的关键就是要将那些待检查的substring转换为int来节省内存，如何高效的编码substring？共4个字符，ACGT,可用两个bit区分它们，分别是00,01,10,11, 
参考解答中的掩码技巧值得学习，使用一个20位的数字0x3ffff称为eraser，每次要更新一位字符时，将老的编码hint & eraser, 然后左移两位，然后加上新字符对应的编码， 
这样就得到了新substring的编码，很巧妙~ 
  1.     // Method 2: hashmap store int instead of string to bypass MLE  
  2.     public static final int eraser = 0x3ffff;  
  3.     public static HashMap<Character, Integer> ati = new HashMap<Character, Integer>();  
  4.     static {  
  5.         ati.put('A', 0);  
  6.         ati.put('C', 1);  
  7.         ati.put('G', 2);  
  8.         ati.put('T', 3);  
  9.     }  
  10.     public List<String> findRepeatedDnaSequences(String s) {  
  11.         List<String> result = new ArrayList<String>();  
  12.         if (s == null || s.length() <= 10)  
  13.             return result;  
  14.         int N = s.length();  
  15.         int hint = 0;  
  16.         for (int i = 0; i < 10; i++) {  
  17.             hint = (hint << 2) + ati.get(s.charAt(i));  
  18.         }  
  19.         HashMap<Integer, Integer> checker = new HashMap<Integer, Integer>();  
  20.         checker.put(hint, 1);  
  21.         for (int i = 10; i < N; i++) {  
  22.             hint = ((hint & eraser) << 2) + ati.get(s.charAt(i));  
  23.             Integer value = checker.get(hint);  // Count Map
  24.             if (value == null) {  
  25.                 checker.put(hint, 1);  
  26.             } else if (value == 1) {  
  27.                 checker.put(hint, value + 1);  // this is not needed.
  28.                 result.add(s.substring(i - 9, i + 1));  // could we avoid substring?
  29.             }  
  30.         }  
  31.         return result;  
  32.     }  

  1.     // Method 1: Memory Limit Exceed & may contain duplicates  
  2.     public List<String> findRepeatedDnaSequences1(String s) {  
  3.         HashMap<String, Integer> map = new HashMap<String, Integer>();  
  4.         int last = s.length() - 10;  
  5.         for (int i = 0; i <= last; i++) {  
  6.             String key = s.substring(i, i + 10);  
  7.             if (map.containsKey(key)) {  
  8.                 map.put(key, map.get(key) + 1);  
  9.             } else {  
  10.                 map.put(key, 1);  
  11.             }  
  12.         }  
  13.         List<String> result = new ArrayList<String>();  
  14.         for (String key : map.keySet()) {  
  15.             if (map.get(key) > 1)  
  16.                 result.add(key);  
  17.         }  
  18.         return result;  
  19.     } 
http://www.shuatiblog.com/blog/2015/05/01/Repeated-DNA-Sequences/
    public List<String> findRepeatedDnaSequences(String s) {
        List<String> res = new ArrayList<String>();
        if (s == null || s.length() < 10) {
            return res;
        }

        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        // map<> stores int-to-int: first int is "ACGT" -> 1234
        // second int is the init position of the pattern in s

        int num = 0;
        int mask = 0xFFFFFFFF;
        mask >>>= (32 - 18);

        for (int i = 0; i < s.length(); i++) {
            num = mask & num;
            // get the last 18 binary digits of num

            num = (num << 2) | convertChatToInt(s.charAt(i));
            // append num with the number representing charAt(i)

            if (i >= 9) {
                // insert or search num in the map
                if (!map.containsKey(num)) {
                    map.put(num, (i - 9));
                    // (i - 9) is the start position of 
                    // the 10-letter-long sequence
                } else if (map.get(num) != -1) {
                    res.add(s.substring(map.get(num), map.get(num) + 10));
                    map.put(num, -1);
                    // after the sequence has been added, mark it in the map
                } else {
                    // do nothing
                }
            }
        }

        return res;
    }

    int convertChatToInt(char ch) {
        if (ch == 'A') {
            return 1;
        } else if (ch == 'C') {
            return 2;
        } else if (ch == 'G') {
            return 3;
        }
        return 0;
    }
http://segmentfault.com/a/1190000003922976
哈希表法
时间 O(N) 空间 O(N)
最简单的做法，我们可以把位移一位后每个子串都存入哈希表中，如果哈希表中已经有这个子串，而且是第一次重复，则加入结果中。如果已经遇到多次，则不加入结果中。如果哈希表没有这个子串，则把这个子串加入哈希表中。
    public List<String> findRepeatedDnaSequences(String s) {
        List<String> res = new LinkedList<String>();
        HashMap<String, Integer> map = new HashMap<String, Integer>();
        for(int index = 10; index <= s.length(); index++){
            // 从第10位开始作为结尾，位移一位，比较一次子串
            String substr = s.substring(index - 10, index);
            if(map.containsKey(substr)){
                // 如果是第一次遇到，则加入结果
                if(map.get(substr) == 1){
                    res.add(substr);
                }
                // 标记为已经遇到过一次了
                map.put(substr, 2); // the real count doesn't mater
            } else {
                // 如果不存在，则加入表中
                map.put(substr, 1);
            }
        }
        return res;
    }
编码法
We can do better.
时间 O(N) 空间 O(N)
思路
实际上我们的哈希表可以不用存整个子串，因为我们知道子串只有10位，且每一位只可能有4种不同的字母，那我们可以用4^10个数字来表示每种不同的序列，因为4^10=2^20<2^32所以我们可以用一个Integer来表示。具体的编码方法是用每两位bit表示一个字符。
    public List<String> findRepeatedDnaSequences(String s) {
        List<String> res = new LinkedList<String>();
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        for(int index = 10; index <= s.length(); index++){
            String substr = s.substring(index - 10, index);
            int code = encode(substr);
            if(map.containsKey(code)){
                if(map.get(code) == 1){
                    res.add(substr);
                }
                map.put(code, 2);
            } else {
                map.put(code, 1);
            }
        }
        return res;
    }
    
    private int encode(String str){
        int code = 0;
        for(int i = 0; i < str.length(); i++){
            char c = str.charAt(i);
            // 每两位表示一个字符
            code <<= 2;
            switch(c){
                case 'A': code += 0; break;
                case 'C': code += 1; break;
                case 'T': code += 2; break;
                case 'G': code += 3; break;
            }
        }
        return code;
    }
https://leetcode.com/discuss/64841/7-lines-simple-java-o-n
public List<String> findRepeatedDnaSequences(String s) { Set seen = new HashSet(), repeated = new HashSet(); for (int i = 0; i + 9 < s.length(); i++) { String ten = s.substring(i, i + 10); if (!seen.add(ten)) repeated.add(ten); } return new ArrayList(repeated); }
LeetCode Extended:
http://www.1point3acres.com/bbs/thread-147555-1-1.html
是要求按大小顺序输出来着，alphabetical order。我直接用的是int array，没有被要求用bit vector来优化了~
hash函数把结果变成整数，范围是0到4^10 - 1， 然后直接用一个这么大的数组来记录结果。之后遍历数组，把找到的结果reverse hash回去~
一共有三种状态吧：0次出现，1次出现，至少两次出现。然后用两个bit来表示这三种状态咯。bit的读取和改变就用and， or之类的bitwise operator来做吧
Read full article from The Code Sniper: 187. Repeated DNA Sequences Leetcode
at
Labels: , , , ,

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts

  • Archives
  • HackerRank: Pacman A*
    HackerRank: Pacman A* In the previous game, you performed UCS on the PacMan grid. In this game we use AStar algorithm to reduce the nodes...
  • LeetCode 471 - Encode String with Shortest Length
    Related:  LeetCode 394 - Decode String http://bookshadow.com/weblog/2016/12/11/leetcode-encode-string-with-shortest-length/ Given a  non...
  • HackerRank: PacMan - BFS
    HackerRank: PacMan - BFS In the previous game, you performed DFS on the PacMan grid. It was seen that DFS might not always give the short...
  • DropBox Interview Misc
    https://paper.dropbox.com/doc/Interview-Notes-Dropbox-wl7npLjRBjrAKA5AOBsaM Behavioural https://www.paysa.com/blog/2017/04/05/what-to...
  • Buttercola: Buddy System
    Buttercola: Buddy System Given a complete binary tree with nodes of values of either 1 or 0, the following rules always hold: 1. A node...
  • LeetCode 988 - Smallest String Starting From Leaf
    https://leetcode.com/problems/smallest-string-starting-from-leaf/ Given the  root  of a binary tree, each node has a value from  0  to  2...
  • LeetCode 752 - Open the Lock
    https://leetcode.com/problems/open-the-lock/description/ You have a lock in front of you with 4 circular wheels. Each wheel has 10 slot...
  • Greedy Algorithms | Set 3 (Huffman Coding) | GeeksforGeeks
    Greedy Algorithms | Set 3 (Huffman Coding) | GeeksforGeeks Huffman coding is a lossless data compression algorithm. The idea is to assign ...
  • Simple Text Editor - HackerRank
    https://www.hackerrank.com/challenges/simple-text-editor In this problem, your task is to implement a simple text editor. Initially, a fi...