F.Y.I

My materials for code interview:

You can have a look on the latest interview questions from careercup.com:
http://www.careercup.com/

And practice coding questions on Leetcode’s online judgement:
http://leetcode.com/

Here are my answers and summary for leetcode’s question on github:
https://github.com/benyl/leetcode

Here are some books that worth reading:

* CareerCup Top 150 Questions
* Cracking the Coding Interview
* C++Primer
* Head First Design Patterns

================================================================
Steps to solve algorithm problem on board:
================================================================

0) Collect detail requirements about the question: data structure, limitation, input types, error handling etc

1) Describe your solution by a simple case step by step.

2) Write your code base on the simple case.

3) “Mind compile” your code, check with corner cases.

4) Give the time & space complexity of your solution, think of ways to optimize them.

================================================================
And some useful knowledge (Good to know but not required):
================================================================

Sample coding questions from Google:
http://basicalgos.blogspot.com/?view=flipcard

如何设计一个LRU Cache
http://blog.csdn.net/hexinuaa/article/details/6630384

从B树、B+树、B*树谈到R 树
http://blog.csdn.net/v_july_v/article/details/6530142

Morris method (no recursive, no stack, O(1) space)
http://www.cnblogs.com/AnnieKim/archive/2013/06/15/MorrisTraversal.html

EXACT STRING MATCHING ALGORITHMS
http://www-igm.univ-mlv.fr/~lecroq/string/index.html

Dynamic Programming: 背包問題九講

Click to access DP.pdf

OOP questions (in java):
http://www.tutorials4u.net/java-faqs/core-java/index.html

教你如何迅速秒杀掉：99%的海量数据处理面试题
http://blog.csdn.net/v_july_v/article/details/7382693

从Trie树（字典树）谈到后缀树
http://blog.csdn.net/v_july_v/article/details/6897097

FB面试准备，这个人写的很详细，我觉得对其他面试也适用
http://www.mitbbs.com/article_t/JobHunting/32741713.html

大型WEB系统架构基本设计思路
http://www.it610.com/article/2619667.htm

增加你在美国找工作获得内推机会的10条建议
http://www.1point3acres.com/how-to-improve-your-chance-of-getting-referrals/

Get that job at Facebook
https://www.facebook.com/notes/facebook-engineering/get-that-job-at-facebook/10150964382448920

Facebook: How to crush your coding interview

系统设计总结：
http://www.mitbbs.com/article_t/JobHunting/32777529.html
http://www.wtoutiao.com/p/ef9tYN.html

================================================================
And something beyond algorithm:
================================================================

面试心仪的公司以前，我建议多面多几家公司，积累面试经验，你最起码要有一下体会：
1）面试提问千奇百怪你都遇到过，但你遇到没见过的问题不慌张。
2）现场面试过几家公司，特别是大公司。
3）足够强的体力和精神力挺过一天的面试。
4）自我介绍和项目经历倒背如流。
5）已经总结出一套跟面试官交流的经验，有几个常问的给面试官的问题。
6）算法基础扎实，对算法题有自己总结的一套经验和思路，面试前不盲目看网上的新题。熟练使用各种数据结构和优化思路，现场面对没遇过的算法题能够通过已有的知识一步一步推导。
7）对于有工作经验的工程师，最好能有自己的一套应对系统设计问题的思路，大致了解网站／分布式系统／移动开发的架构，能把设计题往自己熟悉的领域扩展，拉到自己的主场来分析。
8）关于系统设计，前端开发要考虑API设计，刷新机制，后端开发则需要考虑数据存储，状态更新，通知系统，分布式系统。最好你能有自己的一套理论归纳。简单来说就是减少数据量传输，状态更新的提示，用内存换时间性能、分布式系统的分配问题、负载均衡、数据同步。九章算法的课挺有用，mit bbs也有不错的系统设计总结，有个blog大概叫做a dummy guide to scalebilty写得就非常好，HighScalability这个网站也不错。还有一些网上的资源可以找找看。

这些不是说你特意准备以上几点，而是面试得多了，上面的几点你自然而然的就有了，你就知道自己准备充足了。不然通过的几率会比较低……

