Monday, March 20, 2017

LeetCode 535 - Encode and Decode TinyURL


https://leetcode.com/problems/encode-and-decode-tinyurl/
TinyURL is a URL shortening service where you enter a URL such as https://leetcode.com/problems/design-tinyurl and it returns a short URL such as http://tinyurl.com/4e9iAk.
Design the encode and decode methods for the TinyURL service. There is no restriction on how your encode/decode algorithm should work. You just need to ensure that a URL can be encoded to a tiny URL and the tiny URL can be decoded to the original URL.
X.
https://mikecoder.github.io/oj-code/2017/03/04/EncodeandDecodeTinyURL/
map<string, string> urls;
string hash(string url) {
long long hash = 0;
for (int i = 0; i < (int)url.length(); i++) {
hash = hash * 10 + url[i];
}
return to_string(hash);
}
string encode(string longUrl) {
string key = hash(longUrl);
urls.insert(pair<string, string>(key, longUrl));
return key;
}
string decode(string shortUrl) {
return urls.find(shortUrl)->second;
}
http://xiadong.info/2017/03/leetcode-535-encode-and-decode-tinyurl/
短链接的维护,但不限制内部如何生成短链接。就是Hash表的问题,我直接使用的unordered_map容器所提供的Hash函数对原链接进行处理,得到一个数值,然后将该数值转换为62进制字符串(10个数字+大小写字母各26个),该字符串作为短链接的后缀部分。
class Solution {
    string tinyUrlPrefix = "http://tinyurl.com/";
    unordered_map<string, string> urls;
public:
    // Encodes a URL to a shortened URL.
    string encode(string longUrl) {
        auto hashFunc = urls.hash_function();
        size_t key = hashFunc(longUrl);
        string shortUrl = tinyUrlPrefix + convertToSixtyTwoBase(key);
        urls[shortUrl] = longUrl;
        return shortUrl;
    }
    // Decodes a shortened URL to its original URL.
    string decode(string shortUrl) {
        return urls[shortUrl];
    }
    
    string convertToSixtyTwoBase (size_t key) {
        string str;
        while (key > 0) {
            int mod = key % 62;
            if (mod < 10) str.push_back(mod + '0');
            else if (mod < 36) str.push_back(mod - 10 + 'a');
            else str.push_back(mod - 36 + 'A');
            key /= 62;
        }
        return str;
    }
};
https://discuss.leetcode.com/topic/82273/three-different-approaches-in-java
Approach 1- Using simple counter
public class Codec {
    Map<Integer, String> map = new HashMap<>();
    int i=0;
    public String encode(String longUrl) {
        map.put(i,longUrl);
        return "http://tinyurl.com/"+i++;
    }
    public String decode(String shortUrl) {
        return map.get(Integer.parseInt(shortUrl.replace("http://tinyurl.com/", "")));
    }
}
https://discuss.leetcode.com/topic/81637/two-solutions-and-thoughts
https://discuss.leetcode.com/topic/81633/easy-solution-in-java-5-line-code
My first solution produces short URLs like http://tinyurl.com/0http://tinyurl.com/1, etc, in that order.
class Codec:

    def __init__(self):
        self.urls = []

    def encode(self, longUrl):
        self.urls.append(longUrl)
        return 'http://tinyurl.com/' + str(len(self.urls) - 1)

    def decode(self, shortUrl):
        return self.urls[int(shortUrl.split('/')[-1])]
Using increasing numbers as codes like that is simple but has some disadvantages, which the below solution fixes:
  • If I'm asked to encode the same long URL several times, it will get several entries. That wastes codes and memory.
  • People can find out how many URLs have already been encoded. Not sure I want them to know.
  • People might try to get special numbers by spamming me with repeated requests shortly before their desired number comes up.
  • Only using digits means the codes can grow unnecessarily large. Only offers a million codes with length 6 (or smaller). Using six digits or lower or upper case letters would offer (10+26*2)6 = 56,800,235,584 codes with length 6.
