一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

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

Google Intern SDE 面经

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

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

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
发面经攒攒rp,solution见白字. 1point3acres.com/bbs

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给定时就有序,如何做的更快?
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的操作支持啥?时间复杂度?.鏈枃鍘熷垱鑷1point3acres璁哄潧
Problem 1.5: 现在要增加这样子的一个操作:给定一个x,找出与x差值最小的element
这是个经典问题
Problem 2:

有一种Tree,满足下面的propoerty:
. 鍥磋鎴戜滑@1point 3 acres

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

. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
让你写出如下操作:
1、求最小值
Trivial,就是根
2、给定两棵这种Tree,将他们合并成一个仍满足上面几个property的Tree. 1point 3acres 璁哄潧
Node * merge(Node * a, Node * b)
{. 1point3acres.com/bbs
  if (a == NULL)
    return b;
  if (b == NULL)
    return a;. From 1point 3acres bbs
  if (a->key > b->key) //保证a的根是最小的
    swap(a, b);
  a->left = merge(a->left, b);. from: 1point3acres.com/bbs
  a->size += b->size;
}
3、2里面的代码时间复杂度?
O(height of a + height of b). 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
4、Can be do better?
Node * merge(Node * a, Node * b). 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
{
  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;
}. 鍥磋鎴戜滑@1point 3 acres

5、4中时间复杂度?. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
感觉是O(logn)的。估计面试官也不会


实际上,这个东西是一个经典的数据结构,叫做左偏树,英文叫做Leftist Tree,只不过高度平衡换成了size平衡。


.鐣欏璁哄潧-涓浜-涓夊垎鍦

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


Interview 3: 40min 今年年初的onsite. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
Problem 1: 给定一个只有小写字母的字符串,问有多少连续子序列(子串)中每个字符不重复出现
双指针扫描,开个数组纪录当前每个字符有没有出现过。O(n)
Problem 2:
A->1, B->2, ..., Z->26
AA->27, AB-> 28, ... AZ->52. from: 1point3acres.com/bbs
.... from: 1point3acres.com/bbs


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


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,让我明年再来


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

补充内容 (2015-11-24 09:36):. from: 1point3acres.com/bbs
a + a[j]. 1point 3acres 璁哄潧

补充内容 (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
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 | 显示全部楼层
多谢楼主! 答案显示方法好评~
求职神器indeed - 在全球最大的求职网站找找适合你的工作?
回复 支持 反对

使用道具 举报

虾米酱 发表于 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大的最小的和 ...

嗯这是我一开始的做法.鏈枃鍘熷垱鑷1point3acres璁哄潧
后来面试官希望写一个一趟就完成的
回复 支持 反对

使用道具 举报

 楼主| QDkAc 发表于 2015-11-24 22:04:16 | 显示全部楼层
bingo1995 发表于 2015-11-24 21:33
咦   你在北京面Intern是啥。。暑期的还是平时的?还是说是为来美国之后的实习面试的?

暑假的。三月面的,当时去美帝已经来不及了。
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

 楼主| QDkAc 发表于 2015-11-25 01:04:40 | 显示全部楼层
虾米酱 发表于 2015-11-24 23:54
一趟完成应该怎么做呀,感谢!
-google 1point3acres
Node * search(Node * root, int val). 1point 3acres 璁哄潧
{
  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
.鏈枃鍘熷垱鑷1point3acres璁哄潧     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;
  }
}

编辑框里随手打的 有错误见谅
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

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

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2017-3-29 19:50

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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