================================================================
关于OJ：
================================================================
用OJ训练算法基础是很有效的方法，现在有不少值得使用的OJ系统。我的GitHub (https://github.com/benyl/leetcode) 有当时全部leetcode解答和分析（130题），还有一个excel表格评价各题难度和归类，建议起码把3星及以下题目全部做完，和每一个类别做一个总结。Leetcode的题目我建议第一遍把题目做出来，第二遍精简代码，参考他人的答案，用尽可能简单和少的代码解决问题，这样对你的代码风格有很大帮助，注意，简单的代码不一定是最短的。

================================================================
关于读书时找工作的时间表：
================================================================
通常来说暑假实习需要提早一个学期投简历，前一年的9～12月份就应该一边读书考试，一边参加宣讲会和career fair，找认识的学长学姐内推，以及准备面试。
等到12月底学期结束，11～2月期间大公司面试完毕，没有就坚持到3～4月看能不能捞到一个暑假实习，不然就继续找。如果1、2月才开始找暑假实习，你基本上已经迟了（大公司intern head count很可能已经满了）。
等到春季学期结束，开始暑假实习，同时开始准备毕业和投简历找全职工作。
毕业前找全职工作的时间安排跟找实习差不多，同时有没有好的暑假实习经验也有很大影响。11月～1月面试完大公司。同上，1、2月才开始找的人基本上慢了一截。
最后学期继续一边上课一边投简历找全职工作，同时申请学生临时工作身份OPT。
如果工作不满意，可以继续一边工作一边准备面试更好的公司。
To be continue……

Good luck!

– Poly-Thinking

Leetcode: Distinct Subsequences

Given two strings A and B, find out how many distinct subsequences in A that are exactly equal to B.

Let get close to what is a subsequence.

If S is a subsequence of B, then each element of S can be assigned with an index at B. A valid assignment is that indices of B’s elements aren’t overlapping and in an ascending order.

Then we can come up with a naive solution.

1. for_each(S.begin(), S.end(), assign(char ch, T, range) {…}

Notice that the range parameter represents the constraint that in a valid assignment, indices are in ascending order.

Now this isn’t what all we are looking for. The question requires the number of valid distinct subsequences we can find in T. We will traverse all possible states in order to produce the correct number.

strawmen solution 2: use backtracking to traverse all possible states.

Let’s get close to the details in this solution. Implementing the backtracking algorithm would be the best way to achieve that purpose.

class Solution {
public:
    int numDistinct(string S, string T) {
        return BT(S.c_str(), T.c_str());
    }

    int BT(const char* s, const char* t) {
        if (*t == '\0') return 1;
        if (*s == '\0') return 0;
        if (*s == *t) 
            return BT(s+1, t+1) + BT(s+1, t);
        return BT(s+1, t);
    }
};

This can’t be wrong because BT is THE WAY to traverse all possible states! But hold on, what is the running time of this BT? The question is equivalent to how many sequences we traverse. And the answer is O(C(n, m)), where n is the length of the original string and m is the length of the target subsequence. That is almost n sqrt, which doesn’t seem acceptable for strings processing(strings are large in real life). Does any state have some nice properties that cause the same results, or are there any duplicate states??

Strawman solution 3: 

each call to BT() represents a unique intermediate state. It’s not hard to tell that in the overall BT process, there are duplicate intermediate states. Recomputation on duplicate states are supposed to be cut out by just simply utilizing the previous result.

class Solution {
    vector<vector<int>> mem;

public:
    int numDistinct(string S, string T) {
        mem = vector<vector<int>>(S.length(), vector<int>(T.length(), -1));
        return BT(S, T, 0, 0);
    }

    int BT(string& S, string&T, int si, int ti) {
        // a valid assignment has found
        if (ti == T.length()) {
            return 1;
        }
        // reach the end, no valid assignment found.
        if (si == S.length()) {
            return 0;
        }
        // duplicate states?
        if (mem[si][ti] > -1)
            return mem[si][ti];

        // try to match S[si] with T[ti]
        int sum = 0;
        if (S[si] == T[ti]) {
            sum += BT(S, T, si+1, ti+1);
        }
        // try to match T[ti] with some later element in S.
        sum += BT(S, T, si+1, ti);
        mem[si][ti] = sum;
        return sum;
    }
};

Leetcode: Word Ladder II

Problem description:

http://leetcode.com/onlinejudge#question_126

Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end, such that:

Only one letter can be changed at a time
Each intermediate word must exist in the dictionary
For example,

Given:
start = “hit”
end = “cog”
dict = [“hot”,”dot”,”dog”,”lot”,”log”]
Return
[
[“hit”,”hot”,”dot”,”dog”,”cog”],
[“hit”,”hot”,”lot”,”log”,”cog”]
]
Note:
All words have the same length.
All words contain only lowercase alphabetic characters.

 

Design and Pseudo code:

The same as Word Ladder I, use BFS to search all shortest possible path from start to end.

The tricky point in this problem is that the naive solution will easily exceed the running time limit, optimization is needed for this problem, i.e. eliminate the time for string comparing and copying.

 

1) map the dictionary to index, remember the mapping between words and indexes.

2) for start index, use BFS to find all possible path to end index. At first push start index into queue.

