一亩三分地论坛

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

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

不怎么新鲜的G家面经

[复制链接] |试试Instant~ |关注本帖
爱岛饭 发表于 2015-3-11 08:41:11 | 显示全部楼层 |阅读模式

2015(1-3月) 码农类 硕士 实习@Google - 内推 - 技术电面 |Fail

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

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

x
其实LZ是上个月面的,一直在等消息,然后今天收到了邮件说被拒了,感觉人品已经到了低谷。


. 鍥磋鎴戜滑@1point 3 acres
1. 国人大哥,态度很好 。题目是求一个数的立方根(二分),分析复杂度,follow up,假如要求精确到小数后k位。
2. 美国人。 1)给一个数组,要求处理后奇数放一边偶数放一边。这个我很快就写完了。2)design题, 假设有一个map,用户的query是找某个地点附近的餐馆,如何设计?(这个我说的是把地图分块做成hashtable然后设置一个thredshold每次以目的地点为半径查找) follow up,thredshold怎么设计?这样计算效率是多少?假如用户在两个城市的交界处呢?
3. 美国人。1)给一个字符串,要求找到第一个非字母表升序的字符,非数字或字母算unvalid,考虑大小写。 2)设计数据结构存储全美国人民的电话号码,能实现随意返回一个可用号码的功能。follow up,空间复杂度?怎么降低空间复杂度?(bit set),collision的概率是多少?
. visit 1point3acres.com for more.
. 1point3acres.com/bbs
总体感觉很简单,都是很快就写出来了,想了想如果说被拒的原因,可能是第三个人聊得时候沟通不是很通畅,老是反复让她重复题目,然后可能有些地方出了点小bug之类的。无论如何,之前一直在纠结着到底过没过,现在盒子打开了,薛定谔的猫死了,也算是毫无牵挂了。找实习基本上告一段落了,在经历了无数次被虐后,虽然还是并不知道自己要干什么,但是至少希望以后如果能有机会,一定要做一个nice的面试官,让大家面试的过程不再那么痛苦,鼓励每一个正在努力的少年们。


虽然LZ最近RP已经快没了,但是还是想把RP拿出来分给还没有找到实习的小伙伴们【撒


Good Luck Have Fun !. From 1point 3acres bbs




评分

7

查看全部评分

timtam85 发表于 2015-3-12 13:20:10 | 显示全部楼层
楼主第一题能说一下解法么?
回复 支持 反对

使用道具 举报

 楼主| 爱岛饭 发表于 2015-3-12 23:00:41 | 显示全部楼层
timtam85 发表于 2015-3-12 13:20
楼主第一题能说一下解法么?

就是从[1,n]开始二分地搜索立方根,每次取中间的数看看立方是否超过n。然后如果要求k位精度的话,把数本身先乘10^3k然后用相同的方法求出整数解后再把结果除以10^k
回复 支持 反对

使用道具 举报

timtam85 发表于 2015-3-13 12:27:29 | 显示全部楼层
爱岛饭 发表于 2015-3-12 23:00
就是从[1,n]开始二分地搜索立方根,每次取中间的数看看立方是否超过n。然后如果要求k位精度的话,把数本 ...

谢谢回答。乘10^3k不考虑overflow么?Interviewer说不用考虑这个?
回复 支持 反对

使用道具 举报

 楼主| 爱岛饭 发表于 2015-3-13 12:56:33 | 显示全部楼层
timtam85 发表于 2015-3-13 12:27
谢谢回答。乘10^3k不考虑overflow么?Interviewer说不用考虑这个?

是的,他说不用考虑溢出问题,然后要求使用之前实现的函数,所以,应该就是这样做吧。
回复 支持 反对

使用道具 举报

woshiee123 发表于 2015-3-14 00:38:27 | 显示全部楼层
楼主电话号码那题是hashtable 么 有没有更好的方法?谢谢
回复 支持 反对

使用道具 举报

 楼主| 爱岛饭 发表于 2015-3-14 10:38:19 | 显示全部楼层
woshiee123 发表于 2015-3-14 00:38
楼主电话号码那题是hashtable 么 有没有更好的方法?谢谢

