一亩三分地论坛

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

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

Google 实习面经

[复制链接] |试试Instant~ |关注本帖
隐隐野烟 发表于 2016-1-3 10:38:47 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 实习@Google - 内推 - 技术电面 |Other其他

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

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

x
给一个Array,return XOR值最大的两个数。面试官人很nice,已经延长时间,但楼主仍阵亡。

评分

4

查看全部评分

 楼主| 隐隐野烟 发表于 2016-1-3 12:46:44 | 显示全部楼层
trie + bit manipulation 可以解决,但面时候没有码完,当时trie没问题,但位操作太不熟练。
回复 支持 1 反对 0

使用道具 举报

小柯西 发表于 2016-1-3 12:10:30 | 显示全部楼层
考官对时间复杂度有要求嘛??
回复 支持 反对

使用道具 举报

kinggarden2001 发表于 2016-1-3 12:25:07 | 显示全部楼层
要考虑负数吗?
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-1-3 12:25:11 | 显示全部楼层
lz是先面完一个 再约第2个面试?. 鍥磋鎴戜滑@1point 3 acres
为什么我是连着2个呢。。back to back。。
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-1-3 12:29:46 | 显示全部楼层
感觉,如果不知道optimal solution的话。
可不可以直接给暴力解,组成所有两个pair,然后直接看哪个pair的xor最大?
回复 支持 反对

使用道具 举报

kinggarden2001 发表于 2016-1-3 12:31:57 | 显示全部楼层
暴力估计不是面试官想要的
回复 支持 反对

使用道具 举报

kinggarden2001 发表于 2016-1-3 12:38:19 | 显示全部楼层
想到一个解法,暂时不考虑负数。搞一个map track 最高位到最低位那位为一的数的的index 然后从最高位开始greedy 目的是尽量保留住高位的 1。复杂度是线性。大家觉得如何?
回复 支持 反对

使用道具 举报

 楼主| 隐隐野烟 发表于 2016-1-3 12:44:03 | 显示全部楼层
我是加面,经过和面试官讨论,想到用trie做才能达到nlogn(思路:http://stackoverflow.com/questions/9320109/two-elements-in-array-whose-xor-is-maximum)题目不考虑负数。楼主完整刷过LeetCode + 所有地里intern面经,本来刷别人的面经刷的挺自信。但经过此面,证明自己还是实力还是不到家,继续努力。
回复 支持 反对

使用道具 举报

 楼主| 隐隐野烟 发表于 2016-1-3 12:50:16 | 显示全部楼层
kinggarden2001 发表于 2016-1-3 12:38
想到一个解法,暂时不考虑负数。搞一个map track 最高位到最低位那位为一的数的的index 然后从最高位开始gr ...

怎么都到不了线性的。
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-1-3 12:51:59 | 显示全部楼层
隐隐野烟 发表于 2016-1-3 12:44
我是加面,经过和面试官讨论,想到用trie做才能达到nlogn(思路:http://stackoverflow.com/questions/9320 ...

电面的时候,可以到网上找参考答案么?
面试官会发现么
回复 支持 反对

使用道具 举报

 楼主| 隐隐野烟 发表于 2016-1-3 12:55:07 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-1-3 12:51.鏈枃鍘熷垱鑷1point3acres璁哄潧
电面的时候,可以到网上找参考答案么?.1point3acres缃
面试官会发现么

理论上可以,我没干过。。链接是面试后才找到的,我和他的思路一致。
但是之前看Amazon的面经,有人偷偷google题目,但是面试官是阿三,听到键盘声,直接就问你在干什么。
然后,那位仁兄跪了。。
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-1-3 13:02:24 | 显示全部楼层
隐隐野烟 发表于 2016-1-3 12:55. 鍥磋鎴戜滑@1point 3 acres
理论上可以,我没干过。。链接是面试后才找到的,我和他的思路一致。
但是之前看Amazon的面经,有人偷偷 ...

说在电脑上写思路?
回复 支持 反对

使用道具 举报

kinggarden2001 发表于 2016-1-3 13:11:05 | 显示全部楼层
谢谢 没想的那么细。 这题比较难,楼主运气不好。
回复 支持 反对

使用道具 举报

 楼主| 隐隐野烟 发表于 2016-1-3 13:15:07 | 显示全部楼层
kinggarden2001 发表于 2016-1-3 13:11
谢谢 没想的那么细。 这题比较难,楼主运气不好。

祝你好运,一般intern面不会很难,身边的小伙伴已顺利拿offer。
回复 支持 反对

使用道具 举报

 楼主| 隐隐野烟 发表于 2016-1-3 13:16:57 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-1-3 13:02
说在电脑上写思路?

没理解你的问题。我的建议是,除非忘记数据结构,或者实在没思路。一般情况不要偷偷搜索,多和面试官沟通。
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-1-3 13:23:15 | 显示全部楼层
隐隐野烟 发表于 2016-1-3 13:15
祝你好运,一般intern面不会很难,身边的小伙伴已顺利拿offer。

你这题确实不好写啊。
难度应该是hard了吧?比leetcode hard里面的number of island, lru, merger k sorted lists等难多了。
回复 支持 反对

使用道具 举报

 楼主| 隐隐野烟 发表于 2016-1-3 13:35:54 | 显示全部楼层

满满的眼泪,刷了一学期的题,终还是没拿下G,本来还打算若成了去湾区暑期看你的。
来年再战Google,下学期刷GeekforGeek去,望来年能见。
回复 支持 反对

使用道具 举报

Gianluigi 发表于 2016-1-3 14:33:24 | 显示全部楼层
这题很有意思,但感觉的确挺难的。用 trie 能做,但是要 45 分钟 code 好调试出来,真是不容易啊。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 18:25

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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