2.1) for every words in queue, find the adjacent list of them by searching dictionary for 1 step transfer words

2.2) for every word in adjacent list, push into queue and remember their depth and their parent word index

2.3) if found end index, stop searching

3) use backtracking form end index to generate the full path reversely, and translate from index back to strings

Solution & Analysis:

uses 668 milli secs for large judge
for word length k, and searching in dictionary takes O(1), and the depth of trasation is d
time complexity is O((k*26)^d), space complexity is O((k*26)^d)

class Solution {
    // function to generate path using backtracking method
    void gen(int v1, int v2, vector<string> &vdict, vector<vector<int> >& prev, 
             vector<int>& path, vector<vector<string> >&ans){
             
        path.push_back(v2); // push the nodes into path for back tracking
        
        if(v2 == v1 and path.size() > 1){
            ans.push_back(vector<string>());
            // translate the path of index to string in reverse order
            for(auto rit = path.rbegin(); rit != path.rend(); rit++)
                ans.back().push_back(vdict[*rit]);
        }else{
            // gengrate all possible path in recursive way
            for(int i = 0; i < prev[v2].size(); i++)
                gen(v1, prev[v2][i], vdict, prev, path, ans);
        }
        
        path.pop_back(); // pop the nodes from path for back tracking
    }
public:
    vector<vector<string> > findLadders(string start, string end, unordered_set<string> &dict) {
        dict.insert(start);
        dict.insert(end);
        
        vector<string> vdict(dict.begin(), dict.end()); // vector dictionary: id -> word mapping in dict
        unordered_map<string, int> ids;  // index dictionary: word -> id mapping in vdict
        vector<vector<int> > prev(dict.size()); // store the previous words in BFS
        vector<int> distance(dict.size(), -1); // store the distance from start
        
        // build string - index mapping, transfer problem to graph search
        // use interger instead of string to eliminate cost of string matching
        for(int i = 0; i < vdict.size(); i++)
            ids[vdict[i]] = i;
        
        // find the index of start and end words
        int vstr=0, vend=0;
        while(vdict[vstr] != start) vstr++;
        while(vdict[vend] != end) vend++;
        
        // use queue for BFS to search path from start to end
        queue<int> que;
        que.push(vstr);
        distance[vstr]=0;
        
        while(not que.empty()){
            int v1 = que.front(); que.pop();
            if(v1 == vend) break;
            int d = distance[v1] + 1;
            
            // get adjancent list of the words, branching factor of BFS is 26 characters * string size
            vector<int> adj;
            // erase the appeared words from dictionary can save search time
            ids.erase(vdict[v1]);
            
            // find all the words that can be transfered in 1 step
            for(int j = 0; j < vdict[v1].size(); j++){
                char w = vdict[v1][j];
                for(char c = 'a'; c <= 'z'; c++){
                    vdict[v1][j] = c;
                    if(ids.count(vdict[v1]))
                        adj.push_back(ids[vdict[v1]]);
                    vdict[v1][j] = w;
                }
            }
            
            // use BFS to calculate path to end, add new words (distance=-1) into queue
            // if multiple words can reach the same words, save all the words
            for(int i = 0; i < adj.size(); i++){
                int v = adj[i];
                if(distance[v] == -1){
                    prev[v].push_back(v1);
                    distance[v] = d;
                    que.push(v);
                }else if(distance[v] == d){
                    prev[v].push_back(v1);
                }
            }
        }

        // generate the full sting path using the index
        vector<vector<string> > ans;
        vector<int> path;
        gen(vstr, vend, vdict, prev, path, ans);
        return ans;
    }
};

