面经/LintCode/LeetCode题目想法和代码分享

Max Product Of Two Words With No Common Letter
地里面经
google整理地里所有的面试题目里google_tree.pdf第三页

这道题确实很难。我一开始能想到的唯一优化就是把每个单词转化为一个int，每个字母分别对应一个bit位。
为了简化问题，我们假设每个单词由a~z组成。因为我们只在乎每个字母是否出现在一个单词里，并不在乎出现了多少次，所以ab或者abb转化为int都是3。
这样做的好处在于比较两个单词时，我们直接进行bit比较就好了，如果or的结果为0，证明这两个单词没有相同的字母。
虽然进行了一定的优化，但是主思路还是brutal force，没有太好的想法。
然后我上网搜了搜，careercup上也有这道题，但是也没看到很靠谱的建议。
然后在Quora上也看到了这道题，置顶的思路很不错：
https://www.quora.com/Given-a-dictionary-of-words-how-can-we-efficiently-find-a-pair-words-s-t-they-dont-have-characters-in-common-and-sum-of-their-length-is-maximum
根据这个思路，我们可以建立一个vector，其index为字母组合的bit representation。比如ab在这个vector的index就是3，c的index是4，ca的index是5。
然后每个index记录这 包含这些字母 或者 最多包含这些字母 的word的最长的长度。
比如我们有a，bbbbb，abb三个单词。[1]的长度为1，对应a。[2]的长度为5，对应bbbbb，[3]的长度也应该是5，还是对应bbbbb。
当我们建立了这个vector之后，我们可以重新遍历一遍dict，每个单词我们可以直接通过invert它的bit representation来找到跟它没有共同字母的最长单词长度。

1. 
   
2. class Solution {
   
3. public:
   
4. 
   
5.   unsigned int maxProduct(const vector<string>& dict) {
   
6.     unsigned int res = 0;
   
7.     if (dict.empty()) {
   
8.       return res;
   
9.     }
   
10.     if (dict.size() == 1) {
    
11.       return (int) dict[0].size();
    
12.     }
    
13.     auto bit_sets = wordsToBitSets(dict);
    
14.     const unsigned int used_mask = 0x3FFFFFF; //mask for 26 alphabet
    
15.     for (const auto& word : dict) {
    
16.       auto index = wordToIndex(word);
    
17.       unsigned index_c = (~index) & used_mask;
    
18.       res = max(res, bit_sets[index] * bit_sets[index_c]);
    
19.     }
    
20.     return res;
    
21.   }
    
22. 
    
23. private:
    
24. 
    
25.   unsigned int wordToIndex(const string& word) {
    
26.     unsigned int index = 0;
    
27.     for (const auto& c : word) {
    
28.       index |= 1 << (c - 'a');
    
29.     }
    
30.     return index;
    
31.   }
    
32. 
    
33.   vector<unsigned int> wordsToBitSets(const vector<string>& dict) {
    
34.     const unsigned int s = static_cast<unsigned int>(pow(2, 26));
    
35.     vector<unsigned int> bit_sets(s, 0);
    
36. 
    
37.     //insert all words into the bit sets
    
38.     for (const auto& word : dict) {
    
39.       unsigned int index = wordToIndex(word);
    
40.       bit_sets[index] = max(bit_sets[index], word.size());
    
41.     }
    
42. 
    
43.     //use DP to process the bit sets, such that each cell will contain
    
44.     //the length of the longest word that consists of exactly those letters
    
45.     //or the length of the longest word that consists of at most those letters
    
46.     const unsigned int bit_mask = 0xFFFFFFFF;
    
47.     for (unsigned int i = 1; i < s; ++i) {
    
48.       for (unsigned int j = 0; j < 26; ++j) {
    
49.         unsigned int pre = i & (bit_mask & ~(1 << j));
    
50.         if (pre == 0) {
    
51.           break;
    
52.         }
    
53.         bit_sets[i] = max(bit_sets[i], bit_sets[pre]);
    
54.       }
    
55.     }
    
56. 
    
57.   return bit_sets;
    
58.   }
    
59. };
    

复制代码

但是这个思路有个问题，就是我们在处理bit_sets时的run time peformance为O(a2^a)（a为alphabet个数），如果input dict的size不大，这个算法的效率还不如直接brutal force。

Monotonicity

