一亩三分地论坛

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

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

Google 面经,已挂

[复制链接] |试试Instant~ |关注本帖
游冥客 发表于 2015-8-26 10:38:16 | 显示全部楼层 |阅读模式

2015(7-9月) 码农类 硕士 全职@Google - 内推 - Onsite |Failfresh grad应届毕业生

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

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

x
国内软工硕士,找师姐内推的Google,挂了

电面:
国人,直接中文面的
1. 找两个数组的差集
比如 A = [1,1,1,2,2,2], B= [2,2,3],在A中出现,B中不出现的集合是 [1,1,1,2],反过来 B中出现,A中不出现的集合是 [3]
面试官强调了好几遍有重复元素~~ 用hash表做的. 1point 3acres 璁哄潧
. 1point3acres.com/bbs
. from: 1point3acres.com/bbs
2. 求一个域名下面所有的unique的url的数目,直接用bfs去做的


Onsite:
第一轮: 国人大叔
英文自我介绍了一下,然后大叔说英文还可以,咱用中文吧
一队人打散后,每个人有一个高度,每个人记得原来前面有几个人比他高,没有重复高度,求复原原始队列
愣了半天,面试官很nice的给了hint,其实是很水的题。。。然后讨论了时间复杂度,问问题

第二轮:国人阿姨,有shadow
做了一个morse code的题,每个字符编码里面都没有空格,只用 . 和 - 表示,所以是有二义性的
1. 给一个字符串,输出morse code. 1point3acres.com/bbs
2. 给一个文件,里面每行都是一个串,求重复的morse code数。中间被指出一个bug。。。
3. 给一个morse code串,输出所有的解码结果,暴力解的。。。问复杂度的时候还求错了 TT

第三轮:国人大叔. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
这一轮面的很差。。。唉
1. 给一堆字符串,serialize成一个字符串,然后deserialize回来
2. 压缩颜色  #aabbcc 可以压缩成#abc颜色 #abcdef 和 #ghijkl 距离为 (ab-gh)^2 + (cd - ij)^2 + (ef - kl)^2
    压缩颜色使得距离最小,比如 #123456 => #135

第四轮:印度小哥
印度小哥。。不怎么鸟你,可能听不懂我说话,一直让我写代码,求复杂度
1. 两个string 的 list,找出只在某一个list里出现的string
follow up:扩展到k个list呢?

2. good number, 如果一个数 a 是两组不同的两个三次方的和(a = b^3 + c^3 = d^3 + e^3),这个数就good number,
求 [1, n] 里面所有的 good number

唉,已跪,求rp,求北美收留

评分

5

查看全部评分

本帖被以下淘专辑推荐:

 楼主| 游冥客 发表于 2015-8-28 22:10:47 | 显示全部楼层
sosisarah 发表于 2015-8-28 15:07
找两个数组的差集, 可以线性扫描的. O(m+n).

第一轮国人大叔的那个题目, 如果原始身高是 1 2 3 4 5, 那 ...
. 1point 3acres 璁哄潧
线性扫描是不是得是有序的才行呢

先找最矮的,前面有几个比他高就放到第几个位置上去,然后第二矮的,然后第三矮的。。。

你这个例子,就直接一个一个放就可以了
回复 支持 1 反对 0

使用道具 举报

 楼主| 游冥客 发表于 2015-9-4 00:33:17 | 显示全部楼层
say543 发表于 2015-9-3 12:16
thanks LZ 能够说说怎么做吗? 没有想到什么好方法....

16进制 11 和 22 之间差了17

转成10进制,然后转化成17的倍数
回复 支持 1 反对 0

使用道具 举报

sosisarah 发表于 2015-8-28 15:07:06 | 显示全部楼层
找两个数组的差集, 可以线性扫描的. O(m+n).

第一轮国人大叔的那个题目, 如果原始身高是 1 2 3 4 5, 那么比他高的序列是 0 0 0 0 0. 这个怎么办?
回复 支持 1 反对 0

使用道具 举报

 楼主| 游冥客 发表于 2015-8-26 12:38:43 | 显示全部楼层
jiebour 发表于 2015-8-26 12:11
unique  url这个题需要代码嘛楼主?

要写代码 提供了解析一个url页面里面所有url的api
回复 支持 1 反对 0

使用道具 举报

yangyiming 发表于 2015-8-26 11:49:08 | 显示全部楼层
请问下电面第二题到底什么意思?问题的难点在于?
回复 支持 反对

使用道具 举报

 楼主| 游冥客 发表于 2015-8-26 11:51:46 | 显示全部楼层
yangyiming 发表于 2015-8-26 11:49
请问下电面第二题到底什么意思?问题的难点在于?
. visit 1point3acres.com for more.
就是类似爬虫,输入一个域名,求所有能爬到的链接数量,难点嘛,去重?
回复 支持 反对

使用道具 举报

jiebour 发表于 2015-8-26 12:11:11 | 显示全部楼层
unique  url这个题需要代码嘛楼主?.1point3acres缃
回复 支持 反对

使用道具 举报

可乐杀手 发表于 2015-8-26 12:22:31 | 显示全部楼层
jiebour 发表于 2015-8-26 12:11
unique  url这个题需要代码嘛楼主?

