本科全职 谷歌电面面经

处女贴。

首先是第一题：有一个日志文件，里面有一条一条的记录，记录着很多用户在各个时间点上所在的经纬度：

时间点 | 用户id   | 经度 | 纬度

20150101   | cba321 | 32.119  | -12.3192

20150101   | fed921  | 32.249   | -13.4090

20150101   | iop754  | 35.709   | -12.2590

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

更加数学的方法呀，我说诶诶诶好小的马上改，然后就写了一个求两点距离的function给他看。他说fine。

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

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





补充内容 (2015-1-17 08:39):
整个程序100行代码，不是前面20分钟写了100行

asdfyou6 发表于 2015-1-17 09:11
什么叫 两个用户第一次相隔足够相近的时间？
足够相近是什么意思？
的时间是什么意思？是指时间点么？还 ...

原话就是New service wants to use it to return the first time two users where close enough to see each other.

比如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
原话就是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是不是在大概某一时间相距很近？但是这个‘某一时间’怎么定义？

Fyi，我就是在狗狗上班，只是上班无聊好奇。

多谢楼主分享，brute force的做法还是比较好想出来的， 两层loop依次比对， 不断更新最小距离， 复杂度O(n^2)。
google了一下发现这还是个挺有意思的问题，wiki上面介绍了一个O(nlogn)的解法， divide and conquer.

http://en.wikipedia.org/wiki/Closest_pair_of_points_problem

什么叫 两个用户第一次相隔足够相近的时间？
足够相近是什么意思？
的时间是什么意思？是指时间点么？还是指哪段时间

楼主为了赞人品还是写上例子的输入输出吧，要不大家都不明白。

我也看不明白，
是任意两个用户第一次相隔距离小于一个常数的时候的时间吗
看起来时间点是按天算的，对应每天的列里面会存放所有用户的位置吗，还是只有改变位置的用户及其位置？

root (经度^2 + 纬度^2) ??????

zuying 发表于 2015-1-17 09:24
root (经度^2 + 纬度^2) ??????

This is what he means at last

nano 发表于 2015-1-17 09:18
我也看不明白，
是任意两个用户第一次相隔距离小于一个常数的时候的时间吗
看起来时间点是按天算的，对应 ...

然也，或者纬度和经度分别小于一个常数，make sense就行

该文件存放着所有用户在所有时间里面的经纬度

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

听君一席话，自挂东南枝。

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