有不少题会用到单调性，先来看一下LeetCode No.239 Sliding Window Maximum 这道题。
这道题讨论区里，有一个解法（Clean C++ O(n) solution using a deque）用到了monotonic queue这个数据结构。
代码和详解可以看链接，这里我们用[1,3,-1,-3,5,3,6,7], k = 3做例，观察一下这个结构是怎么运作的。

i = 0, q{0}
i = 1, nums[0] < nums[1], pop 0, q{1}
i = 2, nums[1] > nums[2], q{1, 2}, res{3}
i = 3, nums[2] > nums[3], q{1, 2, 3}, res{3, 3}
i = 4, pop 1, nums[3] < nums[4], pop 3, nums[2] < nums[4], pop 2, q{4}, res{3, 3, 5}
i = 5, nums[4] > nums[5], q{4, 5}, res{3, 3, 5, 5}
i = 6, nums[5] < nums[6], pop 5, nums[4] < nums[6], pop 4, q{6}, res{3, 3, 5, 5, 6}
i = 7, nums[6] < nums[7], pop 6, q{7}, res{3, 3, 5, 5, 6, 7}

可以看到monotonic queue把k区间里的最大值放到了dequeue首，当添加元素时，不停的从dequeue尾pop比新元素小的，保证了整个dequeue是单调递减的。
monotonic queue这个结构比较少见，有些题我们都会使用monotonic stack。
像在九章问答版里的这道题，G家面经题，返回数组的每个元素是原数组中右边的第一个大于该位置元素的index。（里面的代码是我写的:)）
我们从左向右扫描input的同时维持一个单调递减的stack，当扫到新元素时，如果小于等于stack顶index所指向的元素，则说明比stack中所有的元素都小，此时把此元素的index插入到stack中。如果大于stack顶index所指向的元素，则保存此元素的index为stack顶index所指向元素的index Of First Larger Element，并pop stack。循环这一系列操作直到stack为单调递减。

LeetCode No.42 Trapping Rain Water的一种做法也是用到了monotonic stack。

补充内容 (2016-7-19 14:08):
LeetCode No.84 Largest Rectangle in Histogram

Merge Tree XNOR
地里面经
详见Google 电面

昨天写了关于motonic queue的分析，使用了外部链接，到现在都还没通过审核。
明天早上有电面，这两天也挺紧张的，做些稍微简单些的题热热身。
这道题不难，不分析了，主要是看怎么写最简洁。因为都是complete tree，省去了很多edge case checks。

1. 
   
2. struct node {
   
3.   bool is_one;
   
4.   node* left;
   
5.   node* right;
   
6.   node(bool b) : is_one(b), left(nullptr), right(nullptr) {}
   
7. };
   
8. 
   
9. class Solution {
   
10. public:
    
11.   node* MergeTreeXnor(node* root1, node* root2) {
    
12.     if (root1 == nullptr) {
    
13.       return root2;
    
14.     }
    
15.     else if (root2 == nullptr) {
    
16.       return root1;
    
17.     }
    
18.                
    
19.     //we should ask interviewer whether the merged tree is still needed.
    
20.     //if not, we should implement a function to delete the merged tree.
    
21.     if (MergeTreeXnorHelper(root1, root2)) {
    
22.       return root1;
    
23.     }
    
24. 
    
25.     return root2;
    
26.   }
    
27. private:
    
28.   //true use root1 as new root, false use root2 as new root
    
29.   bool MergeTreeXnorHelper(node* root1, node* root2) {
    
30.     if (root1->left == nullptr) {
    
31.       MergeTreeXnorHelper(root2, root1->is_one);
    
32.       return false;
    
33.     }
    
34. 
    
35.     if (root2->left == nullptr) {
    
36.       MergeTreeXnorHelper(root1, root2->is_one);
    
37.       return true;
    
38.     }
    
39. 
    
40.     MergeTreeXnorHelper(root1->left, root2->left);
    
41.     return MergeTreeXnorHelper(root1->right, root2->right);
    
42.   }
    
43. 
    
44.   void MergeTreeXnorHelper(node* root, bool is_one) {
    
45.       if (root->left == nullptr) {
    
46.         root->is_one = root->is_one == is_one;
    
47.         return;
    
48.       }
    
49.     MergeTreeXnorHelper(root->left, is_one);
    
50.     MergeTreeXnorHelper(root->right, is_one);
    
51.   }
    
52. };
    

复制代码

Match Mix Cases Pattern
地里面经
详见狗狗YT面经第二题

这道题一个显而易见的优化就是把字典转化为Trie。
代码如下：

1. 
   
2. #include <vector>
   
3. #include <string>
   
4. #include <unordered_map>
   
5. #include <algorithm>
   
6. 
   
7. using namespace std;
   
8. 
   
9. class Solution {
   
10. public:
    
11.   Solution(const vector<string>& dict) {
    
12.     buildTrie(dict);
    
13.   }       
    
14. 
    
15.   vector<string> findMatches(const string& pattern) {
    
16.     vector<string> res;
    
17.     string cur;
    
18.     if (pattern.empty()) {
    
19.       return res;
    
20.     }
    
21.     findMatchesHelper(root_, pattern, 0, cur, res);
    
22.     return res;
    
23.   }
    
24. 
    
25. private:
    
26.   struct TrieNode {
    
27.     bool is_word = false;
    
28.     unordered_map<char, shared_ptr<TrieNode>> children;
    
29.   };
    
30. 
    
31.   void buildTrie(const vector<string> &dict) {
    
32.     root_ = make_shared<TrieNode>();
    
33.     for_each(dict.begin(), dict.end(), [&](const string& s){insertTrie(s); });
    
34.   }
    
35. 
    
36.   void insertTrie(const string& word) {
    
37.     shared_ptr<TrieNode> cur = root_;
    
38.     for (const char & c : word) {
    
39.       if (cur->children.find(c) == cur->children.end()) {
    
40.         cur->children[c] = make_shared<TrieNode>();
    
41.       }
    
42.       cur = cur->children[c];
    
43.     }
    
44.     cur->is_word = true;
    
45.   }
    
46. 
    
47.   void findMatchesHelper(shared_ptr<TrieNode> root, const string& pattern, int idx, string& cur, vector<string>& res) {
    
48.     const int s = pattern.size();
    
49.     if (idx >= s && root->is_word) {
    
50.       res.push_back(cur);
    
51.     }
    
52. 
    
53.     for (auto it = root->children.begin(); it != root->children.end(); ++it) {
    
54.       if (idx < s && it->first == pattern[idx]) {
    
55.         cur.push_back(it->first);
    
56.         findMatchesHelper(it->second, pattern, idx + 1, cur, res);
    
57.         cur.pop_back();
    
58.       }
    
59.       else {
    
60.         if (islower(it->first) && (idx >= s || isupper(pattern[idx]))) {
    
61.           cur.push_back(it->first);
    
62.           findMatchesHelper(it->second, pattern, idx, cur, res);
    
63.           cur.pop_back();
    
64.         }
    
65.       }
    
66.     }
    
67.   }
    
68. 
    
69.   shared_ptr<TrieNode> root_;
    
70. };
    
71. 
    
72. int main() {
    
73.   vector<string> dict = { "CaaaC", "CaaaK", "CaaaCa", "CaaaCabcdefgh",
    
74.     "CaaaCabcdefghI", "CbbbbbC", "CabK", "CabbbbbbbCK", "CabbbbbC",
    
75.     "caxxxxxxxxxxxxxxxxxxxxxxxxxxxxxK", "AbbbCddddEffff" };
    
76.   Solution s(dict);
    
77.   s.findMatches("CC");
    
78.   s.findMatches("CaC");
    
79.   s.findMatches("A");
    
80.   s.findMatches("c");
    
81.   s.findMatches("ACE");
    
82.   s.findMatches("AbCE");
    
83.   s.findMatches("ACdE");
    
84.   s.findMatches("ACEf");
    
85.   s.findMatches("CaaadC");
    
86. }
    

复制代码

用Trie做DFS要比一个一个比较省去了一些计算。但是也有一些情况应该可以进一步的优化。
比如dict里有CaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaK和CabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbC，我们的inpute pattern是CaC。
我们会一直深度搜索第一个词直到遇到K。对此我们可以做的一个优化是，在Trie分叉时，我们可以记录下一个大写字母有什么。比如Ca有两个子树，以a开头和以b开头的。我们如果知道以a开头的下一个大写字母是K，我们就可以不进行下去了。但这个优化针对CaaaaaaaaaaaaaaaaCK，CabbbbbbbbbbbbbCC，input CaCC这种情况就没什么用。
原帖里也有人提到了一些不错的优化。我觉得可以跟面试官讨论讨论。
除非有什么别的思路，在Trie的基础上修修补补做优化的话run time不会有很大的提升，而且会吃掉很对额外的空间，不一定值得。

上周电面还不错：G电面
下周一就onsite了，努力准备中。

Interval Tree & Compress String
地里面经
详见7/13 Google NY onsite 面经

原帖第二轮题目可见http://www.geeksforgeeks.org/interval-tree/

重点说一下第三轮的Compress String。
这道题感觉很高频，我至少在三个地里最近的Google面经帖里看到这道题了。一般都是让你先做比较简单的Uncompress String，然后让你说说compress的思路之类的。
uncompress我见过有人po过代码，compress我没有见到地里有很好的分析，网上也搜索无果。花了好几个小时死磕这道题，跟大家分享一些我的思路。
为了简化已经很复杂的题目，假设我们的input string只包含大小写字母。
先说我个人对compress string结果的一些小优化：
1. 重复的次数后缀。
2. 如果重复次数为1，则不进行compress。比如aaabbc压缩为a3b2c。
3. 如果重复的string为一个字母，则不添加[]，比如aaa压缩为a3，abcabcabcabc压缩为[abc]4。
4. 如果重复的string的字数与重复数相等，则不添加重复次数，比如可以abab直接为[ab]，ababab为[ab]3，abcabcabc为[abc]。
之所以做这些优化是因为，比如我们把abab变成[ab]2的话，从结果上讲我们并没有做压缩，而且也会增加我们的编程难度。
有些情况比如abab=>[ab]，或者abcabc=>[abc]2，从结果上来说并没有缩短，我们可以不进行压缩。
下面我演算例子时，会以自己的优化为准。
我们再先考虑一个子问题，abababab如何压缩成[ab]4。
大家应该都见过run length encoding这道题，就是aaabbccc=>a3b2c3。（事实上如果Googling String Compression出来的都是这道题的讨论。）
RLE这道题是以一个letter作为单位来压缩，我们可以对这道题稍作修改以数个letter作为单位来压缩。比如abababab就是以2为单位，abcabcabc就是以3为单位。
而这道题我们的难点在于，我们的input string混合了以一个letter或数个letter作为单位来压缩的情况。我们来看aaaabab原帖中给的例子。
aaaabab可以压缩为a3[ab]，也可以为a4bab。如果纯以字数来看a4bab(5)是更好的方案。
举个更好的例子，
aaaabcabcbcabc可以压缩成下面两种情况：
a4[bcabc]2 以一个letter为单位得到a4，以5个letter为单位得到[bcabc]2
a3[abc]2bcab 以一个letter为单位得到a3，以3个letter为单位得到[abc]2，还剩下无法压缩的bcab
那么我们怎么得到所有结果中最短的结果呢？
可以用递归试遍每一个可能性，compress（aaaabcabcbcabc） = min(a + compress(aaabcabcbcabc), ..., aaa + compress(abcabcbcabc), aaaa + compress(bcabcbcabc), ...)
在递归尝试后半部分的同时，我们要压缩前半部分。而压缩的办法是，以1到k / 2为单位来对进行RLE，取最短的结果。
这段很难叙述清楚，请结合代码来看：

1. 
   
2. #include <unordered_map>
   
3. #include <string>
   
4. #include <iostream>
   
5. 
   
6. using namespace std;
   
7. 
   
8. class Solution {
   
9. public:
   
10.   string compressString(const string& in) {
    
11.     string res1 = "";
    
12.     string res2 = "";
    
13.     if (in.empty()) {
    
14.       return res1;
    
15.     }
    
16.     unordered_map<string, string> record;
    
17.     res1 = compressStringHelper(in, record);
    
18.     do {
    
19.       res2 = res1;
    
20.       res1 = compressStringHelper(res2, record);
    
21.     } while (res2.size() != res1.size());
    
22.     return res1;
    
23.   }
    
24. 
    
25.   string compressStringHelper(string in, unordered_map<string, string>& record) {        
    
26.     if (in.empty()) {
    
27.       return "";
    
28.     }
    
29.     auto it = record.find(in);
    
30.     if (it != record.end()) {
    
31.       return it->second;
    
32.     }
    
33.     const int s = in.size();
    
34.     string res;
    
35.     res = in[0] + compressStringHelper(in.substr(1), record);
    
36.     for (int i = 1; i < s; ++i) {
    
37.       string tmp_r = compressStringHelper(in.substr(i + 1), record);
    
38.       int w_size = 1;
    
39.       string tmp_l = in.substr(0, i + 1);
    
40.       for (int w_size = 1; w_size <= (i + 1) / 2; ++w_size) {
    
41.         string tmp = encode(in.substr(0, i + 1), w_size);
    
42.         if (tmp.size() < tmp_l.size()) {
    
43.           tmp_l = tmp;
    
44.         }
    
45.       }
    
46.       if (res.size() > tmp_l.size() + tmp_r.size()) {
    
47.         res = tmp_l + tmp_r;
    
48.       }
    
49.     }
    
50.     record.emplace(move(in), res);
    
51.     return res;
    
52.   }
    
53. 
    
54.   string encode(string src, int w_size) {
    
55.     int rLen;
    
56.     string res;
    
57.     const int len = src.size();
    
58. 
    
59.     for (int i = 0; i < len; i += w_size) {
    
60.       string c = src.substr(i, w_size);
    
61. 
    
62.       rLen = 1;
    
63.       while (i + w_size < len && compare(src, i, i + w_size, w_size)) {
    
64.         rLen++;
    
65.         i += w_size;
    
66.       }
    
67. 
    
68.       if (rLen == 1) {
    
69.         res += c;
    
70.       }
    
71.       else {               
    
72.         if (w_size == 1) {
    
73.           res += c;
    
74.         }
    
75.         else {
    
76.           res += '[' + c + ']';
    
77.         }
    
78.         if (rLen != w_size) {
    
79.           res += to_string(rLen);
    
80.         }
    
81.       }
    
82.     }
    
83.     return res;
    
84.   }
    
85. 
    
86.   bool compare(const string& src, int l, int r, int w_size) {
    
87.     bool contain_letter = false;
    
88.     for (int i = 0; i < w_size; ++i) {
    
89.       if (isalpha(src[l + i])) {
    
90.         contain_letter = true;
    
91.       }
    
92.       if (src[l + i] != src[r + i]) {
    
93.         return false;
    
94.       }
    
95.     }
    
96.     if (contain_letter)
    
97.       return true;
    
98. 
    
99.     return false;
    
100.   }
     
101. };
     
102. 
     
103. int main() {
     
104.   Solution s;
     
105.   string res;
     
106.   s.encode("aaaabbbccccc", 1);
     
107.   s.encode("abababcdcd", 2);
     
108.   s.encode("abcabc", 2);
     
109.   s.encode("abcabc", 3);
     
110.   s.encode("abcabcabc", 3);
     
111.   s.encode("aaabcabcbcab", 3);
     
112.   s.encode("222222222222", 1);
     
113.   s.encode("[[[[[[[[[[[[[[[", 1);
     
114.   res = s.compressString("aaaabab");
     
115.   res = s.compressString("aaaabcabcbcabc");
     
116.   res = s.compressString("aaabaaabccccdaaabaaabccccd");
     
117.   return 0;
     
118. }
     

复制代码

需要注意的一些地方：
在compare中添加了比较对象包不包含letter的检查，以防止对数字和[]进行压缩。
aaabaaabccccdaaabaaabccccd经过一次压缩为[aaabaaabccccd]2，并不是最优解，如果我们再对其进行压缩可以得到[a3ba3bc4d]2。所以在compressString有个do while loop。
上面的代码是Top-down recursive/DFS with memorialization的写法，有兴趣的可以改写为Botttom-up interative DP的写法。
如果用DP的话，状态转移方程大概是DP[ i ][j]代表从i到j substr的最短压缩，DP[ i ][j] = min(DP[ i ][k - 1] + DP[k][j])。
这里我用了string作为hash table的key。用string做key的话，每次查询都是O(n)的开销。但有一个好处，比如...........ababab...................ababab.........两段ababab的index并不一样，但是直接用string做key则都是ababab，省去了对ababab的重复计算。如果用DP[ i ][j]的话，这种情况并不能直接识别。

这道题我觉得思路应该是没问题的，能想到的test cases也都是正确的。可能有一些我没有想到的test cases，所以并不保证这段代码bug free。

Max Length Identical Subtrees
详见Google 面經求問第一题

这道题一个思路是拆分为LeetCode N0.297 Serialize and Deserialize Binary Tree和 最长公共子串 两个问题。
最长公共子串可以参见
http://blog.csdn.net/hackbuteer1/article/details/7968623
http://dsqiu.iteye.com/blog/1701324
这两篇博文。但是好像并没有很高效的解决最长公共子串的方法。

自己思索并比较了一下，觉得还是原帖里hxtang的方法好。

1. 
   
2. class Solution {
   
3. public:
   
4.   TreeNode* findMaxLengthIdenticalSubtrees(TreeNode* root) {
   
5.     unordered_map<hashNode, int, MyHash> id_map;
   
6.     unordered_map<int, TreeNode*> id_to_node;
   
7.     int max_id = 0;
   
8.     helper(root, id_map, id_to_node, max_id);
   
9.     if (!max_id) {
   
10.       return nullptr;
    
11.     }
    
12.     return id_to_node[max_id];
    
13.   }
    
14.         
    
15. private:
    
16.   struct hashNode {
    
17.     int left_id;
    
18.     int right_id;
    
19.     int val;
    
20.     hashNode(int l_id, int r_id, int v) : left_id(l_id), right_id(r_id), val(v) {}
    
21.     bool operator==(const hashNode& rhs) const{
    
22.       return this->left_id == rhs.left_id && this->right_id == rhs.right_id && this->val == rhs.val;
    
23.     }
    
24.   };
    
25. 
    
26.   struct MyHash {
    
27.     inline size_t operator()(const hashNode& p) const {
    
28.       return (7 * hash<int>()(p.left_id) + 13 * hash<int>()(p.right_id) + hash<int>()(p.val));
    
29.     }
    
30.   };
    
31. 
    
32.   int helper(TreeNode* root, unordered_map<hashNode, int, MyHash>& id_map, unordered_map<int, TreeNode*>& id_to_node, int& max_id) {
    
33.     if (root == nullptr) {
    
34.       return 0;
    
35.     }
    
36.     int left_id = helper(root->left, id_map, id_to_node, max_id);
    
37.     int right_id = helper(root->right, id_map, id_to_node, max_id);
    
38.     hashNode tmp(left_id, right_id, root->val);
    
39.     int id = max(left_id, right_id) + 1;
    
40.     if (id_map.find(tmp) == id_map.end()) {
    
41.       id_to_node[id] = root;        
    
42.       id_map[tmp] = id;
    
43.     }
    
44.     else {
    
45.       max_id = max(max_id, id);
    
46.     }
    
47.     return id_map[tmp];
    
48.   }
    
49. };
    

复制代码

把这道题转化为最长公共子串其实是把这道题复杂化了。
对于下面这棵树来说
     3
   /   \
  4    4
/     /
5    5
  4 是identical subtree。
/
5   
而下面这棵树并没有identical subtree:
       3
      /  \
    2    4
   /     /
  1    2
/     /
5    1
假如有一道题要求"sub graph"， 2为答案的话，我觉得可以转换为最长公共子串来做。不过估计并不会有这种题。
                                                  /
                                                 1

Find Overall Time & Two Power Minimum

今天比较水，贴两道之前做过的题。
第一道是在careercup上看到的，好像Facebook的面经也有看到这道题。题目可看comments里的链接。
第二道是在地里看到的，原帖里我应该也贴了代码。题目我写在comments里了。

1. 
   
2. /*
   
3. * https://www.careercup.com/question?id=5723093194506240
   
4. */
   
5. 
   
6. #include <vector>
   
7. #include <unordered_map>
   
8. #include <string>
   
9. 
   
10. using namespace std;
    
11. 
    
12. class Solution {
    
13. public:
    
14. int findOverallTime(vector<string> tasks, int k) {
    
15.   unordered_map<string, int> m;
    
16.   int delay = 0;
    
17.   int overall = 0;
    
18. 
    
19.   for (int i = 0; i < tasks.size(); ++i) {
    
20.     auto it = m.find(tasks[i]);
    
21.     if (it == m.end()) {
    
22.       m.emplace(tasks[i], i + delay);
    
23.     } else {
    
24.       int pos_suppose = i + delay;
    
25.       int pos_actual = it->second + k;
    
26.       int diff = pos_actual - pos_suppose;
    
27.       if (diff < 0) {
    
28.         it->second = i + delay;
    
29.       }
    
30.       else {
    
31.         ++diff;
    
32.         overall += diff;
    
33.         delay += diff;
    
34.         it->second = i + delay;
    
35.       }
    
36.     }
    
37.     ++overall;
    
38.   }
    
39.   return overall;
    
40. }
    
41. };
    
42. 
    
43. int main() {
    
44.   Solution s;
    
45.   vector<string> tasks1 = { "A", "A", "A" };
    
46.   vector<string> tasks2 = { "A", "A", "B" };
    
47.   vector<string> tasks3 = { "A", "A", "B", "A" };
    
48.   vector<string> tasks4 = { "A", "A", "B", "C", "A" };
    
49.   vector<string> tasks5 = { "A", "A", "B", "B", "A" };
    
50.   vector<string> tasks6 = { "A", "A", "B", "C", "D", "A" };
    
51.   vector<string> tasks7 = { "A", "B", "C" };
    
52.   int res = s.findOverallTime(tasks1, 3);
    
53.   res = s.findOverallTime(tasks2, 3);
    
54.   res = s.findOverallTime(tasks3, 3);
    
55.   res = s.findOverallTime(tasks4, 3);
    
56.   res = s.findOverallTime(tasks5, 3);
    
57.   res = s.findOverallTime(tasks6, 3);
    
58.   res = s.findOverallTime(tasks7, 3);
    
59. }
    

复制代码

1. 
   
2. /*
   
3. * Given an array. Check whether 2 power the minimum of the array is larger than the maximum of the array.
   
4. * follow up 1: (minTakesFront)     If you can take out the front elements in the array, how many steps it takes to make the rest of the array satisfying the above condition?
   
5. * follow up 2: (minTakesBothEnds)  what if you can take out elements from both ends of the array? Then what is the minimum steps to find a subarray that satisfying the above condition?
   
6. */
   
7. 
   
8. #include <iostream>
   
9. #include <string>
   
10. #include <vector>
    
11. #include <algorithm>
    
12. #include <limits>
    
13. 
    
14. using namespace std;
    
15. 
    
16. bool checkPow(const int& minValue, const int& maxValue) {
    
17.   errno = 0;
    
18.   double pow2 = std::pow( minValue, 2 );
    
19.   if ( errno == 0 ) {
    
20.     //  std::pow succeeded (without overflow)
    
21.     if (pow2 > maxValue) {
    
22.       return true;
    
23.     }
    
24.   } else {
    
25.     //  some error (probably overflow) with std::pow.
    
26.     return false;
    
27.   }   
    
28.   return false;
    
29. }
    
30. 
    
31. int minTakesFront(const vector<int>& nums) {
    
32.   int minValue = numeric_limits<int>::max();
    
33.   int maxValue = numeric_limits<int>::min();
    
34.   int s = static_cast<int>(nums.size());
    
35.   int i = s - 1;
    
36.   for (; i >= 0 ; --i) {   
    
37.     minValue = min(nums[i], minValue);
    
38.     maxValue = max(nums[i], maxValue);
    
39.     if (!checkPow(minValue, maxValue)) {
    
40.       break;
    
41.     }
    
42.   }
    
43.   if (i == s - 1) {
    
44.     return -1;
    
45.   }
    
46.   return i + 1;
    
47. }
    
48. 
    
49. // return minimum steps to make a subarray inside the passed in array such that 2 power the minimum is larger the maximum
    
50. // or -1 if there is no such subarray
    
51. int minTakesBothEnds(const vector<int>& nums) {
    
52.   int s = static_cast<int>(nums.size());
    
53.        
    
54.   if (s == 0) {
    
55.     return -1;
    
56.   }
    
57.        
    
58.   vector<vector<int>> f(s, vector<int>(s, 0));
    
59.   for (int i = 0; i < s; ++i) {
    
60.     if (checkPow(nums[i], nums[i])) {
    
61.       f[i][i] = 0;
    
62.     } else {
    
63.       f[i][i] = 1;
    
64.     }
    
65.   }
    
66.        
    
67.   for (int i = s - 1; i >= 0; --i) {
    
68.     int minValue = nums[i];
    
69.     int maxValue = nums[i];
    
70.     for (int j = i + 1; j < s; ++j) {
    
71.       minValue = min(nums[j], minValue);
    
72.       maxValue = max(nums[j], maxValue);
    
73.       if (checkPow(minValue, maxValue)) {
    
74.         f[i][j] = 0;
    
75.       } else {
    
76.         f[i][j] = min(f[i + 1][j], f[i][j - 1]) + 1;
    
77.       }
    
78.     }
    
79.   }
    
80.        
    
81.   //if steps equal to size of the array, all elements have been taken out
    
82.   if (f[0][s - 1] == s) {
    
83.     return -1;
    
84.   }
    
85.        
    
86.   return f[0][s - 1];
    
87. }
    