Leetcode: Word Ladder

Problem description:

http://leetcode.com/onlinejudge#question_127

Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:

Only one letter can be changed at a time
Each intermediate word must exist in the dictionary
For example,

Given:
start = “hit”
end = “cog”
dict = [“hot”,”dot”,”dog”,”lot”,”log”]
As one shortest transformation is “hit” -> “hot” -> “dot” -> “dog” -> “cog”,
return its length 5.

Note:
Return 0 if there is no such transformation sequence.
All words have the same length.
All words contain only lowercase alphabetic characters.

 

Design and Pseudo code:

Use BFS to search all possible words from start, and the tricky point here is that you should search thru all words in dictionary for candidate words, this may take o(n) time for searching in each recursion.

Instead, replace one character in a time, and search in dictionary by hashing, assume that searching in dictionary takes o(1) and the length of string is k, this may take o(26*k) time for searching in each recursion, when dictionary size is much bigger than string length (n >> k), this will save lots of time.

1) push start word into queue for BFS

2) for each word in queue:

2.1) search all new words in dictionary that can be transfered in 1 step

2.2) if found end words, stop and return distance, else push words into queue

Solution & Analysis:

uses 608 milli secs for large judge
for word length k, and searching in dictionary takes O(1), and the depth of trasation is d
time complexity is O((k*26)^d), space complexity is O((k*26)^d)

class Solution {
public:
    int ladderLength(string start, string end, unordered_set<string> &dict) {
        if(start == end) return 0;
        if(start.size() != end.size()) return 0;
        
        // use queue for BFS, store word string and their distance from start
        queue<pair<string, int> > que;
        que.push(make_pair(start, 1));
        dict.erase(start);
        
        while(!que.empty()) {
            string str = que.front().first;
            int len = que.front().second;
            que.pop();
            
            // branching factor of BFS is 26 characters * string size
            for(int i=0; i<str.size(); i++)
            for(char c='a'; c<='z'; c++) {
                char chi = str[i];
                str[i] = c;
                
                if(str == end) return len+1;
                
                // use count instead of find to make searching faster
                if(dict.count(str) != 0) {
                    que.push(make_pair(str, len+1));
                    // erase the appeared words from dictionary can save search time
                    dict.erase(str);
                    if(dict.empty()) break;
                }
                
                str[i] = chi;
            }
        }
        return 0;
    }
};

Leetcode: Palindrome Partitioning II

Problem description:

http://leetcode.com/onlinejudge#question_132

Given a string s, partition s such that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

For example, given s = “aab”,

Return 1 since the palindrome partitioning [“aa”,”b”] could be produced using 1 cut.

Design and Pseudo code:

This problem is similar to Palindrome Partitioning I, however, the large test set requires us to limit the time complexity to a low level.

The general idea for this problem is to use dyanmic programming.

Naive approach:

1) if s is Palindrome, return 0
2) else use a (n X n) matrix to store mincut(s[i:i+len]), in here s[i:i+len] means the substring of s that starts a s[i] and ends at s[i+len]
3) for i=0 to s.size-1: initialize mincut[i,1] = 0
4) for len = 2 to s.size:

4.1) for i=0 to s.size-len:

4.2) if s.sub(i, len) is Palindrome: mincut[i,len] = 0

4.3) else mincut[i,len] = min(mincut[i,j-i] + mincut[j,len-j]) + 1

5) return dp[0, s.size]

Improved approach:

1) use an array to store minCut of s[:i] and palidrome s[:i]

2) for i = 0 to s.size()

2.1) for j = 0 to i

2.2) if s[j] == s[i] and s[j+1 : i-1] is palidrome, then s[j:i] is palidrome:

