Google interview questions #5

REF： http://www.mitbbs.com/article_t/JobHunting/33011505.html
Google
电面了2轮，题目有：
一个grid，点代表城市，边代表道路，输入是一个起始点跟一堆destination,还有哪些
路被blocked 打印所有能到的点
DFS或BFS都可以，开2d array或hashmap存visit信息

老题，2d matrix的row跟column都是sorted, 在里面搜某个数
LC #240 Search a 2D Matrix II 

oil pipeline problem, 下面这个链接的10.3-9
http://staff.ustc.edu.cn/~csli/graduate/algorithms/book6/chap10
找median， quick select（一种是常规的random pivot select，另一种是deterministic select，见algorithm课第3周）

补充问题是如果有2根pipeline，怎么放
找1/4 和 3/4的点

------------------------------------------------------------------------------
REF：http://www.mitbbs.com/article_t/JobHunting/33012223.html
1.一个字符串，从字典查出字符串所有单词，然后怎么提升效率,比如输入
whoisbillgates,返回['who', 'is','bill','gates']
Trie
2.N*N的矩阵，M个朋友随机住在矩阵上，求聚会地点，满足所有朋友总路程最短, lg复
杂度
如果是manhattan distance，找所以点的x的median跟y的median

3.树里的所有duplicated子树，O（n)遍历一次
in order遍历，把每个node的值给串成string，只要对比string就知道有没有重复的子树

string helper(vector<TreeNode *> &rt, TreeNode *root,unordered_set<string> &dic) {
    if (root == NULL) return "$"; // special char
    string s = helper(rt,root->left,dic);
    s += root->val;
    s += helper(rt,root->right,dic);

    if (dic.find(s) != dic.end()) {
        rt.push_back(root);
    }else {
        dic.insert(s);    
    }
    
    return s;
}

vector<TreeNode *> findDup(TreeNode *root) {
    unordered_set<string> dic;
    vector<TreeNode*> rt;
    helper(rt,root,dic);
    return rt;
}

4.BST，给定一个数值，返回BST中最接近的节点， lg n
binary search

void helper(TreeNode *root,int target,int &minVal,int &found) {
    if (root == NULL) return;
    if (abs(root->val - target) < minVal) {
            minVal = abs(root->val - target);
            found = root->val;
    }
    if (root->val < target) {
        helper(root->right,target,minVal,found);
    }else {
        helper(root->left,target,minVal,found);    
    }
}

int findClosest(TreeNode *root,int target) {
    int found = 0,minVal = INT_MAX;    
    helper(root,target,minVal,found);
    return found;
}

5.Minus one
类似plus one，特殊情况：当给出的数字为0时

6.一个整数链表，返回最长连续数字长度 o(n)， 例如输入[10,6,2,15,5,9,1,3,100,4
],返回6，因为1-6是连续的
LC #128 longest consecutive sequence

7.一个矩阵，矩阵中节点为一个二元组，如果当前节点为M[a][b] =(x,y),下一个访问
节点为M[a+x][b+y],求从一点出发是否可以遍历矩阵
没啥可说的，O(n^2)

bool canGoAround(vector<vector<pair<int,int> > > &matrix,int row, int col) {
    int m = matrix.size();
    int n = matrix[0].size();
    vector<vector<bool> > visit(m,vector<bool>(n,false));
    int count = m * n;
    
    while (count > 0) {
        if (row < 0 || row == m || col < 0 || col == n || visit[row][col]) {
            return false;
        }
        visit[row][col] = true;
        row += matrix[row][col].first;
        col += matrix[row][col].second;
        count--;
    }
    
    return true;
}

8.判断任意两个人是否有血缘关系，自己定义person类
bfs, 加速的话可以同时从p1，p2出发

bool ifRelated(Person *p1, Person *p2) {
    queue<Person *> que;
    unordered_set<Person*> visit;
    que.push(p1);
    
    while (!que.empty()) {
        Person *me = que.front();
        que.pop();
        if (me == p2 || me->mom == p2 || me->dad == p2) return true;
        
        if (visit.find(me->mom) != visit.end()) {
            visit.insert(me->mom);
            que.push(me->mom);
        }
        if (visit.find(me->dad) != visit.end()) {
            visit.insert(me->dad);
            que.push(me->dad);
        }
        for (Person *k : me->kids) {
            if (k == p2) return true;
            if (visit.find(k) != visit.end()) {
                visit.insert(k);
                que.push(k);
            }
        }
    }
    
    return false;
}

--------------------------------------------------------------------------------
REF http://www.mitbbs.com/article_t/JobHunting/33011907.html
1. Given a robot and a maze, the robot supports these apis: Turn left, move forward, checkIsExit
Write a program to make it move to the exit
取决于题意，可能是给定一个矩阵，那就是简单的bfs或dfs
或者没有给定矩阵，不能标记，那得用pledge algorithm
https://en.wikipedia.org/wiki/Maze_solving_algorithm
http://site.douban.com/guokr/widget/notes/1670101/note/182257056/
https://www.youtube.com/watch?v=_KxAMV-2tKU
http://cs.stackexchange.com/questions/29705/maze-solving-algorithms-pledge-algorithm


2. Design Youtube access control system, storage, scales


3. Suppose there are k threads, write a multi-thread program to make them come to deadlock, I use semaphore at first, then was asked to implement itwith countDownLatch


