Google interview questions #7

ref: 讨论 http://www.mitbbs.com/article_t1/JobHunting/32574909_0_1.html
13年11月，国内电面

10月17日，第一轮电面：
第一题：上海的电话isTree(vector<pair<int,int> >& edges); (离散化+dfs判环
判联通)
树的条件：
#1 没有环
#2 所有node都联通
dfs + hashmap记录visit情况

并交集
http://blog.csdn.net/dm_vincent/article/details/7655764

class UnionFind {
public:
    UnionFind(int number) {
        count = number;
        for (int i = 0; i < number; i++) {
            parent.push_back(i);
            size.push_back(1);
        }
    }
    
    int find(int x) {
        while (x != parent[x]) {
            x = parent[x];
        }
        return x;
    }
    
    void do_union(int x,int y) {
        int p1 = find(x);
        int p2 = find(y);
        if (x == y) return;
        if (size[p1] > size[p2]) {
            size[p1] += size[p2];
            parent[p2] = p1;
        }else {
            size[p2] += size[p1];
            parent[p1] = p2;
        }
        count--;
    }
    
    bool hasCycle() {
        return count == 1;    
    }
    
private:
    int count;
    vector<int> parent;
    vector<int> size;
};

bool isTree(vector<pair<int,int>> &edges, int n) {
    UnionFind uf(n);
    for (int i = 0; i < edges.size(); i++) {
        if (uf.find(edges[i].first) == uf.find(edges[i].second)) {
            return false;    
        }
        uf.do_union(edges[i].first,edges[i].second);
    }
    
    return uf.hasCycle();
}

第二题，
Given a 2D space of maximum size NxN which supports two operations :
[1] void UPDATE(x,y,v) - sets the value of cell [x,y] to v
[2] int QUERY(x1,y1,x2,y2) - returns sub-rectangle sum (x1,y1) to (x2,y2)
inclusive, and there is an infinite stream of such 2 types of
operations which have to supported. How would you store the values for
efficient updates and retrievals ? （二维线段树 说算法+分析复杂度）
一维线段树：
http://www.cnblogs.com/TenosDoIt/p/3453089.html
http://www.geeksforgeeks.org/segment-tree-set-1-sum-of-given-range/
http://www.geeksforgeeks.org/segment-tree-set-1-range-minimum-query/

二维线段树：

第一轮答得还可以。
10月30日，第二轮电面：(挂)
美国的电话，面试官很nice：
第一题。一个二叉树，节点值有正有负，求树中的任意路径的最大值。路径的值就
是路径经过点的值的和。然后我说dfs，面试官就让写代码 。 写代码一开始dfs的接
口声明有问题，期间停下来修改了一下，然后写完。被面试官查出1个bug。面试官提示
了，一开始找出了另外个bug；面试官又提示了一下，才找出了面试官想要我fix的bug
。杯具。

LC # 124

第二题。给三个字符串，a，b，c。问a 和b 能不能组成c，且保证c 中a b 的字母
顺序不变。 一开始我给了一个没验证贪心的想法。然后面试官让我验证或举个反例。
我想贪心多数没戏，就又说了种dp的思路。面试官让我写下来。我写完之后，让我解释
了解释。然后突然悲催地发现我的解法是O(2^n)的。。面试后想想如果我的解法状态去重后，就和普通的dp无异了。。 杯具 。。 然后就挂了。

假设：a.length + b.length = c.length, a和b中有相同字符

3个指针 ia, ib, ic分别指向a, b, c. foo() : boolean 返回a, b能否组成c
bool foo(ia,ib,ic) {
    bool flag1 = false;
    bool flag2 = false;
    if (a[ia] == c[ic]) {
        flag1 = foo(ia + 1, ib, ic + 1);
    }
    if (b[ib] == c[ic]) {
        flag1 = foo(ia, ib + 1, ic + 1);
    }
    return flag1 || flagb
}

显而易见，子问题重复，所以用DP

bool canBuild(string a,string b,string c) {
    if (a.length() + b.length() != c.length()) return false;
    int m = a.length(), n = b.length();
    vector<vector<bool>> dp(m + 1,vector<bool>(n + 1,false));
    dp[0][0] = true;
    // pre-process
    for (int i = 0; i < m; i++) {
        if (a[i] == c[i]) {
            dp[i + 1][0] = true;
        }else {
            break;
        }
    }
    // pre-process
    for (int i = 0; i < n; i++) {
        if (b[i] == c[i]) {
            dp[0][i + 1] = true;
        }else {
            break;    
        }
    }
    
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            dp[i + 1][j + 1] = (a[i] == c[i + j + 1] && dp[i][j + 1])
                    || (b[j] == c[i + j + 1] && dp[i + 1][j]);
        }
    }
    
    return dp[m][n];
}