我用的是hashset,后来改进了一下用bitset,但是空间复杂度还是不小,不过想不到更好的方法了。
回复 支持 反对

使用道具 举报

 楼主| 爱岛饭 发表于 2015-3-14 10:38:30 | 显示全部楼层
woshiee123 发表于 2015-3-14 00:38
楼主电话号码那题是hashtable 么 有没有更好的方法?谢谢

我用的是hashset,后来改进了一下用bitset,但是空间复杂度还是不小,不过想不到更好的方法了。
回复 支持 反对

使用道具 举报

mm豆 发表于 2015-3-15 05:35:19 | 显示全部楼层
1)给一个字符串,要求找到第一个非字母表升序的字符,非数字或字母算unvalid,考虑大小写。 不太理解题意。举个例子“abcdfg”,则答案是d,对不?
回复 支持 反对

使用道具 举报

mm豆 发表于 2015-3-15 05:36:40 | 显示全部楼层
2)设计数据结构存储全美国人民的电话号码,能实现随意返回一个可用号码的功能。可以不可以使用数组保存,然后生成随机数,返回数组元素?
回复 支持 反对

使用道具 举报

mm豆 发表于 2015-3-15 05:40:49 | 显示全部楼层
1)给一个字符串,要求找到第一个非字母表升序的字符,非数字或字母算unvalid,考虑大小写。这个题直接遍历可解。如果用binary search可以找到一个peak,但怎么找第一个peak呢?楼主能不能分享下你的思路?
回复 支持 反对

使用道具 举报

 楼主| 爱岛饭 发表于 2015-3-15 08:22:51 | 显示全部楼层
mm豆 发表于 2015-3-15 05:40
1)给一个字符串,要求找到第一个非字母表升序的字符,非数字或字母算unvalid,考虑大小写。这个题直接遍历 ...

sorry题目可能没有描述太清楚,补充一下。
1)第三题字符串的一个例子是,“ABCDA” 输出“A”因为“DA”是降序,如果是“ABDR”就输出空。字母升序不要求是连续的,只要是升序就行。我的做法就是顺序遍历一遍,因为要判断每个字符是不是valid,所以应该做不了binary search
2)电话号码那题,要求是能满足三个功能。1.判断一个号码是否可用,2.把一个号码标记为不可用,3.随机返回一个可用号码。所以我用的hashset
回复 支持 反对

使用道具 举报

mm豆 发表于 2015-3-16 06:47:38 | 显示全部楼层
爱岛饭 发表于 2015-3-15 08:22
sorry题目可能没有描述太清楚,补充一下。
1)第三题字符串的一个例子是,“ABCDA” 输出“A”因为“DA ...

谢谢楼主分享,电话号码的那个题,我考虑建立一个tire,这样可以节省储存空间,查询也是O(l)的复杂度,删除就是trie的删除,随机取就是图的随机便利。空间复杂度是O(9^l)
回复 支持 反对

使用道具 举报

mm豆 发表于 2015-3-16 07:48:32 | 显示全部楼层
爱岛饭 发表于 2015-3-15 08:22.1point3acres缃
sorry题目可能没有描述太清楚,补充一下。
1)第三题字符串的一个例子是,“ABCDA” 输出“A”因为“DA ...

如果使用hashset,怎么ramdom得到一个数?
回复 支持 反对

使用道具 举报

 楼主| 爱岛饭 发表于 2015-3-16 12:52:01 | 显示全部楼层
mm豆 发表于 2015-3-16 07:48
如果使用hashset,怎么ramdom得到一个数?

我说的是随机生成hashcode然后判断在不在里面,或者如果是有序的hashset的话直接返回第一个
回复 支持 反对

使用道具 举报

williamshyy 发表于 2015-3-19 10:41:48 | 显示全部楼层
设计数据结构存储全美国人民的电话号码,能实现随意返回一个可用号码的功能。用tri树可以吗?
根节点10个数字分支,全permutation最底层就是10的10次方个字符....也好过10的10次方个号码.....然后随机选择就是做dfs....随机选分支。。。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 07:02

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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