4. RunLength encoding, discuss various ways to minimize the encoded string under different constraints


5. Design a system to generate Ids for distributed DBs, discuss various Zookeeper patterns (leader elections etc). For a given number, how to return minimum number of squares that sums up to this number



-------------------------------------------------------------------

REF: http://www.mitbbs.com/article_t/JobHunting/33012339.html

题目：像apple tv，chrome tv之类的，用户可以搜索电影名字，但只能用remote在一

个虚拟的keyboard上搜索，只能在虚拟键盘上下左右移动。现在给定键盘如下：

a b c d e

f g h i j

k l m n o

p q r s t

u v w x y

z

如果用户要搜索电影名字为 cars，那么需要先往右走两步到c，输入enter，再往左走

两步到a，输入enter，再往下走3步往右走2步到r，输入enter，再往右走一步到s，输

入enter。现在规定L，R，U，D分部代表左，右，上，下移动一步，！代表输入enter，

那么用户动作可以表示成 RR!LL!DDDRR!R!

要求写一个函数，输入为一个string代表电影名字，输出为一个string代表用户的动作。

小印面试官，面了当天晚上给negative feedback，挂了。我面试中做的不好的是，没

有立马想到最佳solution，一开始提用bfs，被他否定后来提示下，想到用2d array坐

标，后来code写的还算顺利。但还是被小印无情的挂了。

对每个字母都坐标化，假设初始从‘a’开始
row = char / 5
col = char % 5

string helper(char move,int step) {
    string rt = "";
    for (int i = 0; i < step; i++) {
        rt += move;
    }
    
    return rt;
}

string fromOneLetterToAnother(char c1, char c2) {
    string move = "";
    int row1 = (c1 - 'a') / 5, col1 = (c1 - 'a') % 5;
    int row2 = (c2 - 'a') / 5, col2 = (c2 - 'a') % 5;
    // down
    if (row2 > row1) {
        move += helper('D',row2 - row1);
    }
    // up
    else if (row2 < row1) {
        move += helper('U',row1 - row2);
    }
    // R
    if (col2 > col1) {
        move += helper('R',col2 - col1);
    }
    // L
    else if (col2 < col1) {
        move += helper('L',col1 - col2);
    }
    
    return move;
}

string movement(string input) {
    string output = "";
    char pre = 'a';
    
    for (int i = 0; i < input.length(); i++) {
        output += fromOneLetterToAnother(pre,input[i]) + "!";
        pre = input[i];
    }
    
    return output;
}

----------------------------------------------------------------------------------------------

REF: http://www.mitbbs.com/article_t/JobHunting/32933923.html
1. Wildcard match
LC原题

2. http://www.fgdsb.com/2015/01/25/peek-iterator/类似。写一个de duplicator,wrap 几个stream，输出的stream全是不重复数字。
hash所有输出的结果

class It{
public:
    It(vector<int> &data) {
        ptr = 0;
        this->data = data;
    }
    It() {}
    
    bool has_next() {
        return ptr < data.size();
    }
    int get_next() {
        int rt = data[ptr];
        ptr++;
        return rt;
    }

private:
    vector<int> data;
    int ptr;
};

class Deduplicator{
public:    
    Deduplicator(vector<int> &data) {
        it = It(data);
    }

    int get_next() {   
        if (!st.empty()) {
            int rt = st.top();
            st.pop();
            return rt;
        }
        
        if (!has_next()) {
            return -1;    
        }
        int rt = st.top();
        st.pop();
        return rt;
    }

    bool has_next() {
        if (!st.empty()) {
            return true;
        }
        
        if (!it.has_next()) return false;
        int rt = it.get_next();
        while (dic.find(rt) != dic.end()) {
            if (it.has_next()) {
                rt = it.get_next();
            }else {
                return false;    
            }
        }
        dic.insert(rt);
        st.push(rt);
        return true;
    }

    
private:
    It it;
    unordered_set<int> dic;
    stack<int> st;
};

3. 求一个stream，出现次数最多的数字。然后扩展到N个machine的情况。
系统设计题
#1 储存：单机存不下，有一个（或多个）master专门用来收数字，然后分发到N个机子上，
也可以是环状结构（类似consistent hashing），各机器自己处理接受，然后发到其他机器
#2 计算：各机器自己计算，汇报给其中一台

4. 假设某个company在不同国家都有office，每个国家的office，如果是当地的假期，
就可以放假了。假设可以查询任意航班的信息，每个星期只能呆在一个地方，只有周末
的时候才能飞去别的国家。找一个放假天数最多的schedule。
这题够开放！
假期，输入可为：n个国家 of 54周 of 假期个数
航班，输入可为：54个n * n 2d数组
对每个国家的星期按假期数量排序，按dfs或bfs走都可，每条path都要走一遍才能得出最多假期

输出为一个path

5. LRU + 一些 C++问题。
LC原题

6. 这题记不大清楚了。好像是Longest increasing consecutive sequence， 然后一
个Tree的该进版。求longest increasing consecutive path。
Longest Increasing Continuous subsequence
Longest Increasing Continuous subsequence II 2d数组
Longest Increasing Subsequence


7. file system design。就是设计一个大数据的存取问题。存在disk上。我就是
partition + hash + cache那一套糊弄过去了。