狗家2轮电面

前几天面的。已经拿到onsite。题目:

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

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

求点大米看包袱啊！！

要找list1里去除list2的话为什么不能直接traverse list2然后尝试.index .pop呢 :3 am i missing something?

TW海豆 发表于 2019-5-3 15:05
要找list1里去除list2的话为什么不能直接traverse list2然后尝试.index .pop呢 :3 am i missing something? ...

当你碰到一个list2中的数字时，你怎么判断这个数字是否在list1里存在与否。

TW海豆 发表于 2019-5-3 15:05
要找list1里去除list2的话为什么不能直接traverse list2然后尝试.index .pop呢 :3 am i missing something? ...

如果你说的是unsorted list，求index是一个O(n)的过程鸭

我觉得two pointer是个好办法，不过可能牺牲了点时间。

wangyishuo123 发表于 2019/05/03 15:10:02


当你碰到一个list2中的数字时，你怎么判断这个数字是否在list1里存在与否。

哦哦我想的是.index，locate到第一个在list2里的list1 element，但楼下的人说了这个过程是O（n）会很慢，i guess我一开始没想太多time complexity哈哈哈 surprise楼主第一个solution就给了hash table :P

lalxyy 发表于 2019/05/03 21:05:22


如果你说的是unsorted list，求index是一个O(n)的过程鸭

是滴 i guess我assume了sorted因为example都是sorted的！my bad哈哈

排序双指针的算法，复杂度不应该就是O(MLogM + NLogN)嘛？MLogM + NLogN 肯定 >= M+N

moluren 发表于 2019-5-6 16:55
排序双指针的算法，复杂度不应该就是O(MLogM + NLogN)嘛？MLogM + NLogN 肯定 >= M+N

逻辑上肯定是这样的。我只是写了一下而已。

wangyishuo123 发表于 2019-5-7 02:19
逻辑上肯定是这样的。我只是写了一下而已。

谢谢楼主的回复