本科全职 谷歌电面面经

处女贴。

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

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

20150101   | cba321 | 32.119  | -12.3192

20150101   | fed921  | 32.249   | -13.4090

20150101   | iop754  | 35.709   | -12.2590

20150102   | ert857

您好！
本帖隐藏的内容需要积分高于 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行

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

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

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

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

多谢楼主分享，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就行

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

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

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