The following solution doesn't have these problems. It produces short URLs like http://tinyurl.com/KtLa2U, using a random code of six digits or letters. If a long URL is already known, the existing short URL is used and no new entry is generated.
class Codec:

    alphabet = string.ascii_letters + '0123456789'

    def __init__(self):
        self.url2code = {}
        self.code2url = {}

    def encode(self, longUrl):
        while longUrl not in self.url2code:
            code = ''.join(random.choice(Codec.alphabet) for _ in range(6))
            if code not in self.code2url:
                self.code2url[code] = longUrl
                self.url2code[longUrl] = code
        return 'http://tinyurl.com/' + self.url2code[longUrl]

    def decode(self, shortUrl):
        return self.code2url[shortUrl[-6:]]
It's possible that a randomly generated code has already been generated before. In that case, another random code is generated instead. Repeat until we have a code that's not already in use. How long can this take? Well, even if we get up to using half of the code space, which is a whopping 626/2 = 28,400,117,792 entries, then each code has a 50% chance of not having appeared yet. So the expected/average number of attempts is 2, and for example only one in a billion URLs takes more than 30 attempts. And if we ever get to an even larger number of entries and this does become a problem, then we can just use length 7. We'd need to anyway, as we'd be running out of available codes.
    Map<String, String> index = new HashMap<String, String>();
    Map<String, String> revIndex = new HashMap<String, String>();
    static String BASE_HOST = "http://tinyurl.com/";
    
    // Encodes a URL to a shortened URL.
    public String encode(String longUrl) {
        if (revIndex.containsKey(longUrl)) return BASE_HOST + revIndex.get(longUrl);
        String charSet = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
        String key = null;
        do {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < 6; i++) {
                int r = (int) (Math.random() * charSet.length());
                sb.append(charSet.charAt(r));
            }
            key = sb.toString();
        } while (index.containsKey(key));
        index.put(key, longUrl);
        revIndex.put(longUrl, key);
        return BASE_HOST + key;
    }

    // Decodes a shortened URL to its original URL.
    public String decode(String shortUrl) {
        return index.get(shortUrl.replace(BASE_HOST, ""));
    }

https://discuss.leetcode.com/topic/81620/maybe-base64
Your solution, while terse, totally misses the point of the question. Encoding is valuable as long as you can send back a "shorter" URL; your method seems to generate much longer URLs than the supplied input.
import java.nio.charset.StandardCharsets;
import java.util.Base64;

public class Codec {
    public String encode(String longUrl) {
        return Base64.getUrlEncoder().encodeToString(longUrl.getBytes(StandardCharsets.UTF_8));
    }

    public String decode(String shortUrl) {
        return new String(Base64.getUrlDecoder().decode(shortUrl));
    }
}
X. http://blog.csdn.net/jmspan/article/details/51740066
一般的数据库进行horizontal shard的方法是指,把 id 对 数据库服务器总数 n 取模,然后来得到他在哪台机器上。这种方法的缺点是,当数据继续增加,我们需要增加数据库服务器,将 n 变为 n+1 时,几乎所有的数据都要移动,这就造成了不 consistent。为了减少这种 naive 的 hash方法(%n) 带来的缺陷,出现了一种新的hash算法:一致性哈希的算法——Consistent Hashing。这种算法有很多种实现方式,这里我们来实现一种简单的 Consistent Hashing。
  1. 将 id 对 360 取模,假如一开始有3台机器,那么让3台机器分别负责0~119, 120~239, 240~359 的三个部分。那么模出来是多少,查一下在哪个区间,就去哪台机器。
  2. 当机器从 n 台变为 n+1 台了以后,我们从n个区间中,找到最大的一个区间,然后一分为二,把一半给第n+1台机器。
  3. 比如从3台变4台的时候,我们找到了第3个区间0~119是当前最大的一个区间,那么我们把0~119分为0~59和60~119两个部分。0~59仍然给第1台机器,60~119给第4台机器。
  4. 然后接着从4台变5台,我们找到最大的区间是第3个区间120~239,一分为二之后,变为 120~179, 180~239。
