Google interview questions #4

REF http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=136847&extra=page%3D1%26filter%3Dsortid%26sortid%3D311%26sortid%3D311
给我小哥没有废话直接上题
我coding速度太慢，只面了一道题目
.鐣欏璁哄潧-涓€浜�-涓夊垎鍦�
给出一个迭代器，迭代器里存了很多个类R的实例, 类R里只有两个参数，都是String类型，分别代表Parent 和 Child，child只有一个Parent，Parent 可以有任意数量child
按所给示例输出所有的层级关系

eg：
A
  B1
  B2
    C1
    C2
  B3
    D1. 1point3acres.com/bbs
    D2. 1point3acres.com/bbs


就是建立一个compiler里面的inheritance graph，然后打印

struct TreeNode{
    string parent;
    string name;
    vector<TreeNode *> children;
    TreeNode(string p, string n) {
        parent = p;
        name = n;
    }
};
class A{
    public:
    string parent;
    string child;
};
void printRecursively(TreeNode *root, string tab) {
    if (root == NULL) return;
    cout << tab << root->name << endl;
    for (int i = 0; i < root->children.size(); i++) {
        printRecursively(root->children[i],tab + " ");
    }
}
void printGraph(vector<A> &source) {
    unordered_map<string,TreeNode*> dic;
    for (int i = 0; i < source.size(); i++) {
        TreeNode *p = NULL, *c = NULL;
        if (dic.find(source[i].parent) == dic.end()) {
            p = new TreeNode("",source[i].parent);
            dic[source[i].parent] = p;
        }
        if (dic.find(source[i].child) == dic.end()) {
            c = new TreeNode(source[i].parent,source[i].child);
            dic[source[i].child] = c;
        }
        p = dic[source[i].parent];
        c = dic[source[i].child];
        p->children.push_back(c);
    }
    for (auto t : dic) {
        if (dic[t.first]->parent.length() == 0) {
            printRecursively(dic[t.first],"");
        }
    }
}
int main()
{
    A a1;
    a1.parent = "A";
    a1.child = "B1";
    A a2;
    a2.parent = "A";
    a2.child = "B2";
    A a3;
    a3.parent = "A";
    a3.child = "B3";
    A b1;
    b1.parent = "B2";
    b1.child = "C1";
    A b2;
    b2.parent = "B2";
    b2.child = "C2";
    A c1;
    c1.parent = "B3";
    c1.child = "D1";
    A c2;
    c2.parent = "B3";
    c2.child = "D2";
    vector<A> v;
    v.push_back(a1);
    v.push_back(a2);
    v.push_back(a3);
    v.push_back(b1);
    v.push_back(b2);
    v.push_back(c1);
    v.push_back(c2);
    printGraph(v);
}

---------------------------------------------------------------------------------------
REF http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=134335&extra=page%3D1%26filter%3Dsortid%26sortid%3D311%26sortid%3D311
4月底MTV面的onsite, 很奇怪是5面，至今没消息，直接上面经
鏉ユ簮涓€浜�.涓夊垎鍦拌鍧�. 
1.日本大叔-google 1point3acres
来晚了20分钟导致后面很紧。先写反转链表，然后第二题把链表变成a1->an->a2->an-1
LC reorder list
2.白人小哥+沉默的阿三
第一题是path sum难度一样的dp水果。 第二题给画布上的几个线段，问怎么画最快（移动画笔会浪费时间). Waral 鍗氬鏈夋洿澶氭枃绔�,
待写
3.阿三
到这面的时候才20分钟后面找我吃饭的大叔就来了，草草写完，给一个字符串，问可否组成一个新串使得每两个相邻字符不重复
重复，见Google interview questions #2 onsite第1题
. Waral 鍗氬鏈夋洿澶氭枃绔�,
午饭是个黑叔叔，用手直接抓食物吃，震精

4.光头小白
先问简历，然后又是一个path sum难度一样的dp水果


5.白人小帅
q: 玩过扫雷吗？
a: yes
q: 实现它
a: wtf??
http://www.careercup.com/question?id=11966706
#1 生成地图
给定2维数组，雷的个数为 x / (n * m), x自定义，随机放雷，不重复
生成数字

#2 玩家点击（设置额外数组）
右键：标记
左键：
双击：检测周边的雷是否还没被扫光

