google面试

1. 有这么个游戏，举个例子：给你5个空_ _ _ _ _, 每次猜一个字母，这里出题人想让你猜出来clock，假如你猜a，告诉你这里面没有。你又猜c，他把c全写出来，所以你有c _ _ c _。 让你最多猜10次。写一个程序去猜。输入是几个空，要考虑每次猜的反馈，尽量把词猜出来。
2. 坐标系第一象限上加射线，接下来所有输入的数据都是不相等的整数，不用考虑任何edge case。 想要这两个操作：1. insertX（x）， insertY（y），比如insertX， 就是现有的图上面加上x这条射线，象限会被插入的这些射线分成网格，每个格叫一个区域。 2. find（x，y）， 就是给个坐标，返回这个坐标所在的区域。可以返回区域的id，区域的id自己定。用二叉树。
题意补充解释。比如我说插入x=1, y = 1, 第一象限就被分成了4个部分。各个部分的id自己随便定，数据结构和查找方式也随便选，只要能让插入和查找这两个操作时间短就行了，关于id如果相同方格 每次查询结果都一样当然最好，我当时是没关注这点，问他忽略行吗，他说行。

3. 大整数加法，我去，还结结实实问了45分钟...
4. 1. 两个数组，问是不是permutation。 然后如果只能用constant space怎么做：quicksort。然后如果再让这两个数组是imutable，而且只能是n的复杂度，那不可能有办法给出正确答案，给出的答案可以 是错的，可以怎么做：找他们的几个次序统计量比一比，一样就说是，不一样就说不是。如果得到不是，那一定不是，如果得到是，那可能不是。
   2. 二叉树直径，用dp达到n的复杂度。


review:
1.第一题其实就是经典的游戏 hangman......wiki之..
2. 如作者所说，使用二叉树。每一个结点有一个val和range(left,right)，那么左孩子的range是(left,val)，右孩子的range是(val,right), 以此类推。
4.1. immutable O(n) memory O(n) time hashmap 搞一下
mutable O(1) memory O(nlogn) time quicksort 搞一下
immutable O(1) memory O(n) time 正确性不保证的话，用几个统计量大概看看就好，比如最大值，最小值，均值，方差，中位数之类的...
 4.2 应该说的是找两个Node之间最大距离吧，二叉树标准题，类似leetcode 中的Binary Tree Maximum Path Sum

int maxDistance(Node* root) {
        int depth = 0;
        return maxDistanceHelper(root, depth);
}

int maxDistanceHelper(Node* root, int &depth) {
        if (root == NULL) {
                depth = 0;
                return 0;
        }
        int leftDepth = 0, rightDepth = 0;
        int maxDistanceFromLeft = maxDistanceHelper(root->left, leftDepth);
        int maxDistanceFromRight = maxDistanceHelper(root->right, rightDepth);
        depth = max(leftDepth, rightDepth) + 1;
        return max(leftDepth + rightDepth + 1, max(maxDistanceFromLeft, maxDistanceFromRight));
}