Itertors


https://xmruibi.gitbooks.io/interview-preparation-notes/content/DataStructure/Iterator/JumpIterator.html
Implements an iterator in each output it print the number and skip the next one.
public class JumpIterator implements Iterator<Integer> {

    Iterator<Integer> iterator;

    public JumpIterator(Iterator<Integer> iterator) {
        this.iterator = iterator;
    }

    @Override
    public boolean hasNext() {
        return iterator.hasNext();
    }

    @Override
    public Integer next() {
        int res = iterator.next();
        if (iterator.hasNext())
            iterator.next();
        return res;
    }
}



+
https://xmruibi.gitbooks.io/interview-preparation-notes/content/DataStructure/Iterator/EvenIterator.html
Implements an iterator only output the even number.
public class EvenIterator implements Iterator<Integer> {

    Iterator<Integer> iterator;

    public EvenIterator(Iterator<Integer> iterator) {
        this.iterator = iterator;
    }

    @Override
    public boolean hasNext() {
        return iterator.hasNext(); // should put while logic here
    }

    @Override
    public Integer next() {
        int res = 0;
        while (iterator.hasNext() && (res = iterator.next()) % 2 != 0)
            ;
        return res;
    }
}

https://xmruibi.gitbooks.io/interview-preparation-notes/content/DataStructure/Iterator/IteratorFor2DArray.html
Set up a iterator to iterate a 2-dimensional array.
Iterator for 2-D Array
  • Iterate the 2-D array by x and y.
  • Record current element during hasNext() function.
  • Check the row if it is null.
public class DeepIterator{
    int cur; // this is important
    int row = 0, col = 0;

    int[][] listOfLists;

    public DeepIterator(int[][] listOfLists){
        if(listOfLists == null)
            throw new IllegalArgumentException("Null Input");
        this.listOfLists = listOfLists;
    }

    public Integer next(){
        return cur;
    }

    public boolean hasNext(){
        // make sure the row is not null
        while(row < listOfLists.length && col >= listOfLists[row].length) {
                row ++; col = 0;
        }
        if(row < listOfLists.length) {
            cur = listOfLists[row][col++];
            return true;
        }else
            return false;
    }

    public static void main(String[] args) {
        int[][] listOfLists = {
          {},{},{1,2,3},{},{},{2,3,4}
        };
        DeepIterator it = new DeepIterator(listOfLists);
        while(it.hasNext()){
          System.out.println(it.next());
        }
    }
}
https://xmruibi.gitbooks.io/interview-preparation-notes/content/DataStructure/Iterator/IteratorOfIterators.html
Given a Iterator which contain several iterator inside. The task is to iterate all elements inside these iterators
  • It's a class implements iterator interface but also contains several iterators.
  • Image these iterator is a bucket, the unit is a iterator and the cursor of bucket index is a iteratorelement.
  • Set a current index to point at a iterator.
public class Iterators<T> implements Iterator<T>{
    Iterators<T> current;
    Iterators<Iterators<T>> cursor;
    public Iterators(Iterable<Iterator<T>> iterators){
        if(iterators == null)
            throw new IllegalArgumentException("Illegal Argument!");
        this.cursor = iterators;
    }

    @Override
    public T next(){
        return current.next();
    }

    @Override
    public boolean hasNext(){
        if(!current.hasNext())
            current = findNext();
        return current != null && current.hasNext();
    }

    private Iterator findNext(){
        while(cursor.hasNext()){
            current = cursor.next();
            if(current != null && current.hasNext())
                break;
        }
        return current;
    }

    @Override
    public void remove(){
        if(current!=null)
            current.remove();
    }
}
https://xmruibi.gitbooks.io/interview-preparation-notes/content/DataStructure/Iterator/PeekIterator.html
Given an Iterator class interface with methods: next() and hasNext(), design and implement a PeekingIterator that support the peek() operation -- it essentially peek() at the element that will be returned by the next call to next().



+
class PeekingIterator implements Iterator<Integer> {

    int cur;
    Iterator<Integer> it;
    public PeekingIterator(Iterator<Integer> iterator) {
        this.it = iterator;
        cur = it.hasNext() ? it.next() : null; //\\
    }

    // Returns the next element in the iteration without advancing the iterator.
    public Integer peek() {
        return cur;
    }

