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

Tips for learning a new programming language (when you already know one)

Reference from here:
tips-for-learning-new-programming by Hanneli Tavante

1. Install simplest environment
2. Procedural Programming basics — creating and printing variables, creating and calling basic functions.
3. Object Oriented Programming (OOP) basics — create a class, add attributes, methods and create an object.
4. Test Driven Development (TDD) basics — Write a test –> See it red –> Do the minimal to see it green -> Refactor with OOP.
5. OOP principles — relationships between classes and objects, Abstraction, Polymorphism, Inheritance, Encapsulation and design patterns.
6. Make analogies and compare between the language you already know and the language you are learning.
7. Pair programming — take a simple problem, implement it in pair programming with someone that has experience on the language you are trying to learn.

For functional programming language, OOP may not work, you can find out similar way to learn it.

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).

Chapter 1 – Arrays & Strings – Solution 1.3

Question:

1.3 Write a method to decide if two strings are permutation. i.e. “hello” is a permuataion of “oellh”.

If one string is a permutation of the other, they should has the same length and every character appear the same times in these two strings.

So the solution is to check the length and appear time of each character of these two strings.

We can use the same idea in question in 1.1 to solve this question. For example, use an array to store the appear time of all the characters in ASCII table.

Here is my solution, the time complexity was O(n) and space complexity is O(1).

bool
permutation(string a, string b)
{
  // if the length is different, can not be permutation
  if(a.size() != b.size()) return false;

  // use idea of Bucket-sort to count every ASCII character
  int bucket[256] = {};

  // count the apprear time of every character in a
  for(size_t i=0; i<a.size(); i++)
    bucket[a[i]]++;

  // the appear time of character in b shold be the same with a
  for(size_t i=0; i<b.size(); i++)
    if(bucket[b[i]]-- == 0) return false;

  return true;
}

Chapter 1 – Arrays & Strings – Solution 1.2

1.2 Write code to reverse a C-Style String (char* str). (C-String means that “abcd” is represented as five characters, including the null terminator.)

We can use two pointer, one is pointed to the first character, the other is pointed to the last character before the null pointer. Then we can swap the two character, and move the two pointer one step to each other and repeat.

Here is my solution, the time complexity  of this algorithm is O(n), and the space complexity is O(1).

void
reverse(char* str)
{
  size_t i = 0, j = 0;

  while(str[i]!=0) ++i; // go to the end of string "\0"
  --i; // move to the charcter before "\0"

  while(i>j) // swap the head and end characters one by one
  { // xor swap
    str[i] ^= str[j]; // a = a xor b
    str[j] ^= str[i]; // b = b xor (a xor b) = a
    str[i--] ^= str[j++]; // a = (a xor b) xor a = b
  }

  return;
}

Chapter 1 – Arrays & Strings – Solution 1.1

Cracking the code interviews – Solution

Chapter 1 Arrays & Strings

1.1 Implement an algorithm to determine if a string has all unique characters. What if you can not use additional data structure?

If the characters comes from the ASCII table, there can only be 256 types of them. We can use a boolean array of size 256 to mark each type of characters. This is the same idea of Bucket-sort algorithm.
About Bucket-Sort: http://en.wikipedia.org/wiki/Bucket_sort

When a new character is already marked as true (already appeared), then we will know that this string contains duplicate characters. The time complexity of isUnique() is O(n) and space complexity is O(1).

Here is my solution in c++:

bool
isUnique(string str)
{
  // if length bigger than 256, it must have duplicate character
  if(str.size() >= 256) return false;

  // use idea of Bucket-sort to find the duplicate character
  bool bucket[256] = {}; // remember every ASCII character

  for(size_t i=0; i<str.size(); ++i)
  {
    // mark the appeared character to true
    // if already set true, report the duplicated character
    if(bucket[str[i]])
      return false;

    bucket[str[i]] = true;
  }

  return true;
}

Another solution is to use a 256-bit-map to mark the characters in ASCII table.
The time / space complexity of isUniqueV2() is also O(n) / O(1).

bool
isUniqueV2(string str)
{
  // if length bigger than 256, it must have duplicate character
  if(str.size() >= 256) return false;

  // use idea of Bucket-sort to find the duplicate character
  uint64_t bucket[4] = {};

  for(size_t i=0; i<str.size(); ++i)
  {
    int index = str[i] / 64; // which bucket should be check
    int bit = str[i] % 64; // which bit in the bucket should be check

    // mark the appeared character to true
    // if already set true, report the duplicated character
    if( (bucket[index] & (1 << bit)) != 0)
      return false;

    bucket[index] |= (1 << bit);
  }

  return true;
}

File Compare Tool: Meld

Meld homepage: http://meldmerge.org/

Meld is a very useful tools for file checking, if you used to compare files in Ultraedit under windows, you should install a Meld for your linux.

What’s more, you can do the compare job in gedit when you install meld.

Here is how to do it:

http://my.opera.com/area42/blog/comparing-files-using-gedit