2.3) update mincut(s[:i]) = minimum of mincut(s[:j]) + 1

2.4) else or else mincut(s[:i]) = mincut(s[:i-1]) + 1

3) return mincut(s)

Solution & Analysis:

Version 1, Time Limit Exceeded, time complexity is o(n^3), space complexity is o(n^2).

class Solution {
public:
    bool isPalindrome(string s) {
        if(s.size() == 0) return true;
        if(s.size() == 1) return true;
        
        for(int i=0; i<s.size()/2; ++i)
            if(s[i] != s[s.size()-1-i])
                return false;
        return true;
    }

    int minCut(string s) {
        // use dynamic programming
        // if s is Palindrome, push to answer
        // use a (nXn) matrix to store mincut[i,len]
            // for i=0 to s.size-1: mincut[i,1] = 0
            // for len = 2 to s.size:
                // for i=0 to s.size-len: 
                    // if s.sub(i, len) is Palindrome: mincut[i,len] = 0
                    // else mincut[i,len] = min(mincut[i,j-i] + mincut[j,len-j]) + 1
            // return dp[0, s.size]
                
        if(isPalindrome(s))
            return 0;
            
        vector<vector<int> > dp; // use to store minCut[i, len]
        
        // initial minCut (minCut[i, len] means the result of minCut(s.sub(i, len)))
        for(int i=0; i<s.size(); ++i)
            dp.push_back(vector<int>(s.size()-i+1, 0));
        
        for(int len=2; len<=s.size(); ++len) {
            for(int i=0; i<=s.size()-len; ++i) {
                if((s[i] == s[i+len-1]) && (dp[i+1][len-2]==0)) {
                    dp[i][len] = 0;
                } else {
                    dp[i][len] = len-1;
                    for(int l=1; l<len; ++l) {
                        int cut = dp[i][l] + dp[i+l][len-l] + 1;
                        dp[i][len] = (dp[i][len] < cut) ? dp[i][len] : cut;
                        if(dp[i][len] < 2) break;
                    }
                }
            } // end of: for(int i=0; i<=s.size-len; ++i)
        } // end of: for(int len=2; len<s.size; ++len)
        
        return dp[0][s.size()];
    }
};

Version 2, uses 120 milli secs for large judge, time complexity is o(n^2), space complexity is o(n^2).

class Solution {
public:
    int minCut(string s) {
        int len = s.size();
        int dp[len]; // store minCut of s[i:]
        bool palidrome[len][len]; // store if s[i:j] is palidrome
        
        // init dp of mincut with maximum cut for s[i:] is (len-i-1)
        for(int i=0; i<=len; ++i)
            dp[i] = len-i-1;
        for(int i=0; i<len; ++i)
        for(int j=0; j<len; ++j)
            palidrome[i][j] = false;
        
        // start from end to head of string
        for(int i=len-2; i>=0; --i)
        for(int j=i; j<len; ++j)
            // only consider when s[i:j] is palidrome (s[i] == s[j] and s[i+1:j-1] is palidrome)
            // or else mincut(s[i:]) = mincut(s[i+1:]) + 1
            if((s[i] == s[j]) && (j-i<2 || palidrome[i+1][j-1])) {
                palidrome[i][j] = true;
                // mincut s[i:] is minimum of mincut(s[j:]) + 1 (that is, first cut at j)
                dp[i] = min(dp[i], dp[j+1]+1);
            }
        
        return dp[0];
    }
};

Version 3, uses 28 milli secs for large judge, time complexity is o(n^2), space complexity is o(n).

