推荐:数据科学课程和书籍清单以及培训讲座


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 4534|回复: 11
收起左侧

Google Intern SDE 面经

[复制链接] |试试Instant~ |关注本帖
QDkAc 发表于 2015-11-24 09:32:15 | 显示全部楼层 |阅读模式

2015(1-3月) 码农类 本科 实习@Google - 内推 - 技术电面 Onsite |Passfresh grad应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

x
发面经攒攒rp,solution见白字

Interview 1: 40min,大概在10月的电话面
Problem 1: 给定一个int[] a, 一个x,问有多少pair (i, j) 满足 a + a[j] <= x
Solution: 排序,枚举i,二分j,O(nlogn)
Problem 1.5: 若a给定时就有序,如何做的更快?.鏈枃鍘熷垱鑷1point3acres璁哄潧
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
. 1point 3acres 璁哄潧

让你写出如下操作:.鏈枃鍘熷垱鑷1point3acres璁哄潧
1、求最小值
Trivial,就是根
2、给定两棵这种Tree,将他们合并成一个仍满足上面几个property的Tree
Node * merge(Node * a, Node * b)
{
  if (a == NULL)
    return b;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  if (b == NULL). Waral 鍗氬鏈夋洿澶氭枃绔,
    return a;
  if (a->key > b->key) //保证a的根是最小的. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
    swap(a, b);. from: 1point3acres.com/bbs
  a->left = merge(a->left, b);
  a->size += b->size;
}
3、2里面的代码时间复杂度? 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
O(height of a + height of b)
4、Can be do better?
Node * merge(Node * a, Node * b). visit 1point3acres.com for more.
{
  if (a == NULL)
    return b;
  if (b == NULL)
    return a;
  if (a->key > b->key) //保证a的根是最小的
    swap(a, b);
  a->right = merge(a->right, b); //Caution!
  if (a->right->size > a->left->size) //核心优化
    swap(a->left, a->right);
  a->size += b->size;
}

5、4中时间复杂度?
感觉是O(logn)的。估计面试官也不会. 鍥磋鎴戜滑@1point 3 acres
.鏈枃鍘熷垱鑷1point3acres璁哄潧

实际上,这个东西是一个经典的数据结构,叫做左偏树,英文叫做Leftist Tree,只不过高度平衡换成了size平衡。
.鏈枃鍘熷垱鑷1point3acres璁哄潧



Interiview 1, 2是面的明年summer MTV的intern,最终过了HC


Interview 3: 40min 今年年初的onsite. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
Problem 1: 给定一个只有小写字母的字符串,问有多少连续子序列(子串)中每个字符不重复出现-google 1point3acres
双指针扫描,开个数组纪录当前每个字符有没有出现过。O(n)
Problem 2: . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
A->1, B->2, ..., Z->26. 1point 3acres 璁哄潧
AA->27, AB-> 28, ... AZ->52
. from: 1point3acres.com/bbs ...


写一个这种的转换器(类似于Excel的列号)
类似于进制转换
Problem 3:
给定黑白棋的一个Scenario,问当前黑方可以在那些位置放棋子
沿着上下左右两条对角线分别扫描一下。O(棋盘大小). more info on 1point3acres.com


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


补充内容 (2015-11-24 09:36):
Problem 1: 给定一个int[] a, 一个x,问有多少pair (i, j) 满足 a + a[j] <= x. visit 1point3acres.com for more.
上面显示有问题
. From 1point 3acres bbs
补充内容 (2015-11-24 09:36):-google 1point3acres
a + a[j]

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

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

评分

6

查看全部评分

虾米酱 发表于 2015-11-25 02:40:37 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
QDkAc 发表于 2015-11-25 01:04. 1point3acres.com/bbs
Node * search(Node * root, int val). 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
{
  if (root == NULL)

好机智,感谢!
回复 支持 0 反对 1

使用道具 举报

 楼主| QDkAc 发表于 2015-11-24 12:28:51 | 显示全部楼层
关注一亩三分地微博:
Warald
妈呀根本没有人看吗?
回复 支持 反对

使用道具 举报

echo33 发表于 2015-11-24 13:24:27 | 显示全部楼层
看到了,谢谢楼主!!
回复 支持 反对

使用道具 举报

bearcat001 发表于 2015-11-24 13:50:59 | 显示全部楼层
多谢楼主! 答案显示方法好评~
回复 支持 反对

使用道具 举报

虾米酱 发表于 2015-11-24 21:03:48 | 显示全部楼层
Problem 1.5: 现在要增加这样子的一个操作:给定一个x,找出与x差值最小的element是分别找比x大的最小的和比x小的最大的么
回复 支持 反对

使用道具 举报

bingo1995 发表于 2015-11-24 21:33:09 | 显示全部楼层
咦   你在北京面Intern是啥。。暑期的还是平时的?还是说是为来美国之后的实习面试的?
回复 支持 反对

使用道具 举报

 楼主| QDkAc 发表于 2015-11-24 22:03:48 | 显示全部楼层
虾米酱 发表于 2015-11-24 21:03
Problem 1.5: 现在要增加这样子的一个操作:给定一个x,找出与x差值最小的element是分别找比x大的最小的和 ...

嗯这是我一开始的做法
后来面试官希望写一个一趟就完成的
回复 支持 反对

使用道具 举报

 楼主| QDkAc 发表于 2015-11-24 22:04:16 | 显示全部楼层
bingo1995 发表于 2015-11-24 21:33
咦   你在北京面Intern是啥。。暑期的还是平时的?还是说是为来美国之后的实习面试的?
. 1point3acres.com/bbs
暑假的。三月面的,当时去美帝已经来不及了。
回复 支持 反对

使用道具 举报

虾米酱 发表于 2015-11-24 23:54:53 | 显示全部楼层
QDkAc 发表于 2015-11-24 22:03
嗯这是我一开始的做法
后来面试官希望写一个一趟就完成的

一趟完成应该怎么做呀,感谢!
回复 支持 反对

使用道具 举报

 楼主| QDkAc 发表于 2015-11-25 01:04:40 | 显示全部楼层
虾米酱 发表于 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{. from: 1point3acres.com/bbs
    Node * temp = search(root->left, val);. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
    if (temp == NULL || abs(root->val - val) < abs(temp->val - val)). 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
      return root;
    else 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
      return temp;
  }
}
.鐣欏璁哄潧-涓浜-涓夊垎鍦
编辑框里随手打的 有错误见谅
回复 支持 反对

使用道具 举报

NathanYan2018 发表于 2017-4-24 02:34:09 | 显示全部楼层
谢谢楼主~. 鍥磋鎴戜滑@1point 3 acres
回复 支持 反对

使用道具 举报

本版积分规则

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-7-28 08:50

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表