#3 胜利失败条件



-------------------------------------------------------------------------- REF http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=137928&extra=page%3D1%26filter%3Dsortid%26sortid%3D311%26sortid%3D311
可能是因为我做得慢，总共就做了一道题，就是一个游戏。 
input string：“+++--++-+”
游戏规则：每人每次可以 flip "++" to "--"（必须是相邻的）


第一问：generate all possible moves
第二问：determine if this player can will
Extra：这两个问题的implementation的Big-O

补充内容 (2015-7-12 13:13):
下个人没法flip了这个人就赢；all possible moves for next flip
permutation,  O(n!) 
T(n) = T(n - 1) + T(n - 1) + T(n - 1)...... + c = (n - 1) * T(n - 1) + c
T(n - 1) = (n - 2) * T(n - 2)
T(n - 2) = (n - 3) * T(n - 2)
.....
So T(n) = n!

bool canWin(string s) {
    int start = -1,end = -1;
    for (int i = 0;
    i < s.length();
    i++) {
        if (s[i] == '+') {
            if (start != -1 && i - start > 0) {
                string t = s;
                t[start] = '-';
                t[i] = '-';
                if (!canWin(t)) return true;
                start++;
                }else {
                start = i;
            }
            }else {
            start = -1;
        }
    }
    return false;
}

另一方法：博弈论，可达到O(n^2), 关键词game theory, nimber, grundy number

http://www.1point3acres.com/bbs/thread-137953-1-1.html
----------------------------------------------------------------------------------------

Linked List e.g 1->5->2->3->7
Modify it so that it becomes: 1->7->5->3->2

一头一尾，第二头第二尾，O（1）空间复杂度，O（n）时间复杂度

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

  Given a bunch of N random points in space, how would you draw a line such that N/2 of them were to the left of the line and N/2 to the right of it. Complexity 

按x坐标用quick select，找出median，只需要O(n) 

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

Given an unbalanced binary tree, write code to select a node at random (each node has an equal probability of being selected).

reservoir sampling

void helper(TreeNode *root, int &count, int choice) {
    if (root == NULL) return NULL;
    count++;
    if (rand(1,count) == 1) {
        choice = root;
    }
    helper(root->left,count,choice);
    helper(root->right,count,choice);
}

TreeNode *findRandomNode(TreeNode *root) {
    TreeNode *choice = NULL;
    int count = 0;
    return helper(root,count,choice);
}

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

给一个array和target，找出在array里与target最接近的值的index

类似LC search insert position

int getSmallest(int i, int j) {
    for (int s = 1; s <= j; s++) {
        if (s * i % j == 0) return s * i;
    }
}

int jumpBack(vector<int> &shuffle) {
    vector<int> visit(shuffle.size(),-1);
    int count = 0, preCount = 1;
    for (int i = 0; i < shuffle.size(); i++) {
        count = 0;
        int index = i;
        while (visit[index] == -1) {
            count++;
            visit[index] = shuffle[i];
            index = shuffle[index];
            if (visit[index] != -1 && visit[index] != visit[i]) return -1;
        }
        if (count != 0) preCount = getSmallest(count,preCount);
    }
    return preCount;
}

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

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

onsite

1. card shuffler：shuffle的程序是一个简单的array，array里的值代表当前位置卡

片的下一个位置 

e.g 当前卡片位置ABCDE shuffle array是01234的话下个卡片位置还是ABCDE，43210的

话下个卡片位置是EDCBA。

问给定一个shuffle array，不断用这个array去shuffle，能否得到最初的card deck，

能得话要多少次。 

吐槽下，面试官是个三哥，全程非常严肃／黑脸，我说句话就用小本子记下搞得我很紧

张。我说用java写可以吗，曰可以，刚写了两行问我add是啥意思，不知道是想考我基

础知识还是不懂java。

O(n), 对shuffle里面的每一个点都走一遍，最后走回起始点，走过的路径全部mark起来，记录count。mark过的可以直接跳过
最后取所以count的最小公约数即可

2. 给定一个binary search tree，返回range内所有key，key可以有重复。 

略

版上出现了多次的把一个数拆成任意个平方和的最小拆法。

DP，重复

面试官是中年国人大叔，除了告诉我题目是啥就在电脑上自顾自工作，问话要问两遍才