class Solution {
public:
    int minCut(string s) {
        if (s.size() < 2)
            return 0;
        int len = s.size();
        // use two arrays for dyanmic programming
        int minSegs[len+1]; // store the min palidrome segments of s[:i]
        int palLen[len+2]; // store all lengths of palidrome that ends at s[i]
        
        // initialize the minSegs and possible lengths of palidrome for s[:1]
        minSegs[0] = 0; minSegs[1] = 1;
        palLen[0] = 0; palLen[1] = 1; palLen[2] = -1;
        
        for (int i=1; i<s.size(); i++) {
            // init mincut(s[:i+1]) = mincut(s[:i]) + 1
            minSegs[i+1] = minSegs[i] + 1;
            int n = 0; // numbers of palidrome that ends at s[i]
            // for all palidrome that ends at s[i-1], check if s[left:i] is palidrome
            for (int j=0; palLen[j] != -1; j++) {
                int left = i-1-palLen[j];
                // if s[left:i] is palidrome, add length of s[left:i] into array and update minSegs[i+1]
                if (left>=0 && s[left]==s[i]) {
                    palLen[n++] = palLen[j] + 2;
                    // first cut at left and s[left:i] is palidrome -> minSegs[i+1] = minSegs[left] + 1
                    minSegs[i+1] = min(minSegs[i+1], minSegs[left] + 1);
                    if(minSegs[i+1] == 1) break;
                }
            }
            // add lengths 0 and 1 to array of palidrome length for s[:i]
            palLen[n++] = 0; palLen[n++] = 1; palLen[n] = -1;
        }
        
        // minCut(s) = minSeg(s) - 1
        return minSegs[s.size()] - 1;
    }
};

Leetcode: Palindrome Partitioning

Problem description:

http://leetcode.com/onlinejudge#question_131

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

For example, given s = “aab”,
Return

[
[“aa”,”b”],
[“a”,”a”,”b”]
]

Design and Pseudo code:

To get all possible palindrome partitioning of s, we need to try all possible partitions recursively.

Partition(s):

1) find all possible palindrome in s that start with the first letter

2.1) for each palindrome p, get the substring s1 of s that have the characters after p, so s = p + s1

2.2) find all possible palindrome partition of s1 by calling partition(s1), add p to the begin of return and save to answers

3) return answers

Solution:

class Solution {
public:
    // function to find if s is palindrome
    bool isPalindrome(string s) {
        if(s.size() == 0) return true;
        if(s.size() == 1) return true;

        for(int i=0; i<s.size()/2; ++i)
            if(s[i] != s[s.size()-1-i])
                return false;
        return true;
    }

    vector<vector > partition(string s) {
        vector<vector > answer;

        if(s.size() == 0)
            return answer;

        // if s is Palindrome, push to answer
        if(isPalindrome(s))
            answer.push_back(vector(1,s));

        if(s.size() == 1)
            return answer;

        for(int i=1; i<s.size(); ++i) {
            string s1 = s.substr(0, i);
            string s2 = s.substr(i, s.size()-i);

            if(isPalindrome(s1)) {
                // get sub_answers of partition(s[i:])
                vector<vector > sub_answer = partition(s2);

                // add s1 to the begin of sub_answers
                for(int j=0; j<sub_answer.size(); ++j) {
                    sub_answer[j].insert(sub_answer[j].begin(), s1);
                    answer.push_back(sub_answer[j]);
                }
            }
        }

        return answer;
    }
};

Analysis:

Passed leetcode judge large, 464 milli secs.

The time complexity of function isPalindrome takes o(n), and the partition will call isPalindrome n times, which takes o(n^2).

And the creation of s1, s2 takes o(n), and was done n times, totally o(n^2), and the all possible combinations of result is 2^n.

And the partition will recursively call itself n times, so the total time complexity is o(n*2^n).

The space complexity of partitions is the same as all possible combination of partition of string, which is o(2^n).

Leetcoding in C++11: Min/Max

How to get the minimum value of a set of number?

C++98:

int nums[] = { 1, a, tabl[0], 0 };
cout << *max_element(num, sizeof(nums)/sizeof(int));

C++11:

//1.
int nums[] = { 1, a, table[0], 0 };
cout << *max_element(begin(nums), end(num)); // T* end(T (&a)[N])
//2.
cout << max({1, a, table[0], 0}); // T max(initlizer_list<T> il)

References:

std::begin/end

http://www.cplusplus.com/reference/iterator/end/?kw=end

std::max

http://www.cplusplus.com/reference/algorithm/max/?kw=max

Leetcoding in C++11, An Act of God

Remember the time I become obsessed in C++. It was 2007. I knew nothing and was hacking a OJ problem. I ended up writing probably 100 lines of C code. I felt painful and messy so I searched for better solutions. A snippet of C++ solution came out with no more than 10 lines of code including Main(). And I still remembered how shock it was when I saw “table[“abc”] = 1″, where an array taking a string as index. I was like what the heck!

