一亩三分地论坛

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

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

G onsite 2015/02/09

[复制链接] |试试Instant~ |关注本帖
tianyangche 发表于 2015-2-10 10:40:09 | 显示全部楼层 |阅读模式

2015(1-3月) 码农类 硕士 全职@Google - 内推 - Onsite |Other

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

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

x
斗胆面了谷歌,小弟很弱,不出意外挂了,因为每轮只面我一道题。.1point3acres缃
1. 给你一个target number,和一个list,list里面装的都是整数。问是否能用list里面的所有数字,只用四则运算和括号之类的,问能不能得到target number。很像24点,不过是它的扩展。
2. 给你一堆input,每一个input是一条边,表示谁和谁是朋友,例如
    1 - 2
    3 - 4
    4 - 5. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
    要求找出所有的groups,每个group里面的人认识,group和group间的人不认识。如上面的例子,返回 {1, 2}, {3, 4, 5}
3. 先讲了半天什么事profiling。所谓的profiling是指一个程序,里面有许多函数,我们记录每个函数什么时候开始执行,什么时候执行结束。输入就是一堆entry,每个entry有:函数名,时间戳,开始执行/执行结束,例如:
    main    0       ENTER
    foo      5       ENTER
    foo      50     EXIT
    bar      60     ENTER
    bar      90     EXIT
    main    100   EXIT. more info on 1point3acres.com
输出有以下要求:1.按照CPU执行的顺序来显示结果。2. 若一个函数a里面调用函数b,函数b要求缩进。. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
    main       100.鏈枃鍘熷垱鑷1point3acres璁哄潧
         foo        45
         bar        30
4. 给两组点,第一组的点都在圆上,第二组的点都在圆外,从第一组里面和第二组里面分别找一点,这两点之间的距离最小。

小弟技术浅薄,经验少,估计要挂了……希望各位大大集思广益~

评分

6

查看全部评分

本帖被以下淘专辑推荐:

Primer 发表于 2015-2-10 15:16:57 | 显示全部楼层
lklk1986fa 发表于 2015-2-10 15:06
请问第四题有什么比较好的方法呢

可不可以把圆上每个点用与x轴夹角表示,然后对圆外每个点,取其与圆心连线相对于x轴的夹角,找与这个夹角最近的圆上的点(二分查找,因为圆上点也是夹角表示的),算距离,这个就是对于当前圆外点与所有圆上点的距离的最小值了,比较所有圆外点算得的最小值来得到全局最小值,复杂度是O(NLogM), 如果圆外N个点圆上M个点的话
回复 支持 1 反对 0

使用道具 举报

babysor 发表于 2015-2-10 11:15:54 | 显示全部楼层
看了一趟,感觉第一题蛮有趣的。
除了recursion暂时想不到其他方法了...当时楼主怎么解决的?这道题就是耗一轮的节奏,不要担心,祝有offer
回复 支持 反对

使用道具 举报

茕茕梦 发表于 2015-2-10 11:50:50 | 显示全部楼层
赞一个!G家onsite录取率确实不高,据说大概1/4-1/7。。。不过感觉楼主还是挺有希望的,他家每轮一题的节奏很正常啊,祝楼主早日拿到offer!
回复 支持 反对

使用道具 举报

茕茕梦 发表于 2015-2-10 11:52:45 | 显示全部楼层
对了请问楼主是在Mountain View面的么?
回复 支持 反对

使用道具 举报

Linzertorte 发表于 2015-2-10 12:25:01 | 显示全部楼层
感觉这些题好题。楼主运气不太好。
回复 支持 反对

使用道具 举报

 楼主| tianyangche 发表于 2015-2-10 12:59:18 | 显示全部楼层
babysor 发表于 2015-2-10 11:15
看了一趟,感觉第一题蛮有趣的。. from: 1point3acres.com/bbs
除了recursion暂时想不到其他方法了...当时楼主怎么解决的?这道题就是耗 ...

对的~我是用的recursion解法~
回复 支持 反对

使用道具 举报

 楼主| tianyangche 发表于 2015-2-10 13:05:08 | 显示全部楼层
茕茕梦 发表于 2015-2-10 11:50
赞一个!G家onsite录取率确实不高,据说大概1/4-1/7。。。不过感觉楼主还是挺有希望的,他家每轮一题的节 ...

嗯,没关系,小弟本着不抱希望的心态去,反而很放松。是的,我是在mountain view面的。
回复 支持 反对

使用道具 举报

 楼主| tianyangche 发表于 2015-2-10 13:05:59 | 显示全部楼层
Linzertorte 发表于 2015-2-10 12:25
感觉这些题好题。楼主运气不太好。
.1point3acres缃
我也不知道啦,刚开始想了几个方法,他们说不够优化,就在他们的提示下最后反正都写出来了,结果如何看天意了
回复 支持 反对

使用道具 举报

