Google interview questions #8

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

是烙印, 问的是LCA of DAG. 全程不让写代码, 就一直问follow up, 问复杂度, 问怎
么做, 为什么要这么做, 用那个为什么不好, 后来问要是有很多pair of nodes 求LCA
要怎么做preprocessing.

解法：

2个node各做bfs，记录走过的node和距离，如果出现重复就记录2个的距离和，直到找到最小的距离和

follow up：
预先计算出每个node到其他所有node的距离。当给定2个node时，找出所有的共同点，计算距离和

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

x_0 = C (integer)
if x_n is even then x_{n+1} is x_n / 2
if x_n is odd then x_{n+1} to be 3 * x_n + 1

这题的复杂度是O(logC)吗？

https://en.wikipedia.org/wiki/Collatz_conjecture

---------------------------------------------------------------------
ref: http://www.meetqun.com/forum.php?mod=viewthread&tid=11377&extra=page%3D1%26filter%3Dtypeid%26typeid%3D50

一队人，每一个人有两个值（height，tvalue），其中height代表身高，tvalue代表这个人前面有多少人比他高。现在把这个array of (height, tvalue)打乱，然后要还原这个数列。.

解法：

按height排序，从最低height开始，tvalue就是它在新array里的最终位置。需要注意是，每次都要对之前index前面里已经有多少被放置

最终的index = tvalue + （index之前已经确定的元素个数）

所以复杂度是O(n ^ 2)

nlogn 的解法：根据array的index建立一个bst，附带一个额外的值代表此subtree当前有多少个node被填过

-------------------------------------------------------------------------------------
ref: http://www.meetqun.com/forum.php?mod=viewthread&tid=7849&extra=page%3D1%26filter%3Dtypeid%26typeid%3D50

#1 把bst变成双向链表
解法：inorder遍历，保证一个pointer pass by reference

逆序数
解法： divide and conquer(merge sort)

#2 实现Candy Crush
1.m行n列的矩阵；2.q种花色物品；3.矩阵里每个cell的花色都是random的；4.初始化之后至少一个available的move；5.no 3-run，即初始化的时候不能直接出现三个同种物品连一线的情况。
好像还有其他几个要求，我已经记不清了。
我就开始按照他的要求挨个进行分析。先是random函数，然后就可以用双层for循环来填充每一个cell。我说但是一个available的move这个太难了，因为有太多的情况。就问他要提示，而且我不断做尝试。他说“其实答案比你想想的简单多了。最后直接告诉我：“你可以直接在填充所有的cell之前先创造一个可以move的三个物品先放进去。我恍然大悟，对对对，在双层for循环之前先做这一步操作。
下一个是"no 3-run的条件”。我说就每当在填充一个之前先往上下左右四个方向的两个格子都跟将random生成的物品进行比对。他说：“其实另一种情况。”我说：“就是将要填充的物品正好在两个同色物品之间。”他说对。我说咱们就可以用一个while循环，如果random生成的颜色不符合要求（设置一个boolean函数来判断，这里不要求实现）就继续循环。; u# V. Y: \ p7 B$ {/ a/ [: n
他说：“OK。其实这样会stuck到一种情况，你来想想。”我就想到比如比如当前方格的上、下、左、右各有一种两个同色物品排列，那么这个cell填这四种颜色的任何一种都不对了。”他说对，怎么避免呢？经过他的提示我就写这样的情况下直接清除board中所有已填颜色从头来过。0 L% F- Z) k( F
难点解决了，下一步就是写代码了，然后照相。
感觉这种题目面试官已经在里面设置好了处理的难点来等待你遇到和解决，然后看你尝试解决问题的方法以及交流能力。就像寻宝一样不断地试探、前进、解决问题。
#3 Tries

#4
比如1729 = 1^3 + 12 ^ 3 = 9 ^ 3 + 10 ^ 3。像这种可以由两对或两对以上的立方和组成的数叫做R某某某数（单词记不清了）。让你构造一个函数，输入是N，输出小于N的所有这种数。/ u" f% G( Z( |9 Q0 f- _1 H5 K
其实方法很简单，就是将从1到N的立方根之间的数，从中任取两个来求立方和，然后看结果集当中有没有出现两次或两次以上的数。就是类似于暴力了。

解法: 暴力 + hash，从1开始算到N

----------------------------------------------------------
ref: http://www.meetqun.com/forum.php?mod=viewthread&tid=11067&extra=page%3D1%26filter%3Dtypeid%26typeid%3D50

Google onsite
1. 类似这道题：
给如下的数据格式：<start_time, end_time, value>
For example,
1, 3, 100
2, 4, 200
5, 6, 300
。。。
这些数据时间点可能有重合。在时间段2~3之间，value的和是100+200 = 300. 找出这
组数据中最高的value和
[consider end points]

解法：类似meeting room，把开始、结束时间排序，设2个指针p1, p2。
如果是开始时间，cur + value[p1++], 结束时间cur - value[p2++]

2.find k most frequent words from a file
解法：priority queue + hash map

3.brainstorming: 一个上传文件的service，之前正常运转，突然有一天挂了，这期间
没改代码。问怎么排查问题。

查log，物理硬件

-------------------------------------------------------------------------------
ref： http://www.meetqun.com/forum.php?mod=viewthread&tid=301&extra=page%3D1%26filter%3Dtypeid%26typeid%3D50&page=6

check一个数是否是3的次幂

解法：http://stackoverflow.com/questions/1804311/how-to-check-if-an-integer-is-power-of-3

遍历

查表，32位内3的幂也就几十位

2分

---------------------------------------------------------------------------------
ref: http://www.geeksforgeeks.org/dynamic-programming-set-18-word-wrap/
word wrap

解法：
标准dp

 int cube(int num) {
 return  num * num * num;
}

int minCost(vector<int> &v,vector<int> &dp,int index, int width) {
 if (index == v.size()) return 0;
 if (dp[index] != INT_MAX) return dp[index];
 int len = v[index];
 int minC = INT_MAX;
 for (int i = index; i < v.size(); i++) {
  minC = min(minC, cube(width - len) + minCost(v,dp,i + 1,width));
  len += v[i] + 1;
  if (width < len) break;
 }
 dp[index] = minC;
 return minC;
}

int spawn(vector<int> &v, int width) {
 vector<int> dp(v.size(),INT_MAX);
 return minCost(v,dp,0,width);
}

---------------------------------------
round 1: 给定一个class
class Event {
int id; /nsor id
int timestamp;
boolean status;
}
意思是某个sensor会触发一个事件使其状态status改变，true->false or false->true. 设计数据结构，存储以下信息：每个事件的sensor id, timestamp和status，使其可以响应一种query， query包含id, timestamp,返回这个id在这个时刻的status
follow up: 如果来的event不是按照timestamp递增的，怎么修改数据结构

round 2:
一个二维矩阵，里面是bits (1 or 0)，可以用int 或byte表示，左右翻转这个矩阵，有什么优化

round 3:
一个猜词游戏，给定一个词典，里面的词的长度都一样，有一个secret word在这个词典里，每次从词典里选一个词猜，只会返回和secret word有几个字母是一样的（只知道数量，不知道位置）。问怎样猜能尽量减少猜测次数