有反应。写完说我程序有问题，查了半天查不出bug，然后指出我漏了个尖括号，跪了

。。

3. 版上出现多次的longest consecutive sequence in tree 

follow up 如何加速，memory放不下怎么办。

国人小哥比较nice，但是只要我不和他主动说话绝不主动和我说话，因为前两场心情略

糟糕写完题目在白板前发呆，哥们就望着我啥也不说，尴尬。。当然也不怪他我自己比

较紧张，回家发现有很弱智的bug但小哥没提不知道怎么回事，可能放我水了

跟LC #128 Longest Consecutive Sequence 类似
对于follow up，hashmap<int,int>里可只记录范围，将范围内的都删掉省空间，但是如果给定的数组或树内有重复元素，则次方法不适用

4. 设计个用bit形式表示时间（小时：分钟）的clock，

e.g 10:15可以写作1010:1111，每个bit是一个小灯泡，打印所有有且仅有n盏灯亮着的

时间，

e.g. n＝0就只有0:0一种可能。

面试官是亚裔年轻mm，话不多人很cool，但是思路清晰会引导面试者，感觉碰到懂得引

导面试者或冷漠面试官对面试人表现会有很大影响，真的是看运气了。

permutation，遍历写法

int countOnes(int num) {
    int count = 0;
    while (num > 0) {
        count++;
        int twosC = ~num + 1;
        num = (~(twosC & num)) & num;
    }
    
    return count;
}

string toBinary(int num) {
    string bi = "";
    while (num > 0) {
        char c = (num % 2) + '0';
        bi = c + bi;
        num /= 2;
    }
    if (bi.length() == 0) return "0";
    return bi;
}

vector<vector<int> > precompute() {
    vector<vector<int> > table(6);
    
    for (int i = 0; i < 60; i++) {
        int count = countOnes(i);
        table[count].push_back(i);
    }
    return table;
}


void printPermutation(int n) {
    vector<vector<int> > table = precompute();
    vector<string> rt;
    
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j < table[i].size(); j++) {
            for (int k = 0; k < table[n - i].size(); k++) {
                if (table[i][j] < 24) {
                    rt.push_back(toBinary(table[i][j]) + ":" + toBinary(table[n - i][k]));   
                }
            }
        }
    }
}

#1 递归的解法,注意插入rt时的条件，仅仅只是 n == 0，如果加上 && index == 6，则将会过滤掉10,100，1000。。。等等case
#2 string "0"与”00“要是重复，要过滤掉

int toNum(string bi) {
    int num = 0;
    for (int i = 0; i < bi.length(); i++) {
        num = num * 2 + bi[i] - '0';
    }
    
    return num;
}

void computeMinute(vector<string> &rt,int n, string s,int index) {
    if (n < 0 || index > 6 || toNum(s) > 59) return;
    if (n == 0) {
        rt.push_back(s);
    }
    
    if (s != "0") {
        computeMinute(rt,n,s + '0',index + 1);
        computeMinute(rt,n - 1,s + '1',index + 1);
    }else {
        computeMinute(rt,n - 1,"1",index + 1);
    }
}

void computeHour(vector<string> &rt,int n, string s,int index) {
    if (n < 0 || index > 5 || toNum(s) > 23) return;
    vector<string> mins;
    computeMinute(mins,n,"0",0);
    
    for (int i = 0; i < mins.size(); i++) {
        rt.push_back(s + ":" + mins[i]);
    }
    
    if (s != "0") {
        computeHour(rt,n,s + '0',index + 1);
        computeHour(rt,n - 1,s + '1',index + 1);
    }else {
        computeHour(rt,n - 1,"1",index + 1);
    }
}

vector<string> printPer1(int n) {
    vector<string> rt;
    computeHour(rt,n,"0",0);
    return rt;
}

5.算法游戏，给一个只有＋－两种字符的array，两个玩家，轮到某个玩家他可以任选

两个连续的－－将他们变成＋＋，如果某个玩家发现自己无法行动则赢得游戏，要求写

isWin（String s）判断先行动的玩家能否赢。

followup 如何优化，时间上和空间上。

面试官是做android前端的白人mm，非常活泼健谈，一路聊天愉快，面完就感觉她会给

强推。
重复