一亩三分地论坛

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

扫码关注一亩三分地公众号
查看: 1968|回复: 10
收起左侧

Google Intern SDE 面经

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

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

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

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

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

有一种Tree,满足下面的propoerty:

. Waral 鍗氬鏈夋洿澶氭枃绔,
1、节点上的key满足heap的性质,小根堆. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
2、每个节点上记录这个节点所在子树节点数量,用size表示
3、每个节点左子树的size>=右子树的size. Waral 鍗氬鏈夋洿澶氭枃绔,

. 鍥磋鎴戜滑@1point 3 acres
让你写出如下操作:
1、求最小值
Trivial,就是根
2、给定两棵这种Tree,将他们合并成一个仍满足上面几个property的Tree
Node * merge(Node * a, Node * b)
{
  if (a == NULL)
    return b;
  if (b == NULL)
    return a;.1point3acres缃
  if (a->key > b->key) //保证a的根是最小的
    swap(a, b);. Waral 鍗氬鏈夋洿澶氭枃绔,
  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)
{
  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)的。估计面试官也不会


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


. visit 1point3acres.com for more.

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


Interview 3: 40min 今年年初的onsite
Problem 1: 给定一个只有小写字母的字符串,问有多少连续子序列(子串)中每个字符不重复出现. From 1point 3acres bbs
双指针扫描,开个数组纪录当前每个字符有没有出现过。O(n)
Problem 2:
A->1, B->2, ..., Z->26.1point3acres缃
AA->27, AB-> 28, ... AZ->52 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
.... From 1point 3acres bbs
. 1point3acres.com/bbs
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
写一个这种的转换器(类似于Excel的列号). From 1point 3acres bbs
类似于进制转换
Problem 3:
给定黑白棋的一个Scenario,问当前黑方可以在那些位置放棋子
沿着上下左右两条对角线分别扫描一下。O(棋盘大小)


Interview 4: 与3是一起的
Problem 1: 一个n*m方格图,有一个位置被下雨了,问最终能从哪些边界处的格子流出水
BFS. 1point3acres.com/bbs
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):
a + a[j]
. from: 1point3acres.com/bbs
补充内容 (2015-11-24 09:36):
a# + a[j]
. 1point3acres.com/bbs
补充内容 (2015-11-24 09:37):. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
啊啊啊啊啊无语了啊。。是a数组的第i项+a数组的第j项

评分

6

查看全部评分

 楼主| QDkAc 发表于 2015-11-24 12:28:51 | 显示全部楼层
妈呀根本没有人看吗?
回复 支持 反对

使用道具 举报

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
. from: 1point3acres.com/bbs 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. 1point3acres.com/bbs
嗯这是我一开始的做法
后来面试官希望写一个一趟就完成的

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

使用道具 举报

 楼主| 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){. 1point3acres.com/bbs
    Node * temp = search(root->right, val);
    if (temp == NULL || abs(root->val - val) < abs(temp->val - val))
     return root;
   else. 1point3acres.com/bbs
     return temp;
  }
  else{
    Node * temp = search(root->left, val);
    if (temp == NULL || abs(root->val - val) < abs(temp->val - val))
      return root;
    else. 1point 3acres 璁哄潧
      return temp;
  }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
}

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

使用道具 举报

虾米酱 发表于 2015-11-25 02:40:37 | 显示全部楼层
QDkAc 发表于 2015-11-25 01:04
Node * search(Node * root, int val). 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
{. from: 1point3acres.com/bbs
  if (root == NULL)

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

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2017-1-19 16:50

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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