lyft面经

感谢地里的推荐，可惜没过。
电面：
有一堆log，每行的格式是“时间点：各种操作”；给定两个时间点，求在这两个时间点（start， end）内的

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

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

ted）。

面试交流说的挺好，可惜很快就拒了。反馈说解法不是optimal的。

teedoo 发表于 2017-8-7 13:20
我怎么感觉和LC 34比较像？两次binary search找到start time的开始一行和end time的最后一行

这道题我的第一反应和你类似：
既然给定时间点了 且已知数据格式是“时间点：各种操作” ， 那我就两次二分 分别找到start的第一行 和end的最后一行，然后既然是一个时间点一个log 直接 wc -l

那么楼主说不optimal的思路是？

xuanyue 发表于 2017-8-7 13:44
我倒是觉得要用到外部排序的思想?

毕竟 楼主的描述是, 一堆文件,  然后每个都很大. (可能无序?)  那应该 ...

一开始就说是service log，所以是按照时间排好序的。文件很大，只是暗示不要尝试load进memory；此外也确认是单线程操作，所以也没有分布式和并行的问题（可能会做follow－up吧）。

xuanyue 发表于 2017-8-7 13:44
我倒是觉得要用到外部排序的思想?

毕竟 楼主的描述是, 一堆文件,  然后每个都很大. (可能无序?)  那应该 ...

会不会可能是因为LZ写的worst case不够好，因为LZ用正常的binary找到start就停下了，那么比如1,2,3，3,3,3,3,3,3,4,5这样就很慢，如果全是3的array的话直接worst case就logn了，

这道题和经典的“100楼扔鸡蛋”好像

补充内容 (2017-8-7 13:38):
求出来x(x+1)/2 >= numOfLines， numofLines估计可以用fileSize估一下？然后先goToOffset(x), 如果比start大就往回找，如果比start小就再gotoOffset(x +(x-1))这样一直找，直到numOfLines肯定能找到了。

我怎么感觉和LC 34比较像？两次binary search找到start time的开始一行和end time的最后一行

我倒是觉得要用到外部排序的思想?

毕竟 楼主的描述是, 一堆文件,  然后每个都很大. (可能无序?)  那应该不能考虑直接 sort 吧.

teedoo 发表于 2017-8-7 13:20
我怎么感觉和LC 34比较像？两次binary search找到start time的开始一行和end time的最后一行

可是LZ用的就是lc34的方法吧 不知道在filesize很大的情况下会有什么不同

goToOffset() 是什么意思？

FightForTomo 发表于 2017-8-7 14:02
goToOffset() 是什么意思？

就是把当前文件指针移到离当前位置为某offset值的位置

LeetCode 635?