--------------------------------------------------------------------------------------------------------
ref: https://vermashubhang.wordpress.com/2014/02/28/google-summer-internship-interview-questions/
1. You are given a number in the formed of a linked list as given below :

eg. 1 -> 2 -> 3 -> 4 represents the number 1234

You have to increment the number by 1 i.e. you have to change the number in the linked list to 1235. The number in the list can be arbitrarily large.

Take two pointers to mark the last non-nine digit and the second one for traversal of the array

2. What is a Binary Search Tree ? Given a binary Search Tree and a value as N. You have to find out the number in the BST nearest to this number N i.e. with the minimum modulus of difference value.

lgN，小的走左边，大的右边，每次记录difference

3. You are given a Binary Search Tree and a sum value S. You have to find out the pair of numbers in the binary search Tree whose sum is equal to S .

hashmap, 走一遍tree
two pointer？？？怎么做

4. You are given an array of numbers

a1 , a2, a3, a4, a5,…….

you have to sort the array in the following form.

a1 <=a2 >= a3 <= a4 >= a5.

扫一遍，不符合rule的就swap

void reorder(vector<int> &nums) {
    if (nums.size() < 2) {
        return;
    }
    
    for (int i = 0; i < nums.size() - 1; i++) {
        if (i % 2 == 0 && nums[i] > nums[i + 1]) {
            swap(nums[i],nums[i + 1]);
        }
        if (i % 2 == 1 && nums[i] < nums[i + 1]) {
            swap(nums[i],nums[i + 1]);
        }
    }
}

----------------------------------------------
ref: http://www.mitbbs.com/article_t/JobHunting/33054861.html

给一个 n*m 的房间，房间里存在各种可能的墙，房间的格子里已经放了 e 个器材，要
求新放一个器材，放置位置距其它 e 个器材的距离最近。Breadth-first search.

从每个器材处出发做bfs，各个器材所生成的距离累加。最后取最小值
O(e * m * n)

如果题目是不包含障碍物：
#1 各建1个n长度和m长度的数组，n[i]表示所有row index小于i的器材的个数，m[i]表示所有col index小于i的器材个数
o(n * m)
#2 根据m[i]算出第一行的值
#3 如果index横向移动，只需要m[i]来计算，如果纵向移动，需要n[i]

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

ref: http://www.mitbbs.com/article_t/JobHunting/33056297.html

在别处看到别的公司也考，突然想起来我G onsite貌似挂在这题上了。想请教请教各位
大牛怎么做

“给你一棵树，不是binary的，每个节点会有任意个children，然后这棵树是存在一个
数组里的，数组的每个元素就是一个节点，节点包含了它的index以及它的parent的
index，而不是children的index哦，所以这棵树是从child指向parent的。最后是给我
这个数组和一个节点的index，让我删除这个index以及它的子树，只能用O(n)的空间复
杂度，而且大小是确定好的”
数组里各个node是打乱的，不是topologically sorted的

update：
举个例子：
[3,1,4,1,5,7,2,6]
删index 1
得到
[x,x,4,x,5,7,2,6] （x代表被删除）
最终输出
[1,2,4,0,3]

删除操作：用hashmap，用一个记录走过的node。用一个array记录node往上走的路径，碰到为已删除或者是要删除的，就删除当前array里所有node。
空间跟时间都为O(n)

重新排序：开一个额外array来记录node之前跟之后的index对应

例子，删除操作后：
index:             0 1 2 3 4 5 6 7
parent Index:  x 5 4 x 1 n x x
需要返回:      1 n 3 0


-------------------------------------------------------------
ref: http://www.mitbbs.com/article_t/JobHunting/33060313.html

给一个m*n的矩阵，每个点不是0就是1，所有值为1的点是连通的，给你一个点的坐标，
告诉你这个点的值是1，求一个最小的矩形，能把所有的1包括在内
同学给了一个n logm的算法，但是面试官并不满意，想问问各位还有更优的算法吗？

寻找边界：从给定的点向四边做2分扫描，对每一行或每一列再线性扫。复杂度为O(m * lg n)或者O(m * lg k)

 -----------------------------------------------------------------
ref: http://www.mitbbs.com/article_t/JobHunting/33061095.html

没有一轮国人，过程感觉也没有很亲切，看来还是要中国人多才好。九月初的onsite，
一共五轮，四轮coding一轮系统设计（第一轮）
1. billion级别的raw data，怎样村在多个节点中，实现有效率的查找。给定条件是数
据是已经在那里的，而且不会被修改。
2. valid bst讨论属性，边界条件
3. 给一个排序的数组， 1 2 5 8 9 11 16，输出missing range比如3-4，6-7，10，
12-15
4. iterator of iterator，写一个iterator iterate所有的元素，例如
itr1 1 2 3 4
itr2 5 6 7 8
itr3 9 10 11 12
写一个iterator输出1 5 9 2 6 10 ...
5. 类似moving average，固定size不断update average，讨论多县城的情况。