Google 电面

刚结束的Google电面
小哥准时打电话过来,和我聊七八分钟的天,说他们组是做infrastructure和推荐系统的,听口音应该是中国人,而且我和他唠电商的时候,他说出了淘宝和京东的名字······
后面开始做题,小哥一句 So are u ready? 瞬间出戏,感觉像是什么游戏开始的讯号“谷歌大冒险吗”···
第一道题,给一个二叉树,存的是int,找到全局里面祖先节点和他孩子节点的差值的最大值。我说用dfs访问每一个节点作为根节点,然后再对每一个根节点做dfs访问他所有孩子节点,更新全局的maxDiff。然后他让我推了下时间复杂度,我说最好的情况,如果是balanced tree那就是O(nlogn),如果最坏的情况退化成单链表,那就是O(n^2)。他说可以,你实现一下吧。写了之后,他让我跑了两个test case,然后说Let’'s move forward to second problem。
第二道题,有一个字符串的Google pattern “google”,每一个字符可以重复多次或者不出现,比如ggggoogle,googlllle,l,但是相对顺序不能改变,考虑所有的input string都是valid,问里面有多少个l。
一开始没有理解清楚题目意思,我问是不是要先判断input是否valid,他给我说不用,全部都是valid,我说那我的直觉就是扫一遍,然后数有多少个,然后问了时空复杂度,问可以更好吗,问到这儿我差不多明白他是想让我二分了··· 我说那可以二分,用两次二分找到第一个l出现的位置和最后一个l出现的位置,然后相减。他说可以,你写一下呗。写了,一边写一边给他说啥意思,然后他给了我6,7个test case说你跑一下,都跑过以后,他问你有什么想问我的吗··· 就又唠了一下。

第一题能不能这样,dfs的时候加两个parameter,正在访问的node的祖先的maxValue和minValue,计算现在node的值与maxValue和minValue的差值,更新maxDiff,因为最大差值一定是和祖先的最大值或最小值的差。
这样dfs访问每个节点只要O(n)

二分取了mid之后你也不知道l在前面还是后面啊?还是说一开始就知道没有重复的词什么样?

哦 有pattern在前面
要不要先建一个字母对应位置的map方便查?

第一题递归函数遍历左右node 返回最大最小值 然后和root比一下求差
再搞个global参数存全局最大

相对顺序不能改变 怎么保存他们的顺序啊 谢谢楼主~ ~

第一题O(n)可以吧

对的对的,当时他问我有没有更好的思路,我说这个说到一半,说要保存max和min,但没想到最大差值一定是和祖先的最大值或最小值的差这一点,后面就还是照着第一种写了,感谢。

对的 就是一楼的思路

顺序不用存啊,就只要知道’‘l’‘前面的只可能是goog,’‘l’'后面的只可能是e就可以二分了啊

第一题的code感觉楼上不太对请指正:

class Solution {
  private int maxDiff;
  public int maxDiff(TreeNode root) {
   maxDiff = Integer.MIN_VALUE;
   helper(root);
    return maxDiff;
  }

  private int helper(TreeNode root) {
   int left = Integer.MAX_VALUE;
   int right = Integer.MAX_VALUE;
   if (root.left != null)
    left = helper(root.left);
   if (root.right != null)
    right = helper(root.right);
   int min = Math.min(left, right);
   maxDiff = Math.max(maxDiff, root.val - min);
   return Math.min(min, root.val);
  }
}