    // hasNext() and next() should behave the same as in the Iterator interface.
    // Override them if needed.
    @Override
    public Integer next() {
        int res = curl
        cur = it.next() ? it.next() : null;
        return res;
    }

    @Override
    public boolean hasNext() {
        return it.hasNext();
    }
}

[LintCode][System Design] Consistent Hashing - 简书


[LintCode][System Design] Consistent Hashing - 简书
一般的数据库进行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 台机器的时候,区间的分布情况和对应的机器编号分别是多少?

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]
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,1],
  [90,179,3],
  [180,269,2],
  [270,359,4]
]
模拟的方法,每次选取最大的range,然后插入新的range。

    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;
    }
Read full article from [LintCode][System Design] Consistent Hashing - 简书

[LintCode][System Design] Consistent Hashing II - 简书


[LintCode][System Design] Consistent Hashing II - 简书
在 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

当 n 为 2^64 时,在这个区间内随机基本不会出现重复。

当 n 为 2^64 时,在这个区间内随机基本不会出现重复。
但是为了方便测试您程序的正确性,n 在数据中可能会比较小,所以你必须保证你生成的 k 个随机数不会出现重复。

当 n 为 2^64 时,在这个区间内随机基本不会出现重复。
但是为了方便测试您程序的正确性,n 在数据中可能会比较小,所以你必须保证你生成的 k 个随机数不会出现重复。
LintCode并不会判断你addMachine的返回结果的正确性(因为是随机数),只会根据您返回的addMachine的结果判断你getMachineIdByHashCode结果的正确性。
Example
create(100, 3)
addMachine(1)
>> [3, 41, 90]  => 三个随机数
getMachineIdByHashCode(4)
>> 1
addMachine(2)
>> [11, 55, 83]
getMachineIdByHashCode(61)
>> 2
getMachineIdByHashCode(91)
>> 1
文/chk(简书作者)
原文链接:http://www.jianshu.com/p/4b39053a7a24
著作权归作者所有,转载请联系作者获得授权,并标注“简书作者”。

class Solution {
private:
static int shardNum;
static int microShardNum;
static vector<int> shard2mach;
public:
// @param n a positive integer
// @param k a positive integer
// @return a Solution object
static Solution create(int n, int k) {
    shardNum = n;
    microShardNum = k;
    shard2mach.resize(n);
    for(int i = 0; i < n; i++) {
        shard2mach[i] = -1;
    }
}

// @param machine_id an integer
// @return a list of shard ids
vector<int> addMachine(int machine_id) {
    srand(time(NULL));
    int count = 0;
    vector<int> ret;
    while(count < microShardNum) {
        int number = rand() % shardNum;
        if (shard2mach[number] == -1) {
            count++;
            shard2mach[number] = machine_id;
            ret.push_back(number);
        }
    }

    return ret;
}

// @param hashcode an integer
// @return a machine id
int getMachineIdByHashCode(int hashcode) {
    int i = hashcode;
    while(true) {
        if (i == shardNum) {
            i = 0;
        }

        if (shard2mach[i] != -1) {
            return shard2mach[i];
        }
        i++;
    }
}
};

int Solution::shardNum;

int Solution::microShardNum;

vector<int> Solution::shard2mach;
Read full article from [LintCode][System Design] Consistent Hashing II - 简书

LintCode 502 - Mini Cassandra


http://www.jianshu.com/p/94fe92ad945b
Cassandra is a NoSQL storage. The structure has two-level keys.
  1. Level 1: raw_key. The same as hash_key or shard_key.
  2. Level 2: column_key.
  3. Level 3: column_value
raw_key is used to hash and can not support range query. let's simplify this to a string.
raw_key is used to hash and can not support range query. let's simplify this to a string.
column_key is sorted and support range query. let's simplify this to integer.
raw_key is used to hash and can not support range query. let's simplify this to a string.
column_key is sorted and support range query. let's simplify this to integer.
column_value is a string. you can serialize any data into a string and store it in column value.
implement the following methods:
  1. insert(raw_key, column_key, column_value)
  2. query(raw_key, column_start, column_end) // return a list of entries
Example
insert("google", 1, "haha")
query("google", 0, 1)
>> [(1, "haha")]
map<string, map<int, string>>的方式保存数据,由于map是根据key的大小排好序的hash表,所以遍历map<int, string>时,如果key已经大于column_end则退出。
/**
 * Definition of Column:
 * class Column {
 * public:
 *     int key;
 *     String value;
 *     Column(int key, string value) {
 *         this->key = key;
 *         this->value = value;
 *    }
 * }
 */
