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 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;
}

        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

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);
}

        3.白人小哥 java 一个数据结构改错，没什么tricky的地方
        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;
}

        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

------------------------------------
需要建立有向图 #1 recursion + back track
设一个set来存所有的edge，走过的就删掉
base case 是当edge为空，此时又刚好到达终点
另一个是当edge为空，此时到达不了终点，或者当前点无路可走。然后返回上一步，换
一条路径

#2 permutation，permute所有线段，然后走一遍检测。优化条件是每段线的头尾是否
是相连
----------------------------------------------