Google Intern SDE 面经

发面经攒攒rp，solution见白字

Interview 1: 40min，大概在10月的电话面
Problem 1: 给定一个int[] a, 一个x，问有多少pair (i, j) 满足 a[i] + a[j] <= x
Solution: 排序，枚举i，二分j，O(nlogn)
Problem 1.5: 若a给定时就有序，如何做的更快？
j的范围随着i的移动单调，双指针扫描。O(N)
Problem 2: 给定一个int[] a, 一个x，问有多少长度为k的tuple(i_1, i_2, .., i_k),满足a[i_1] + a[i_2] + ... + a[i_k] <= x
DFS即可，O(n^k)


这次感觉题目整体比较简单


Interview 2: 40min，与Interview 1同一天
Problem 1: BST的操作支持啥？时间复杂度？
Problem 1.5: 现在要增加这样子的一个操作：给定一个x，找出与x差值最小的element
这是个经典问题
Problem 2:

有一种Tree，满足下面的propoerty：


1、节点上的key满足heap的性质，小根堆
2、每个节点上记录这个节点所在子树节点数量，用size表示
3、每个节点左子树的size>=右子树的size


让你写出如下操作

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

color="#000000">Problem 1: 一个n*m方格图，有一个位置被下雨了，问最终能从哪些边界处的格子流出水
BFS
Problem 2: RMQ问题
有各种各样的方法，我说了O(N)预处理每次O(1)回答的
Problem 2.5: 实践中可能有什么优化？
Cache？其他的不知道了
Interview 3、4是今年年初面的Beijing intern。最终被告知没有Headcount，让我明年再来


补充内容 (2015-11-24 09:36):
Problem 1: 给定一个int[] a, 一个x，问有多少pair (i, j) 满足 a[i] + a[j] <= x
上面显示有问题

补充内容 (2015-11-24 09:36):
a[i] + a[j]

补充内容 (2015-11-24 09:36):
a#[i] + a[j]

补充内容 (2015-11-24 09:37):
啊啊啊啊啊无语了啊。。是a数组的第i项＋a数组的第j项

QDkAc 发表于 2015-11-25 01:04
Node * search(Node * root, int val)
{
  if (root == NULL)

好机智，感谢！

虾米酱 发表于 2015-11-24 23:54
一趟完成应该怎么做呀，感谢！

Node * search(Node * root, int val)
{
  if (root == NULL)
    return root;
  if (root->val == val)
    return root;
  else if (root->val < val){
    Node * temp = search(root->right, val);
    if (temp == NULL || abs(root->val - val) < abs(temp->val - val))
     return root;
   else
     return temp;
  }
  else{
    Node * temp = search(root->left, val);
    if (temp == NULL || abs(root->val - val) < abs(temp->val - val))
      return root;
    else
      return temp;
  }
}

编辑框里随手打的 有错误见谅

谢谢楼主，不过楼主，合并两棵树，使其满足左偏堆的性质的核心优化部分。
也就是这里：
if (a->right->size > a->left->size) //核心优化
需要判断a的左节点是否为空，也就是少了一个判断，在叶子节点时候merge就会出问题了，任何一个test case都可以测出来，可能google不需要完全bug free的代码吧！

妈呀根本没有人看吗？

看到了，谢谢楼主！！

多谢楼主！ 答案显示方法好评～

Problem 1.5: 现在要增加这样子的一个操作：给定一个x，找出与x差值最小的element是分别找比x大的最小的和比x小的最大的么

咦   你在北京面Intern是啥。。暑期的还是平时的？还是说是为来美国之后的实习面试的？

虾米酱 发表于 2015-11-24 21:03
Problem 1.5: 现在要增加这样子的一个操作：给定一个x，找出与x差值最小的element是分别找比x大的最小的和 ...

嗯这是我一开始的做法
后来面试官希望写一个一趟就完成的

bingo1995 发表于 2015-11-24 21:33
咦   你在北京面Intern是啥。。暑期的还是平时的？还是说是为来美国之后的实习面试的？

暑假的。三月面的，当时去美帝已经来不及了。

QDkAc 发表于 2015-11-24 22:03
嗯这是我一开始的做法
后来面试官希望写一个一趟就完成的

一趟完成应该怎么做呀，感谢！