假设一开始所有的数据都在一台机器上,请问加到第 n 台机器的时候,区间的分布情况和对应的机器编号分别是多少?
 Notice
你可以假设 n <= 360. 同时我们约定,当最大区间出现多个时,我们拆分编号较小的那台机器。
比如0~119, 120~239区间的大小都是120,但是前一台机器的编号是1,后一台机器的编号是2, 所以我们拆分0~119这个区间。
Clarification
If the maximal interval is [x, y], and it belongs to machine id z, when you add a new machine with id n, you should divide [x, y, z] into two intervals:
[x, (x + y) / 2, z] and [(x + y) / 2 + 1, y, n]
Example
for n = 1, return
[
  [0,359,1]
]
represent 0~359 belongs to machine 1.
for n = 2, return
[
  [0,179,1],
  [180,359,2]
]
for n = 3, return
[
  [0,89,1]
  [90,179,3],
  [180,359,2]
]
for n = 4, return
[
  [0,89,1],
  [90,179,3],
  [180,269,2],
  [270,359,4]
]
for n = 5, return
[
  [0,44,1],
  [45,89,5],
  [90,179,3],
  [180,269,2],
  [270,359,4]
]
方法:使用堆来维护区间。
  1.     public List<List<Integer>> consistentHashing(int n) {  
  2.         // Write your code here  
  3.         PriorityQueue<Range> heap = new PriorityQueue<>(16,   
  4.             new Comparator<Range>() {  
  5.                 @Override  
  6.                 public int compare(Range r1, Range r2) {  
  7.                     if (r1.to - r1.from > r2.to - r2.from) return -1;  
  8.                     if (r1.to - r1.from < r2.to - r2.from) return 1;  
  9.                     return r1.id - r2.id;  
  10.                 }  
  11.             }  
  12.         );  
  13.         heap.offer(new Range(10359));  
  14.         for(int i = 2; i <= n; i++) {  
  15.             Range range = heap.poll();  
  16.             Range range1 = new Range(range.id, range.from, (range.from+range.to)/2);  
  17.             Range range2 = new Range(i, (range.from+range.to)/2+1, range.to);  
  18.             heap.offer(range1);  
  19.             heap.offer(range2);  
  20.         }  
  21.         Range[] ranges = heap.toArray(new Range[0]);  
  22.         List<List<Integer>> results = new ArrayList<>(ranges.length);  
  23.         for(int i = 0; i < ranges.length; i++) {  
  24.             List<Integer> result = new ArrayList<>(3);  
  25.             result.add(ranges[i].from);  
  26.             result.add(ranges[i].to);  
  27.             result.add(ranges[i].id);  
  28.             results.add(result);  
  29.         }  
  30.         return results;  
  31.     }  
  32. class Range {  
  33.     int id;  
  34.     int from, to;  
  35.     Range(int id, int from, int to) {  
  36.         this.id = id;  
  37.         this.from = from;  
  38.         this.to = to;  
  39.     }  
http://www.jianshu.com/p/002473c378c3
    vector<vector<int>> consistentHashing(int n) {
        // Write your code here
        vector<vector<int>> ret;
        vector<int> range;
        range.push_back(0);
        range.push_back(359);
        range.push_back(1);
        ret.push_back(range);

        for(int i = 2; i <= n; i++) {
            int maxRange = INT_MIN;
            int index = -1;
            for(int j = 0; j < ret.size(); j++) {
                if (maxRange < ret[j][1] - ret[j][0]) {
                    maxRange = ret[j][1] - ret[j][0];
                    index = j;
                }
            }

            int mid = (ret[index][1] + ret[index][0]) / 2;
            int end = ret[index][1];
            ret[index][1] = mid;
            range[0] = mid + 1;
            range[1] = end;
            range[2] = i;
            ret.push_back(range);
        }

        return ret;
    }


X. http://blog.csdn.net/jmspan/article/details/51749521
在 Consistent Hashing I 中我们介绍了一个比较简单的一致性哈希算法,这个简单的版本有两个缺陷:
  1. 增加一台机器之后,数据全部从其中一台机器过来,这一台机器的读负载过大,对正常的服务会造成影响。
  2. 当增加到3台机器的时候,每台服务器的负载量不均衡,为1:1:2。
为了解决这个问题,引入了 micro-shards 的概念,一个更好的算法是这样:
  1. 将 360° 的区间分得更细。从 0~359 变为一个 0 ~ n-1 的区间,将这个区间首尾相接,连成一个圆。
  2. 当加入一台新的机器的时候,随机选择在圆周中撒 k 个点,代表这台机器的 k 个 micro-shards。
  3. 每个数据在圆周上也对应一个点,这个点通过一个 hash function 来计算。
  4. 一个数据该属于那台机器负责管理,是按照该数据对应的圆周上的点在圆上顺时针碰到的第一个 micro-shard 点所属的机器来决定。
n 和 k在真实的 NoSQL 数据库中一般是 2^64 和 1000。
请实现这种引入了 micro-shard 的 consistent hashing 的方法。主要实现如下的三个函数:
  1. create(int n, int k)
  2. addMachine(int machine_id) // add a new machine, return a list of shard ids.
  3. getMachineIdByHashCode(int hashcode) // return machine id
 Notice
当 n 为 2^64 时,在这个区间内随机基本不会出现重复。
但是为了方便测试您程序的正确性,n 在数据中可能会比较小,所以你必须保证你生成的 k 个随机数不会出现重复。
LintCode并不会判断你addMachine的返回结果的正确性(因为是随机数),只会根据您返回的addMachine的结果判断你getMachineIdByHashCode结果的正确性。
create(100, 3)
addMachine(1)
>> [3, 41, 90]  => 三个随机数
getMachineIdByHashCode(4)
>> 1
addMachine(2)
>> [11, 55, 83]
getMachineIdByHashCode(61)
>> 2
getMachineIdByHashCode(91)
>> 1

  1.     private TreeMap<Integer, Integer> tm = new TreeMap<>();  
  2.       
  3.     private int[] nums;  
  4.     private int size = 0;  
  5.     private int k;  
  6.       
  7.     public Solution(int n, int k) {  
  8.         this.nums = new int[n];  
  9.         for(int i = 0; i < n; i++) this.nums[i] = i;  
  10.           
  11.         Random random = new Random();  
  12.         for(int i = 0; i < n; i++) {  
  13.             int j = random.nextInt(i + 1);  
  14.             int t = nums[i];  
  15.             nums[i] = nums[j];  
  16.             nums[j] = t;  
  17.         }  
  18.         this.k = k;  
  19.     }  
  20.       
  21.     // @param n a positive integer  
  22.     // @param k a positive integer  
  23.     // @return a Solution object  
  24.     public static Solution create(int n, int k) {  
  25.         // Write your code here  
  26.         return new Solution(n, k);  
  27.     }  
  28.   
  29.     // @param machine_id an integer  
  30.     // @return a list of shard ids  
  31.     public List<Integer> addMachine(int machine_id) {  
  32.         // Write your code here  
  33.         List<Integer> ids = new ArrayList<>();  
  34.         for(int i = 0; i < this.k; i++) {  
  35.             int id = this.nums[size++ % this.nums.length];  
  36.             ids.add(id);  
  37.             this.tm.put(id, machine_id);  
  38.         }  
  39.         return ids;  
  40.     }  
  41.   
  42.     // @param hashcode an integer  
  43.     // @return a machine id  
  44.     public int getMachineIdByHashCode(int hashcode) {  
  45.         // Write your code here  
  46.         if (tm.isEmpty()) return 0;  
  47.         Integer ceiling = tm.ceilingKey(hashcode);  
  48.         if (ceiling != nullreturn tm.get(ceiling);  
  49.         return tm.get(tm.firstKey());  
  50.     }  

http://www.jianshu.com/p/4b39053a7a24
https://github.com/zxqiu/leetcode-lintcode/blob/master/system%20design/Consistent_Hashing_II.java
public class Solution {
    static int[] hashToMachine;
    static int shardsPerMachine;
    static int maxShards;
    static int availableShards;

    // @param n a positive integer
    // @param k a positive integer
    // @return a Solution object
    public static Solution create(int n, int k) {
        Solution solution = new Solution();
       
        solution.maxShards = n;
        solution.shardsPerMachine = k;
        solution.availableShards = n;
        solution.hashToMachine = new int[n];
       
        Arrays.fill(hashToMachine, -1);
       
        return solution;
    }

    // @param machine_id an integer
    // @return a list of shard ids
    public List<Integer> addMachine(int machine_id) {
        if (shardsPerMachine > availableShards) {
            return new ArrayList<Integer>();
        }
       
        List<Integer> shards = randomNumber();
       
        for (Integer i : shards) {
            hashToMachine[i] = machine_id;
        }
       
        availableShards -= shardsPerMachine;
        Collections.sort(shards);
        return shards;
    }

    // @param hashcode an integer
    // @return a machine id
    public int getMachineIdByHashCode(int hashcode) {
        int ret = hashcode % maxShards;
       
        while (hashToMachine[ret] == -1) {
            ret = (ret + 1) % maxShards;
        }
       
        return hashToMachine[ret];
    }
   
    private static List<Integer> randomNumber() {
        Set<Integer> dupCheck = new HashSet<Integer>();
        List<Integer> ret = new ArrayList<Integer>();
        Random r = new Random();
       
        while (ret.size() < shardsPerMachine) {
            int candidate = r.nextInt(maxShards);
           
            if (dupCheck.contains(candidate) || hashToMachine[candidate] != -1) {
                continue;
            }
           
            ret.add(candidate);
            dupCheck.add(candidate);
        }
       
        return ret;
    }


No comments:

Post a Comment

Labels

GeeksforGeeks (1109) LeetCode (1095) Review (846) Algorithm (795) to-do (633) LeetCode - Review (574) Classic Algorithm (324) Dynamic Programming (294) Classic Interview (288) Google Interview (242) Tree (145) POJ (139) Difficult Algorithm (132) LeetCode - Phone (127) EPI (125) Bit Algorithms (120) Different Solutions (120) Lintcode (113) Cracking Coding Interview (110) Smart Algorithm (109) Math (108) HackerRank (89) Binary Search (83) Binary Tree (82) Graph Algorithm (76) Greedy Algorithm (73) DFS (71) Stack (65) LeetCode - Extended (62) Interview Corner (61) List (58) Advanced Data Structure (56) BFS (54) Codility (54) ComProGuide (52) Algorithm Interview (50) Geometry Algorithm (49) Trie (49) Binary Search Tree (47) USACO (46) Interval (45) LeetCode Hard (42) Mathematical Algorithm (42) ACM-ICPC (41) Data Structure (40) Knapsack (40) Space Optimization (40) Jobdu (39) Matrix (39) Recursive Algorithm (39) String Algorithm (38) Union-Find (37) Backtracking (36) Codeforces (36) Introduction to Algorithms (36) Must Known (36) Beauty of Programming (35) Sort (35) Array (33) Data Structure Design (33) Segment Tree (33) Sliding Window (33) prismoskills (33) HDU (31) Priority Queue (31) Google Code Jam (30) Permutation (30) Puzzles (30) Array O(N) (29) Company-Airbnb (29) Company-Zenefits (28) Microsoft 100 - July (28) Palindrome (28) to-do-must (28) Graph (27) Random (27) Company - LinkedIn (25) GeeksQuiz (25) Logic Thinking (25) Post-Order Traverse (25) Pre-Sort (25) Time Complexity (25) hihocoder (25) Queue (24) Company-Facebook (23) High Frequency (23) TopCoder (23) Algorithm Game (22) Binary Indexed Trees (22) Bisection Method (22) Hash (22) DFS + Review (21) Lintcode - Review (21) Two Pointers (21) Brain Teaser (20) CareerCup (20) Company - Twitter (20) LeetCode - DP (20) Merge Sort (20) O(N) (20) Follow Up (19) UVA (19) Ordered Stack (18) Probabilities (18) Company-Uber (17) Game Theory (17) Topological Sort (17) Codercareer (16) Heap (16) Shortest Path (16) String Search (16) Tree Traversal (16) itint5 (16) Difficult (15) Iterator (15) BST (14) KMP (14) LeetCode - DFS (14) Number (14) Number Theory (14) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Euclidean GCD (13) Long Increasing Sequence(LIS) (13) Majority (13) Reverse Thinking (13) mitbbs (13) Combination (12) Computational Geometry (12) LeetCode - Classic (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) Miscs (11) Princeton (11) Proof (11) Rolling Hash (11) Tree DP (11) X Sum (11) 挑战程序设计竞赛 (11) Bisection (10) Bucket Sort (10) Coin Change (10) Company - Microsoft (10) DFS+Cache (10) Facebook Hacker Cup (10) HackerRank Easy (10) O(1) Space (10) SPOJ (10) Theory (10) TreeMap (10) Tutorialhorizon (10) DP-Multiple Relation (9) DP-Space Optimization (9) Divide and Conquer (9) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Prefix Sum (9) Quick Sort (9) Simulation (9) Stack Overflow (9) Stock (9) System Design (9) Use XOR (9) Book Notes (8) Bottom-Up (8) Company-Amazon (8) DFS+BFS (8) Interval Tree (8) Left and Right Array (8) Linked List (8) Longest Common Subsequence(LCS) (8) Prime (8) Suffix Tree (8) Tech-Queries (8) Traversal Once (8) 穷竭搜索 (8) Algorithm Problem List (7) Expression (7) Facebook Interview (7) Fibonacci Numbers (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Level Order Traversal (7) Math-Divisible (7) Probability DP (7) Quick Select (7) Radix Sort (7) TreeSet (7) n00tc0d3r (7) 蓝桥杯 (7) Catalan Number (6) Classic Data Structure Impl (6) DFS+DP (6) DP - Tree (6) DP-Print Solution (6) Dijkstra (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Manacher (6) Minimum Spanning Tree (6) Morris Traversal (6) Multiple Data Structures (6) One Pass (6) Programming Pearls (6) Pruning (6) Rabin-Karp (6) Randomized Algorithms (6) Sampling (6) Schedule (6) Stream (6) Suffix Array (6) Threaded (6) Xpost (6) reddit (6) AI (5) Algorithm - Brain Teaser (5) Art Of Programming-July (5) Big Data (5) Brute Force (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) Cycle (5) DP-Include vs Exclude (5) Fast Slow Pointers (5) Find Rule (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LeetCode - TODO (5) Matrix Chain Multiplication (5) Maze (5) Microsoft Interview (5) Pre-Sum (5) Quadtrees (5) Quick Partition (5) Quora (5) SPFA(Shortest Path Faster Algorithm) (5) Subarray Sum (5) Sudoku (5) Sweep Line (5) Word Search (5) jiuzhang (5) 单调栈 (5) 树形DP (5) 1point3acres (4) Abbreviation (4) Anagram (4) Anagrams (4) Approximate Algorithm (4) Backtracking-Include vs Exclude (4) Brute Force - Enumeration (4) Chess Game (4) Consistent Hash (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) LeetCode - Recursive (4) MST (4) MinMax (4) N Queens (4) Nerd Paradise (4) Parallel Algorithm (4) Practical Algorithm (4) Probability (4) Programcreek (4) Spell Checker (4) Stock Maximize (4) Subset Sum (4) Subsets (4) Symbol Table (4) Triangle (4) Water Jug (4) algnotes (4) fgdsb (4) to-do-2 (4) 最大化最小值 (4) A Star (3) Algorithm - How To (3) Algorithm Design (3) B Tree (3) Big Data Algorithm (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) Finite Automata (3) Github (3) GoLang (3) Graph - Bipartite (3) Include vs Exclude (3) Joseph (3) Jump Game (3) K (3) Knapsack-多重背包 (3) LeetCode - Bit (3) Linked List Merge Sort (3) LogN (3) Master Theorem (3) Min Cost Flow (3) Minesweeper (3) Missing Numbers (3) NP Hard (3) O(N) Hard (3) Online Algorithm (3) Parser (3) Pascal's Triangle (3) Pattern Match (3) Project Euler (3) Rectangle (3) Scala (3) SegmentFault (3) Shuffle (3) Sieve of Eratosthenes (3) Skyline (3) Stack - Smart (3) State Machine (3) Subtree (3) Transform Tree (3) Trie + DFS (3) Two Pointers Window (3) Warshall Floyd (3) With Random Pointer (3) Word Ladder (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) Binary Search - Smart (2) Binomial Coefficient (2) Bit Counting (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) Company-Snapchat (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) Edit Distance (2) Factor (2) Forward && Backward Scan (2) GoHired (2) Graham Scan (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) Linked Interview (2) Linked List Sort (2) Longest SubArray (2) Lucene-Solr (2) Math-Remainder Queue (2) Matrix Power (2) Median (2) Minimum Vertex Cover (2) Negative All Values (2) Number Each Digit (2) Numerical Method (2) Object Design (2) Order Statistic Tree (2) Parent-Only Tree (2) Parentheses (2) Peak (2) Programming (2) Range Minimum Query (2) Regular Expression (2) Return Multiple Values (2) Reuse Forward Backward (2) Robot (2) Rosettacode (2) Scan from right (2) Search (2) SimHash (2) Simple Algorithm (2) Spatial Index (2) Strongly Connected Components (2) Summary (2) TV (2) Tile (2) Traversal From End (2) Tree Sum (2) Tree Traversal Return Multiple Values (2) Tree Without Tree Predefined (2) Word Break (2) Word Graph (2) Word Trie (2) Yahoo Interview (2) Young Tableau (2) 剑指Offer (2) 数位DP (2) 1-X (1) 51Nod (1) Akka (1) Algorithm - New (1) Algorithm Series (1) Algorithms Part I (1) Analysis of Algorithm (1) Array-Element Index Negative (1) Array-Rearrange (1) Augmented BST (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 Sarch Tree (1) Binary String (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) Clean Code (1) Cloest (1) Clone (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-Yelp (1) Compression Algorithm (1) Concise (1) Concurrency (1) Cont Improvement (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) Diagonal (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 - Facebook (1) Isomorphic (1) JDK8 (1) K Dimensional Tree (1) Knapsack - Fractional (1) Knapsack - ZeroOnePack (1) Knight (1) Knuth Shuffle (1) Kosaraju’s algorithm (1) Kruskal (1) Kth Element (1) Least Common Ancestor (1) LeetCode - Binary Tree (1) LeetCode - Coding (1) LeetCode - Construction (1) LeetCode - Detail (1) LeetCode - Related (1) LeetCode - Thinking (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) Machine Learning (1) Maintain State (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) Memory-Efficient (1) MinHash (1) MinMax Heap (1) Monotone Queue (1) Monto Carlo (1) Multi-End BFS (1) Multi-Reverse (1) Multiple DFS (1) Multiple Tasks (1) Next Element (1) Next Successor (1) Offline Algorithm (1) PAT (1) Parenthesis (1) Partition (1) Path Finding (1) Patience Sort (1) Persistent (1) Pigeon Hole Principle (1) Power Set (1) Pratical Algorithm (1) PreProcess (1) Probabilistic Data Structure (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) Resources (1) Reverse Inorder Traversal (1) Robin (1) Selection (1) Self Balancing BST (1) Similarity (1) Sort && Binary Search (1) Square (1) Streaming Algorithm (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) Test Cases (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 and Heap (1) Trie vs Hash (1) Trie vs HashMap (1) Triplet (1) Two Data Structures (1) Two Stacks (1) Two-End-BFS (1) USACO - Classical (1) USACO - Problems (1) UyHiP (1) Valid Tree (1) Vector (1) Virtual Matrix (1) Wiggle Sort (1) Wikipedia (1) ZOJ (1) ZigZag (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