Since then, I’ve started coding in C++ for everything. Taking full advantages of STL has become my hobbe. I got to know map, pair, lower_bound, swap and sort, all these good stuff. Back then, C was the main trend for hacking OJ and Java wasn’t even an option yet.

In 2013, GCC 4.8 has come out recently, as the first compiler that fully supports C++11. At the mean while, friends and I have started hacking OJ again. Nevertheless, LeetCode OJ enables C++11! I think this is an act of god so that I could continues my journay in C++11.

Leetcode:Divide Two Integers

The main idea of the solution is very simple. Using shift to replace the operation of multiply and division.

Assume that a>0 and b>0,c=a/b

(1) When a<b , c must be zero

(2) When a>b, we can consider the solution at this way. c= 1001……11111(In binary system) . Obviously, some digit may be zero. At this way, c equals 1*2^n1+1*2^n2+………1*2^nk. Thus, a must equals to b*2^n1+b*2^n2……..b*2^nk.So we can find out the b*2^n1 (which is smaller than a and close enough to a).  Subtract the b*2^n1, try to find the next close number to the subtracted number. Do it iteratively,and find the result. (Here, 2^n1 can be calculated by using shift operation.)

Notice:

(1) a/b can be indivisible. Thus, if we find the try number is smaller than the divisor, we should end the loop, because at this time we are calculation the digit behind the point.

For example, 5/3, the next number we try can 3*2^-1=1 <3, at this time, we should jump out of the loop and return the result.

(2) need to consider the flag of dividend and divisor.

(3) need to consider the shift may result overflow. Thus, we need to use longer type to contain the try number(type: long long instead of just int)

The code:

/*
想法很简单，a/b=c可以变成 a=b*c，c必然可以拆成2^n1+2^n2.......2^nk次方
（不一定每一项都有，不过必然是2的多少次方相加）。之后试验出最接近a的b*2^ni，然后a减去这个结果。
然后迭代把减去之后的结果当成新的a，继续找最接近的.........
*/
class Solution {
public:
 int divide(int dividend, int divisor) {
 // Start typing your C/C++ solution below
 // DO NOT write int main() function
 unsigned int num1;//必须考虑除数和被除数的正负问题，所以这个为全部为正的被除数和除数
 unsigned int num2;
 int num1Flag=0;//标定被除数和除数的正负
 int num2Flag=0;
 if (dividend<0)
 {
 num1=-dividend;
 num1Flag=1;
 }
 else
 {
 num1=dividend;
 num1Flag=0;
 }
 if (divisor<0)
 {
 num2=-divisor;
 num2Flag=1;
 }
 else
 {
 num2=divisor;
 num2Flag=0;
 }

//如果num1<num2,证明被除数比除数小（正负已经去掉了）必然为0 不用往下做了
 if (num1<num2) return 0;
 //之后被除数大于等于除数
 long long tryNumber=num2;//用来尝试的数
 unsigned int result=0;//记录结果的
 unsigned int counter=0;//2的多少次方，后面的次方
 int requireNumber=num1;//想要到达的number

 //尝试找临界的数
 while(tryNumber<=num1)
 {
 tryNumber=tryNumber<<1;
 counter++;
 }
 tryNumber=tryNumber>>1;
 counter--;
 //找到临界点
 result=1<<counter;//相当于2的counter次方
 requireNumber=requireNumber-tryNumber;//减去已经满足num2*2^counter次方的结果

while(requireNumber>0)
 {
 tryNumber=tryNumber>>1;
 counter--;
 if (tryNumber<num2) break;//如果tryNumber小于num2就是说这时候尝试的是结果小数点之后的了（counter），因为这里返回的是整数，所以就不需要考虑了
 if (requireNumber>=tryNumber) //迭代，减去对应尝试结果，进行下一步迭代
 {
 requireNumber=requireNumber-tryNumber;
 result=result+(1<<counter);
 }
 }
 //最后返回考虑正负的结果
 int finalResult;
 if ((num1Flag==0 && num2Flag==0) || (num1Flag==1 && num2Flag==1))
 {
 finalResult=result;
 }
 else
 {
 finalResult=-result;
 }
 return finalResult;
 }
};