能发我一份吗? yechi.zhang@ucla.edu 谢谢!
回复 支持 反对

使用道具 举报

hulahu 发表于 2015-8-26 13:51:33 | 显示全部楼层
好多都不会做哦
回复 支持 反对

使用道具 举报

hulahu 发表于 2015-8-26 13:53:04 | 显示全部楼层
电面一, 是用两hash表吗?
电面二, 可不可以把代码贴给偶们看看
回复 支持 反对

使用道具 举报

jiebour 发表于 2015-8-26 14:16:19 | 显示全部楼层
楼主,第一题真没看懂哎。。。。.鐣欏璁哄潧-涓浜-涓夊垎鍦
比如 A = [1,1,1,2,2,2], B= [2,2,3],在A中出现,B中不出现的集合是 [1,1,1,2],反过来 B中出现,A中不出现的集合是 [3]
为啥是【1,1,1,2】????
回复 支持 反对

使用道具 举报

 楼主| 游冥客 发表于 2015-8-26 16:04:00 | 显示全部楼层
jiebour 发表于 2015-8-26 14:16
楼主,第一题真没看懂哎。。。。
比如 A = [1,1,1,2,2,2], B= [2,2,3],在A中出现,B中不出现的集合是 [1, ...

就是说要统计次数啦
回复 支持 反对

使用道具 举报

 楼主| 游冥客 发表于 2015-8-26 16:11:32 | 显示全部楼层
hulahu 发表于 2015-8-26 13:53-google 1point3acres
电面一, 是用两hash表吗?
. visit 1point3acres.com for more.电面二, 可不可以把代码贴给偶们看看

我是用两个hash做的,面试官也没说啥

第二题,大概就是这个样子
  1. int count(string url) {
  2.     unordered_set<string> visited;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  3.     queue<string> urlQueue;
  4.     process.push(url);
  5.     while (!urlQueue.empty()) {
  6.         auto toProcess = urlQueue.front();
  7.         urlQueue.pop();.鏈枃鍘熷垱鑷1point3acres璁哄潧
  8.         visited.insert(toProcess);
  9.     <span style="line-height: 1.5;">   </span><span style="line-height: 1.5;"> </span><span style="line-height: 1.5;">for (auto next: extract(toProcess)) {</span>
复制代码
回复 支持 反对

使用道具 举报

 楼主| 游冥客 发表于 2015-8-26 16:14:16 | 显示全部楼层
游冥客 发表于 2015-8-26 16:11.1point3acres缃
我是用两个hash做的,面试官也没说啥

第二题,大概就是这个样子
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
电面二:
  1. int count(string url) {
  2.     unordered_set<string> visited;
  3.     queue<string> urlQueue;
  4.     process.push(url);.鐣欏璁哄潧-涓浜-涓夊垎鍦
  5.     while (!urlQueue.empty()) {
  6.         auto toProcess = urlQueue.front();
  7.         urlQueue.pop();
  8.         visited.insert(toProcess);
  9.         for (auto next: extract(toProcess)) {
  10.             if (visited.find(next) != visited.end()) {
  11.                 // exists
  12.                 continue;
  13.             }
  14.             urlQueue.push(next);
  15.         }
  16.     }. 鍥磋鎴戜滑@1point 3 acres
  17.     return visited.size();
  18. }
复制代码
回复 支持 反对

使用道具 举报

wenqiang88 发表于 2015-8-26 20:25:35 | 显示全部楼层
请问为啥#123456 => #135?
回复 支持 反对

使用道具 举报

alittlesheep 发表于 2015-8-26 21:03:16 | 显示全部楼层
wenqiang88 发表于 2015-8-26 20:25.鐣欏璁哄潧-涓浜-涓夊垎鍦
请问为啥#123456 => #135?

应该是css里面的十六进制颜色表示法的压缩
这是stackoverflow上的吐槽:.1point3acres缃
http://stackoverflow.com/questio ... -color-codes-in-css-google 1point3acres

0x123456 => 0x113355 => 0x135

(0x12-0x11)^2 +(0x34-0x33)^2+ (0x56-0x55)^2 是最小的近似颜色压缩
回复 支持 反对

使用道具 举报

hulahu 发表于 2015-8-26 22:31:19 | 显示全部楼层
游冥客 发表于 2015-8-26 16:14
. from: 1point3acres.com/bbs 电面二:

Thanks a lot.
回复 支持 反对

使用道具 举报

wb7 发表于 2015-8-28 00:54:33 | 显示全部楼层
题主 第一题可以详细解释下么…

没太看明白要求,也不太清楚解法. 鍥磋鎴戜滑@1point 3 acres

谢谢了…
回复 支持 反对

使用道具 举报

 楼主| 游冥客 发表于 2015-8-28 22:06:25 | 显示全部楼层
wb7 发表于 2015-8-28 00:54
题主 第一题可以详细解释下么…

没太看明白要求,也不太清楚解法

哪个题?
回复 支持 反对

使用道具 举报

wb7 发表于 2015-8-29 04:27:25 | 显示全部楼层

每个人知道前面有几个人比他高那个…没太看懂…

. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴谢谢题主了…
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-10 01:30

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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