YY大帝 发表于 2015-2-10 13:36:31 | 显示全部楼层
求问第二题的思路,感觉可以用并查集,但也蛮复杂的,LZ有别的方法吗,比如用啥data structure存的
回复 支持 反对

使用道具 举报

 楼主| tianyangche 发表于 2015-2-10 14:51:50 | 显示全部楼层
YY大帝 发表于 2015-2-10 13:36. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
求问第二题的思路,感觉可以用并查集,但也蛮复杂的,LZ有别的方法吗,比如用啥data structure存的

不知道何为并查集~小弟把这道题看作是一道图题,每个人建一个Person类,里面有他的id,还有一个list,用来存所有的他的friends。假如有n个人,那么
1.首先建立一个n大小的Person数组persons,里面的每个元素对应一个人。并且建立一个n大小的visited的boolean数组,用于判断某一个人是否已经处理过
2.然后处理输入,对于每个输入,把这个边的两个点分别加入到相应的人的friends里面去。
3.遍历数组。如果某一个人被放问过,那么略过,处理下一个。如果没有被放问过,分为两种情况
   a. 没有friends,那么单独成为一个group,加入到一个tempList里面,然后存进最终的结果list
   b. 有friends,把所有的未被放问过的friends放入一个queue里面,并且放入tempList里面,之后把这个person的visited标志为已访问。然后遍历这个queue。遍历这个queue的时候,基本上是和b步骤累死的过程,直到queue为空。
回复 支持 反对

使用道具 举报

lklk1986fa 发表于 2015-2-10 15:06:54 | 显示全部楼层
请问第四题有什么比较好的方法呢
回复 支持 反对

使用道具 举报

 楼主| tianyangche 发表于 2015-2-10 15:19:47 | 显示全部楼层
lklk1986fa 发表于 2015-2-10 15:06
请问第四题有什么比较好的方法呢

我想了半天没想出来,然后面试官提醒我用极坐标。假如在圆上的点的list是A,在园外的点的list是B。我想了个办法,把两个list里面的数都放在一个大list里面,叫做C,然后根据他们相对于圆心的弧度排序。然后C,每次找到一个B里面的点,就找到这个点在前面的一个和后面的一个A里面的点,然后比较这两个A里面的点和B里面的点的距离就可以了。这样的话,时间复杂度大约降到O(nlogn),也就是之前排序的时间复杂度。后面的时间复杂度是O(n).
回复 支持 反对

使用道具 举报

 楼主| tianyangche 发表于 2015-2-10 15:23:55 | 显示全部楼层
Primer 发表于 2015-2-10 15:16
可不可以把圆上每个点用与x轴夹角表示,然后对圆外每个点,取其与圆心连线相对于x轴的夹角,找与这个夹角 ...

嗯,咱俩的做法差不多哦~
回复 支持 反对

使用道具 举报

YY大帝 发表于 2015-2-10 23:45:29 | 显示全部楼层
tianyangche 发表于 2015-2-10 14:51
不知道何为并查集~小弟把这道题看作是一道图题,每个人建一个Person类,里面有他的id,还有一个list,用 ...

好想法!
回复 支持 反对

使用道具 举报

yangbin009 发表于 2015-2-11 01:59:17 | 显示全部楼层
第二题能不能建一个n*n的boolean matrix, 对于每个pair把相应的两个位置置1,然后用一个visited[] 和BFS的方法 遍历从1到n?.鐣欏璁哄潧-涓浜-涓夊垎鍦
感觉每道题都有意思。
谢谢分享!
回复 支持 反对

使用道具 举报

 楼主| tianyangche 发表于 2015-2-11 03:13:39 | 显示全部楼层
回复 支持 反对

使用道具 举报

 楼主| tianyangche 发表于 2015-2-11 03:16:50 | 显示全部楼层
yangbin009 发表于 2015-2-11 01:59
第二题能不能建一个n*n的boolean matrix, 对于每个pair把相应的两个位置置1,然后用一个visited[] 和BFS的 ...

.鏈枃鍘熷垱鑷1point3acres璁哄潧我觉得可以呀,我用的是邻接表,你用的是邻接矩阵,是图的两种表示方式~
回复 支持 反对

使用道具 举报

yapingchen1990 发表于 2015-2-11 03:46:19 | 显示全部楼层
yangbin009 发表于 2015-2-11 01:59
第二题能不能建一个n*n的boolean matrix, 对于每个pair把相应的两个位置置1,然后用一个visited[] 和BFS的 ...

我想的也是这样,转成图问题,我想的是建成adjency list, 正在看楼主的方法
回复 支持 反对

使用道具 举报

TsenAlex 发表于 2015-2-11 04:33:51 | 显示全部楼层
LZ几轮电面拿到的onsite 电面是什么水平的题目啊? 从内推到电面到onsite分别花了多少时间?
多谢啦!!!
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 18:17

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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