google 西雅图 Onsite 在职

  1. LC原题,rob 二叉树house
  2. 旋转二叉树,有点意思。面试官很谦虚地说探讨一下:給一棵二叉树的根节点和一个叶节点。把这树上节点想象成线上挂的球。那么提起其中一个叶子节点就会变成新的二叉树。
        1
       / \
      2   3
     / \   \
    4   5   6
   / \   \
  7   8   9 

提起6:

             6
            /
           3
          /
         1
        /
       2
      / \
     4   5
    / \   \
   7   8   9 

提起9:

                 9
                /
               5
              /
             2
            / \
           4   1
          / \   \
         7   8   3
                  \
                   6

比如提起7,变成

       7
       /
      4
     / \
    8   2
       / \
      5   1
       \   \
        9   3
             \
              6

提起8:

            8
           /
          4
         / \
        7   2
           / \
          5   1
           \   \
            9   3
                 \
                  6

分有父节点指针,和没有父节点指针两种情况。

  1. 机器人走矩阵,从坐上走到右下角。矩阵中有0和1,1是障碍。有多少种方法。如果其中有一个0变1或者1变成0,怎么应对。算复杂度。

  2. 设计map reduce系统处理大数据,各种HA, checkpoint, heartbeat, communication, etc.

  3. 一个图中去除最少的edge变无环图。