class MiniCassandra {
private:
    map<string, map<int, string>> ret;
public:
    MiniCassandra() {
        // initialize your data structure here.
    }

    /**
     * @param raw_key a string
     * @param column_start an integer
     * @param column_end an integer
     * @return void
     */
    void insert(string raw_key, int column_key, string column_value) {
        // Write your code here
        ret[raw_key][column_key] = column_value;
    }

    /**
     * @param raw_key a string
     * @param column_start an integer
     * @param column_end an integer
     * @return a list of Columns
     */
    vector<Column> query(string raw_key, int column_start, int column_end) {
        // Write your code here
        vector<Column> q;
        for(map<int, string>::iterator iter = ret[raw_key].begin(); iter != ret[raw_key].end(); iter++) {
            if (iter->first > column_end) {
                break;
            }

            if (column_start <= iter->first) {
                q.push_back(Column(iter->first, iter->second));
            }
        }

        return q;
    }
};
http://blog.csdn.net/jmspan/article/details/51749526
方法:使用哈希影射和有序影射。
* public class Column { * public int key; * public String value; * public Column(int key, String value) { * this.key = key; * this.value = value; * } * } */ public class MiniCassandra { private Map<String, TreeMap<Integer, String>> map = new HashMap<>(); public MiniCassandra() { // initialize your data structure here. } /** * @param raw_key a string * @param column_start an integer * @param column_end an integer * @return void */ public void insert(String raw_key, int column_key, String column_value) { // Write your code here TreeMap<Integer, String> tm = map.get(raw_key); if (tm == null) { tm = new TreeMap<>(); map.put(raw_key, tm); } tm.put(column_key, column_value); } /** * @param raw_key a string * @param column_start an integer * @param column_end an integer * @return a list of Columns */ public List<Column> query(String raw_key, int column_start, int column_end) { // Write your code here List<Column> results = new ArrayList<>(); TreeMap<Integer, String> tm = map.get(raw_key); if (tm == null) return results; Map<Integer, String> queried = tm.subMap(column_start, true, column_end, true); for(int key : queried.keySet()) { results.add(new Column(key, queried.get(key))); } return results; } }


Algorithm Problem Solving Approaches


http://www.jiuzhang.com/qa/623/
能不能系统讲讲什么时候用BFS和DFS

我就稍微说几句,BFS 和 DFS 都是搜索算法,我就比较一下他们的优缺点。
1.BFS是用来搜索最短径路的解是比较合适的,比如求最少步数的解,最少交换次数的解,因为BFS搜索过程中遇到的解一定是离根最近的,所以遇到一个解,一定就是最优解,此时搜索算法可以终止。这个时候不适宜使用DFS,因为DFS搜索到的解不一定是离根最近的,只有全局搜索完毕,才能从所有解中找出离根的最近的解。(当然这个DFS的不足,可以使用迭代加深搜索ID-DFS去弥补)

2.空间优劣上,DFS是有优势的,DFS不需要保存搜索过程中的状态,而BFS在搜索过程中需要保存搜索过的状态,而且一般情况需要一个队列来记录。

3.DFS适合搜索全部的解,因为要搜索全部的解,那么BFS搜索过程中,遇到离根最近的解,并没有什么用,也必须遍历完整棵搜索树,DFS搜索也会搜索全部,但是相比DFS不用记录过多信息,所以搜素全部解的问题,DFS显然更加合适。

上面提到的迭代加深搜索(ID-dfs)我觉得充分吸收了BFS和DFS各自的长处
基本原则:能用BFS的时候就用BFS,不能用的时候再用DFS。

https://segmentfault.com/a/1190000006059081
波利亚用三本书:《How To Solve It》、《数学的发现》、《数学与猜想》)来试图阐明人类解决问题的一般性的思维方法,总结起来主要有以下几种:
  • 时刻不忘未知量。即时刻别忘记你到底想要求什么,问题是什么。(动态规划中问题状态的设定)
  • 试错。对题目这里捅捅那里捣捣,用上所有的已知量,或使用所有你想到的操作手法,尝试着看看能不能得到有用的结论,能不能离答案近一步(回溯算法中走不通就回退)。
  • 求解一个类似的题目。类似的题目也许有类似的结构,类似的性质,类似的解方案。通过考察或回忆一个类似的题目是如何解决的,也许就能够借用一些重要的点子(比较 Ugly Number 的三个题目:263. Ugly Number, 264. Ugly Number II, 313. Super Ugly Number)。
  • 用特例启发思考。通过考虑一个合适的特例,可以方便我们快速寻找出一般问题的解。
  • 反过来推导。对于许多题目而言,其要求的结论本身就隐藏了推论,不管这个推论是充分的还是必要的,都很可能对解题有帮助。
刷 LeetCode 的最大好处就是可以锻炼解决问题的思维能力,相信我,如何去思考本身也是一个需要不断学习和练习的技能。

Check if a string is a double string | Letuscode


Check if a string is a double string | Letuscode
Given a string, we need to check if a string is a double string possibly by deleting a character.
A double string is a repetition of two strings affixed together.
For example the following strings are double strings
"aa", "meme", "abbabb"
Where as the follwing are not double strings
"ab", "abc", "acbab"
However "acbab" can be be a double string if we remove "c" from it.

Case 1:
If the given string is of even length, we simply need to check if it is a double string by checking if the left half and right half are equal.
No need to consider the case of deleting a character because, if we delete a character, it’s length will be odd which will never be a double string.
Case 2:
If the string is of odd length, we have to delete a character before checking if it is a double string. How to find out which character to be deleted?
So it appears that we should try to remove each possible character and check if it is a double string. However since we want to check for a double string,
the left and right half should atleast be similar if not equal.
Consider an example “acbab”, we can divide the string into longer and shorter halves in two ways
("acb", "ab")
("ac", "bab")

Since the first pair of string differ by only character (In other words, their edit distance is just 1)
So we just need to check if the edit distance between the longer and shorter strings is at most 1.
bool is_double(string &input) {
    size_t len = input.size();
    if( len % 2 == 1 )
        return false;
    int i;
    int mid = len/2;
    for( i = 0; i < mid; i++ ) {
        if( input[i] != input[i+mid] )
            return false;
    }
    return true;
}

bool is_sub_seq(string &longer, string &shorter) {
    int i, j;
    bool mismatch = false;
    for( i = 0, j = 0; i < longer.size() && j < shorter.size(); ) {
        if( longer[i] != shorter[j] ) {
            if( mismatch ) {
                return false;//more than one mismatch; not a double string
            }
            else {
                mismatch = true; //one mismatch is fine
                i++; //skip this character from the longer half
            }
        }
        else
        {
            i++;
            j++;
        }
    }
    return true;
}

bool can_be_double(string &input) {
    size_t len = input.size();
    if( len < 2 )
        return false;
    if( len % 2 == 0 )
        return is_double(input);
    else
    {
        string longer = input.substr(0, len/2+1);
        string shorter = input.substr(len/2+1, len/2);
        if( is_sub_seq(longer, shorter) )
            return true;
        shorter = input.substr(0, len/2);
        longer = input.substr(len/2, len/2+1);
        return is_sub_seq(longer,shorter);
    }
}
Read full article from Check if a string is a double string | Letuscode

Searching for an element in array of adjacent numbers | Letuscode


Searching for an element in array of adjacent numbers | Letuscode
Given an array of numbers where the difference between any adjacent numbers is 1, how do we efficiently find a given number?
For example consider the array {1, 2, 1, 2, 3, 2, 3, 4, 5, 6}, and we want to search for the number 5.

Let us assume we are searching for a number x+3 in an array.
Let us start with a number x at index 0. Here are the some of the possible patterns of numbers that the array can have
x, x+1, x+2, x+3, ...
x, x+1, x, x+1, ...
x, x-1, x, x+1, ...
x, x-1, x-2, x-1, ...
x, x+1, x+2, x+1, ...
etc...
We can safely jump to index 3 and check if the number is present. Why? Because in any pattern there is no chance of having x+3 before the index 3.
If the number is present, that is fine. Otherwise repeat the same procedure until we find the element or reach the end of the array.
The time complexity of the above procedure is still O(n), because in the worst case, we make n/2 jumps. But this is an improvement over the linear search (n comparisons in the worst case).
Example, search for number 6 in the array {4, 5, 4, 5, 4, 5, 4, 5, 4, 5}, we have to make 5 jumps to conclude that 6 is not present.
bool search_adj(const vector<int> &arr, int s) {
bool ret = false;
size_t i;
for( i = 0; i < arr.size(); ) {
if( arr[i] == s ) {
ret = true;
break;
}
else {
i += abs(s-arr[i]);
}
}
return ret;
}

Read full article from Searching for an element in array of adjacent numbers | Letuscode

Find a Mother Vertex in a Graph - GeeksforGeeks


Find a Mother Vertex in a Graph - GeeksforGeeks
A mother vertex in a graph G = (V,E) is a vertex v such that all other vertices in G can be reached by a path from v.

There can be more than one mother vertices in a graph. We need to output anyone of them.
How to find mother vertex?
  • Case 1:- Undirected Connected Graph : In this case, all the vertices are mother vertices as we can reach to all the other nodes in the graph.
  • Case 2:- Undirected/Directed Disconnected Graph : In this case, there is no mother vertices as we cannot reach to all the other nodes in the graph.
  • Case 3:- Directed Connected Graph : In this case, we have to find a vertex -v in the graph such that we can reach to all the other nodes in the graph through a directed path.
A Naive approach : 
A trivial approach will be to perform a DFS/BFS on all the vertices and find whether we can reach all the vertices from that vertex. This approach takes O(V(E+V)) time, which is very inefficient for large graphs.
Can we do better?
We can find a mother vertex in O(V+E) time. The idea is based on Kosaraju’s Strongly Connected Component Algorithm. In a graph of strongly connected components, mother verices are always vertices of source component in component graph. The idea is based on below fact.
If there exist mother vertex (or vertices), then one of the mother vertices is the last finished vertex in DFS. (Or a mother vertex has the maximum finish time in DFS traversal).
A vertex is said to be finished in DFS if a recursive call for its DFS is over, i.e., all descendants of the vertex have been visited.
How does the above idea work?
Let the last finished vertex be v. Basically, we need to prove that there cannot be an edge from another vertex u to v if u is not another mother vertex (Or there cannot exist a non-mother vertex u such that u-→v is an edge). There can be two possibilities.
  1. Recursive DFS call is made for u before v. If an edge u-→v exists, then v must have finished before u because v is reachable through u and a vertex finishes after all its descendants.
  2. Recursive DFS call is made for v before u. In this case also, if an edge u-→v exists, then either v must finish before u (which contradicts our assumption that v is finished at the end) OR u should be reachable from v (which means u is another mother vertex).
Algorithm :
  1. Do DFS traversal of the given graph. While doing traversal keep track of last finished vertex ‘v’. This step takes O(V+E) time.
  2. If there exist mother vertex (or vetices), then v must be one (or one of them). Check if v is a mother vertex by doing DFS/BFS from v. This step also takes O(V+E) time.
// A recursive function to print DFS starting from v
void Graph::DFSUtil(int v, vector<bool> &visited)
{
    // Mark the current node as visited and print it
    visited[v] = true;
    // Recur for all the vertices adjacent to this vertex
    list<int>::iterator i;
    for (i = adj[v].begin(); i != adj[v].end(); ++i)
        if (!visited[*i])
            DFSUtil(*i, visited);
}
// Returns a mother vertex if exists. Otherwise returns -1
int Graph::findMother()
{
    // visited[] is used for DFS. Initially all are
    // initialized as not visited
    vector <bool> visited(V, false);
    // To store last finished vertex (or mother vertex)
    int v = 0;
    // Do a DFS traversal and find the last finished
    // vertex 
    for (int i = 0; i < V; i++)
    {
        if (visited[i] == false)
        {
            DFSUtil(i, visited);
            v = i;
        }
    }
    // If there exist mother vertex (or vetices) in given
    // graph, then v must be one (or one of them)
    // Now check if v is actually a mother vertex (or graph
    // has a mother vertex).  We basically check if every vertex
    // is reachable from v or not.
    // Rset all values in visited[] as false
    fill(visited.begin(), visited.end(), false);
    DFSUtil(v, visited); // Do DFS beginning from v
    for (int i=0; i<V; i++)
        if (visited[i] == false)
            return -1;
    return v;
}
Read full article from Find a Mother Vertex in a Graph - GeeksforGeeks

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