一亩三分地论坛

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

一亩三分地官方iOS手机应用下载
查看: 959|回复: 12
收起左侧

本科全职 谷歌电面面经

[复制链接] |试试Instant~ |关注本帖
itisnanful 发表于 2015-1-17 08:36:40 | 显示全部楼层 |阅读模式

2015(1-3月) 码农类 本科 全职@Google - 网上海投 - 技术电面 |Other

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

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

x
处女贴。. 鍥磋鎴戜滑@1point 3 acres

首先是第一题:有一个日志文件,里面有一条一条的记录,记录着很多用户在各个时间点上所在的经纬度:
时间点 | 用户id   | 经度 | 纬度
20150101   | cba321 | 32.119  | -12.3192
20150101   | fed921  | 32.249   | -13.4090
20150101   | iop754  | 35.709   | -12.2590
20150102   | ert857  | 34.509  | -13.1890
这些记录是按照时间点排序的。
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
我要做的是:设计一个服务,可以返回两个用户第一次相隔足够相近的时间(第一次遇见美丽的自己。爱慕。

没见过啊!我当时有点苦恼。先问了考官说input是什么,给我一个function header好不好,然后他说由你决定

第一步是要跟面试官解释。我琢磨了一两分钟,觉得这道题的wording有点像“找最近”,于是我说用bfs吧。。。用bfs吧。。。不对,你能不能让我先把code写一写,这样我思路好一点?他说好。
. From 1point 3acres bbs

这一写就写了差不多100行代码。我首先把两个user的记录都拿了出来放到两个ArrayList里面。然后又苦苦思索了一下,发现bfs行不通。此时时间已经过去一半了。然后拼命想以前是不是见过类似的题,脑海里依稀出现"two pointers"字眼。刷了leetcode不到一半,硬着头皮在接下来20分钟写完了。

然后肯定就是,第二题!不对,好像40分钟过去了呢。。。于是三哥开始review my code了。他从头看到尾后,指出了一个bug。我改好了,然后他说我确定两个用户是否相近的方法能不能用更加数学的方法呀,我说诶诶诶好小的马上改,然后就写了一个求两点距离的function给他看。他说fine。

45分钟到了。然后我跟他一直聊到55分。我说你是不是在Map组做的,干嘛给我出这种题。他嫣然一笑说是啊两年前。。。

第一次面大公司的电面,居然能遇到这种题,还45分钟就做了一道题啊,简直醉了





补充内容 (2015-1-17 08:39):
整个程序100行代码,不是前面20分钟写了100行
asdfyou6 发表于 2015-1-17 09:11:19 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
什么叫 两个用户第一次相隔足够相近的时间?. 1point3acres.com/bbs
足够相近是什么意思?. from: 1point3acres.com/bbs
的时间是什么意思?是指时间点么?还是指哪段时间-google 1point3acres

楼主为了赞人品还是写上例子的输入输出吧,要不大家都不明白。
回复 支持 反对

使用道具 举报

dalei 发表于 2015-1-17 09:16:34 | 显示全部楼层
关注一亩三分地微博:
Warald
多谢楼主分享,brute force的做法还是比较好想出来的, 两层loop依次比对, 不断更新最小距离, 复杂度O(n^2)。
google了一下发现这还是个挺有意思的问题,wiki上面介绍了一个O(nlogn)的解法, divide and conquer.

http://en.wikipedia.org/wiki/Closest_pair_of_points_problem.1point3acres缃
回复 支持 反对

使用道具 举报

nano 发表于 2015-1-17 09:18:12 | 显示全部楼层
我也看不明白,
是任意两个用户第一次相隔距离小于一个常数的时候的时间吗
看起来时间点是按天算的,对应每天的列里面会存放所有用户的位置吗,还是只有改变位置的用户及其位置?
回复 支持 反对

使用道具 举报

zuying 发表于 2015-1-17 09:24:32 | 显示全部楼层
root (经度^2 + 纬度^2) ??????
求职神器indeed - 在全球最大的求职网站找找适合你的工作?
回复 支持 反对

使用道具 举报

 楼主| itisnanful 发表于 2015-1-17 10:05:11 | 显示全部楼层
asdfyou6 发表于 2015-1-17 09:11. 1point 3acres 璁哄潧
什么叫 两个用户第一次相隔足够相近的时间?
足够相近是什么意思?. visit 1point3acres.com for more.
的时间是什么意思?是指时间点么?还 ...

原话就是New service wants to use it to return the first time two users where close enough to see each other. . from: 1point3acres.com/bbs
.鐣欏璁哄潧-涓浜-涓夊垎鍦
比如sf市中心的某个咖啡馆的经纬度是111, 222, 然后我1月14号8:45在那里,你1月14号8:50在该咖啡馆旁边的电话亭站着,而且以前没这么近过,就返回1月14号8:45或者1月14号8:50.

Function header我写的是public long findFirstTime(String userA, String userB, OpenFile file). 我老实跟他说我不太懂Java的I/O方法,他就让我随便自己写点make sense的名字,OpenFile是一个
回复 支持 反对

使用道具 举报

 楼主| itisnanful 发表于 2015-1-17 10:05:53 | 显示全部楼层
zuying 发表于 2015-1-17 09:24
root (经度^2 + 纬度^2) ??????

. 1point 3acres 璁哄潧This is what he means at last
回复 支持 反对

使用道具 举报

 楼主| itisnanful 发表于 2015-1-17 10:09:19 | 显示全部楼层
nano 发表于 2015-1-17 09:18
我也看不明白,
是任意两个用户第一次相隔距离小于一个常数的时候的时间吗
看起来时间点是按天算的,对应 ...
. 1point 3acres 璁哄潧
然也,或者纬度和经度分别小于一个常数,make sense就行

该文件存放着所有用户在所有时间里面的经纬度
回复 支持 反对

使用道具 举报

 楼主| itisnanful 发表于 2015-1-17 10:12:22 | 显示全部楼层
dalei 发表于 2015-1-17 09:16
多谢楼主分享,brute force的做法还是比较好想出来的, 两层loop依次比对, 不断更新最小距离, 复杂度O(n^ ...

.鏈枃鍘熷垱鑷1point3acres璁哄潧听君一席话,自挂东南枝。

我写出来是O (n)..... two pointers, 但是我总觉得还是有点对的。。。
回复 支持 反对

使用道具 举报

asdfyou6 发表于 2015-1-17 10:27:55 | 显示全部楼层
itisnanful 发表于 2015-1-17 10:05
原话就是New service wants to use it to return the first time two users where close enough to see e ...

对时间有要求么?如果是一个8:40一个10:40呢? 是不是要有个范围?如果是8:40和第二天8:40呢?

这道题的意思是不是看看两个输入的user是不是在大概某一时间相距很近?但是这个‘某一时间’怎么定义?
. 1point3acres.com/bbs
Fyi,我就是在狗狗上班,只是上班无聊好奇。
回复 支持 反对

使用道具 举报

 楼主| itisnanful 发表于 2015-1-17 10:38:38 | 显示全部楼层
asdfyou6 发表于 2015-1-17 10:27
对时间有要求么?如果是一个8:40一个10:40呢? 是不是要有个范围?如果是8:40和第二天8:40呢?

这道 ...

考官说这是几个constant, 是沟通过才知道的。于是我就自己捏造了几个像模像样的constant
回复 支持 反对

使用道具 举报

 楼主| itisnanful 发表于 2015-1-17 10:39:53 | 显示全部楼层
asdfyou6 发表于 2015-1-17 10:27
对时间有要求么?如果是一个8:40一个10:40呢? 是不是要有个范围?如果是8:40和第二天8:40呢?

这道 ...

狗狗大神求罩啊感觉快挂了
回复 支持 反对

使用道具 举报

圆梦梦剧场 发表于 2015-1-17 10:56:01 | 显示全部楼层
dalei 发表于 2015-1-17 09:16
多谢楼主分享,brute force的做法还是比较好想出来的, 两层loop依次比对, 不断更新最小距离, 复杂度O(n^ ...

但这里的point还要区分是user1的point还是user2的point,怎么用divide & conquer?
. more info on 1point3acres.com
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2017-2-27 08:02

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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