Small Test:

Large Test:

Leetcode:Sort Colors

It is a very old leetcode problem. Because I want to find out which problem in the leetcode is  unfinished yesterday, I reuploaded all my code to leetcode. Then I    found out that I have not finished this problem.

This problem requires only one pass.

The main idea of the solution is to guess that there is a sequence of “111111”in the array. Assume the head location of the sequence is firstOne, the rear of the sequence is lastOne. We need put all the “0” before the firstOne, and put all the “2” after the lastOne.

We first guess all the element s in the array is 1. The we check the location one by one.

when the checked element is zero,

(1) check location larger than firstOne.

This means that there must be an 1111 sequence before. We can swap the element the firstOne points to with the element now check(which is 0). It means we insert the 0 element before the firstOne. And the firstOne plus one.(Because the header of sequence 111111 is move behind for one location.)

(2) check location equal to firstOne.

This means that the header of “111111” we guess is not correct. The header of “111111”is zero, so we need to guess the location behind this header and check this location. (nowCheck++ and firstOne++)

(3) check location before firstOne.

Impossible, because we only move firstOne backwards after we check the location. Thus, firstOne must smaller than the  check location or equal as the check location.

when the checked element is 1,

just need to check the location behind. (The main idea of the solution is put all “0” before the guess sequence “1111”, put “2” after the guessing sequence.)

when the checked element is 2,

we need to swap this element with the last One of guessing sequence “1111”. lastOne location minus one. (Because we put an “2” behind the guessing sequence”111111″ )

/*
只扫描一遍的思路如下：
我们需要维持3段有序的在数组里面
我们可以假设数组里面有一段111111，不过不知道数量是多少，可能没有，我们用两个变量去标识这段东西的头和尾部
然后把扫到的所有0都摆在这段的前面，也就是头的前面，扫到的2都摆在这段的后面。
当扫的指针遇上这段的尾部的尾部就扫描完了，因为尾部后面必然都是2
*/
class Solution {
public:
 void sortColors(int A[], int n) {
 // Start typing your C/C++ solution below
 // DO NOT write int main() function
 int nowCheck=0;
 int firstOne=0;//初期假设整条序列都是1，那么第一个就是位置0，最后一个就是位置n-1
 int lastOne=n-1;
 while(nowCheck<=lastOne)
 {
 if (A[nowCheck]==0)
 {
 //当前扫描位置在1111段的头之后，前面必定有1的值
 if (nowCheck>firstOne)
 {
 //当前扫描位置大于1字符段的开头，证明前面必然有1，交换他们的值，当前扫描位置的值就是1，在下一次判断时候指针就会往后挪
 swap(A[nowCheck],A[firstOne]);
 firstOne++;//因为当前扫到的是0，所以和1字符段开头的第一个元素交换，1字符段的头元素就要往后挪一位了，相当于前面插了一个0
 }
 else if (nowCheck==firstOne)
 {
 /*因为firstOne实际上是猜测的1段的开头，当检测的位置和猜测的1段头相同的时候
 并且检测到0的时候，之前的必然都是0，所以这个位置不用动。检测位置挪去下一位，同样猜测的1段开头要往后挪
 */
 nowCheck++;
 firstOne++;
 }
 //不可能nowCheck在firstOne之前，因为猜测的1段能够往后移动必须要之前的位置都被检测过，一开始检测位置和猜测1段开始的位置两个的位置重合
 //firstone只有在nowCheck之前才会往后移动，而两者位置相同的时候都是同时往后移动
 }
 else if (A[nowCheck]==1)
 {
 //检测到1的时候，不需要移动，因为我们只需要把0摆在1的前面，2摆在1的后面就可以了
 nowCheck++;
 }
 else if (A[nowCheck]==2)
 {
 //因为nowcheck必然小于lastOne，否则就可以结束了,当遇到2的时候直接交换猜测1段的最后一个位置
 swap(A[nowCheck],A[lastOne]);
 lastOne--;
 }
 }

}
};

Test Result:

small data:

large data: