Leetcode: Google interview questions #2
REF http://www.mitbbs.com/article_t/JobHunting/32996813.html
phone: 1.given an order string "abc" check if "aabdccd" maintain the order
"aabdccd" -> true;
"abbca" -> false;
note:order does not contain all chars in s
2.abbre word, given a list of words, return a map contains abbre word
map to a list of original word
abbre word means: word -> w2d, international -> i11l
跟anagram差不多
COME_BACK
onsite: 1.毛子 given "AABBCC" return "ABCABC", no same char next to each
other
"ABBB" -> exception
"ABBA" -> "ABAB"
用map记录下所有字符出现的次数，若某一个字符超过（总数 + 1）/ 2以上则为exception
在while loop之后，最终没有字符或者只会有一种字符被拉下，然后从头开始填充
*思考constant space的解法
2.国人 excel encoding, leetcode那个
given [1,2,0,6,9] and target 81, return true if add “+” between
numbers can add up to target. 12+0+69=81 -> true.
类似subset题目，将每个数字之间的加号为设为“有”或“无”
注意base case 为 target == curSum, 不是target = 0
3.白人小哥 java 一个数据结构改错，没什么tricky的地方
4.三哥 abbre word again... follow up是 word->w2d, 另一个wold->wo1d,
也就是说不能group起来，每个都是unique的
返回所有可能的abbreviation
5.毛子 maximum path from upper left to right bottom, follow up是除了
往下往右，还可以往左走，怎么避免死循环。
follow up用BFS / dijkstra
-------------------------------------------------
REF http://www.mitbbs.com/article_t/JobHunting/33000225.html
给一个起点，一个终点，然后已知这个人从起点到终点的所有线段，但是打乱了，要你
复原走的路线。
难点是路线里面可能有Cycle，而且会重复。
比如给的是A-->F
线段是 B->C, D->E, A->B, C-D, E->B, B->C, C->F
复原结果是 A B C D E B C F
X. Sort intervals by start point.------------------------------------
需要建立有向图 #1 recursion + back track
设一个set来存所有的edge，走过的就删掉
base case 是当edge为空，此时又刚好到达终点
另一个是当edge为空，此时到达不了终点，或者当前点无路可走。然后返回上一步，换
一条路径
#2 permutation，permute所有线段，然后走一遍检测。优化条件是每段线的头尾是否
是相连
Read full article from Leetcode: Google interview questions #2
REF http://www.mitbbs.com/article_t/JobHunting/32996813.html
phone: 1.given an order string "abc" check if "aabdccd" maintain the order
"aabdccd" -> true;
"abbca" -> false;
note:order does not contain all chars in s
bool checkOrder(string order, string s) { vector<int> v(256,-1); for (int i = 0; i < order.size(); i++) { v[order[i]] = i; } int curOrder = 0; for (int i = 0; i < s.length(); i++) { if (v[s[i]] == -1) continue; if (v[s[i]] < curOrder) { return false; } curOrder = v[s[i]]; } return true;}2.abbre word, given a list of words, return a map contains abbre word
map to a list of original word
abbre word means: word -> w2d, international -> i11l
跟anagram差不多
COME_BACK
onsite: 1.毛子 given "AABBCC" return "ABCABC", no same char next to each
other
"ABBB" -> exception
"ABBA" -> "ABAB"
用map记录下所有字符出现的次数，若某一个字符超过（总数 + 1）/ 2以上则为exception
在while loop之后，最终没有字符或者只会有一种字符被拉下，然后从头开始填充
*思考constant space的解法
string noNext(string s) { unordered_map<char int=""> map; for (int i = 0; i < s.length(); i++) { if (map.find(s[i]) == map.end()) { map[s[i]] = 1; }else { map[s[i]]++; } } string temp; temp.resize(s.length()); char left = '\0'; int i = 0; bool flag = true; while (i < temp.length() && flag) { for (auto kv : map) { if (map[kv.first] > (temp.length() + 1) / 2) return "exception"; if (map[kv.first] != 0) { if (i != 0 && kv.first == temp[i - 1]) { left = kv.first; flag = false; break; } temp[i] = kv.first; map[kv.first]--; i++; } } } if (i == temp.length()) return temp; string rt; int index = 0; rt.resize(temp.length()); if (temp[0] != left) { rt[index] = left; index++; map[left]--; } for (int j = 0; j < temp.length() && index < temp.length(); j++) { rt[index] = temp[j]; index++; if (map[left] > 0 && left != temp[j] && left != temp[j + 1]) { rt[index] = left; index++; map[left]--; } } return rt;}given [1,2,0,6,9] and target 81, return true if add “+” between
numbers can add up to target. 12+0+69=81 -> true.
类似subset题目，将每个数字之间的加号为设为“有”或“无”
注意base case 为 target == curSum, 不是target = 0
bool helper(vector<int> &nums, int target, int curSum, int index) { if (index == nums.size() && target == curSum) return true; if (target < 0 || index >= nums.size()) return false; if (helper(nums,target, curSum * 10 + nums[index],index + 1)) { return true; } if (index != 0 && helper(nums,target - curSum,nums[index],index + 1)) { return true; } return false;} bool possibleSum(vector<int> &nums, int target) { return helper(nums,target,0,0);}4.三哥 abbre word again... follow up是 word->w2d, 另一个wold->wo1d,
也就是说不能group起来，每个都是unique的
返回所有可能的abbreviation
vector<string> allAbbre(string s) { vector<string> rt; if (s.length() == 0) return rt; if (s.length() < 3) { rt.push_back(s); return rt; } for (int i = 0; i < s.length() - 1; i++) { string prefix = s.substr(0,i + 1); for (int j = s.length() - 1; j > i + 1; j--) { string suffix = s.substr(j); rt.push_back(prefix + to_string(j - i - 1) + suffix); } } return rt;}往下往右，还可以往左走，怎么避免死循环。
follow up用BFS / dijkstra
-------------------------------------------------
REF http://www.mitbbs.com/article_t/JobHunting/33000225.html
给一个起点，一个终点，然后已知这个人从起点到终点的所有线段，但是打乱了，要你
复原走的路线。
难点是路线里面可能有Cycle，而且会重复。
比如给的是A-->F
线段是 B->C, D->E, A->B, C-D, E->B, B->C, C->F
复原结果是 A B C D E B C F
X. Sort intervals by start point.------------------------------------
需要建立有向图 #1 recursion + back track
设一个set来存所有的edge，走过的就删掉
base case 是当edge为空，此时又刚好到达终点
另一个是当edge为空，此时到达不了终点，或者当前点无路可走。然后返回上一步，换
一条路径
#2 permutation，permute所有线段，然后走一遍检测。优化条件是每段线的头尾是否
是相连
Read full article from Leetcode: Google interview questions #2
