Leetcode: Google interview questions #2

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;

}

        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

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