88. 
    
89. int main()
    
90. {
    
91.   vector<int> test1 = {5};
    
92.   vector<int> test2 = {1};
    
93.   vector<int> test3 = {5, 1, 3};
    
94.   vector<int> test4 = {1, 1, 1};
    
95.   vector<int> test5 = {5, 3, 1};
    
96.   vector<int> test6 = {2, 5, 3, 1};
    
97.   vector<int> test7 = {-2};
    
98.   vector<int> test8 = {1, 5, 3};
    
99.   
    
100.   cout << "test1 front result : " << minTakesFront(test1) << endl;
     
101.   cout << "test2 front result : " << minTakesFront(test2) << endl;
     
102.   cout << "test3 front result : " << minTakesFront(test3) << endl;
     
103.   cout << "test4 front result : " << minTakesFront(test4) << endl;
     
104.   cout << "test5 front result : " << minTakesFront(test5) << endl;
     
105.   cout << "test6 front result : " << minTakesFront(test6) << endl;
     
106.   cout << "test7 front result : " << minTakesFront(test7) << endl;
     
107.   cout << "test8 front result : " << minTakesFront(test8) << endl;
     
108.   cout << endl;
     
109.   cout << "test1 both result : " << minTakesBothEnds(test1) << endl;
     
110.   cout << "test2 both result : " << minTakesBothEnds(test2) << endl;
     
111.   cout << "test3 both result : " << minTakesBothEnds(test3) << endl;
     
112.   cout << "test4 both result : " << minTakesBothEnds(test4) << endl;
     
113.   cout << "test5 both result : " << minTakesBothEnds(test5) << endl;
     
114.   cout << "test6 both result : " << minTakesBothEnds(test6) << endl;
     
115.   cout << "test7 both result : " << minTakesBothEnds(test7) << endl;
     
116.   cout << "test8 both result : " << minTakesBothEnds(test8) << endl;
     
117. }
     
118. 
     

复制代码

Some System Design Related Figures

QPS = query per second
MAU = monthly active users

                       QPS   Capacity
Memory          10M   100GB
Flash               100K  1TB
Hard Drive       100    1TB

Design Twitter
300K read QPS
6000 write QPS
400m tweets per day; 5K/sec daily average; 7K/sec daily peak; >12K/sec during large events
300m MAU

Design Facebook
1.65b MAU
13M peak QPS

Design Uber/Lyft
170k peak QPS

Design Whatsapp/Facebook Messenger
1b users
70% MAU
42b messages per day

Design Youtube/Youtube upload
>1b users
40% DAU
4b video views per day
300 hours per minute new videos uploaded
video file size: for 60 seconds @ 60 fps BluRay H.264 (1080p25 = 56 Mbps): 1.01 GB

Design Netflix
81m users
number of hours per day that users spend watching
100m hours

Design Yelp
145m unique MAU
total reviews 102m

Design TicketMaster
2000 number of businesses

Design Restaurant Reservation System
Opentable:
seating more than 19 million diners per month via online bookings across more than 37,000

Design Google Map
2.3m QPS
Earth Surface Area 5.1 billion km2
>20PB storage

Design Dropbox
500m users
1.2b files uploaded daily

Design Web Crawler
crawls 1.6m web pages per second
1trillion web pages
10b web pages storage

Design Typeahead
Google Search
DAU: 500m
Search: 6 * 6 * 500m = 18b
QPS = 18b / 86400 ≈ 200k
Peak QPS = QPS * 2 ≈ 400k

LZ好勤奋 赞一个

题目来源:LintCode 原题地址 题目: 给定两个二进制字符串,返回他们的和(用二进制表示)。