新鲜 脸书 挂经

刘爱华 发表于 2020-7-25 04:06
第一题的想法：
1.平方和排序，用3SUM的思路
2.如果能固定头和尾，是不是可以用binary search...

请问binary search思路是怎样呢？

匿名者 发表于 2020-7-25 05:20
哈哈哈，第一题我其中一个update版本说了3sum, 但后来一想 3sum 也是 On2, 于是我才考虑如果按 绝对值排 ...

我感觉按照绝对值排序然后按3SUM做应该是对的吧
第二题没啥好想法，不知道怎么用“大部分排序”这个条件

lch04 发表于 2020-7-25 08:06
我感觉按照绝对值排序然后按3SUM做应该是对的吧
第二题没啥好想法，不知道怎么用“大部分排序”这个条件

第二题应该是insertion sort
https://www.educative.io/edpress ... almost-sorted-array
然鹅我不搜估计当场也写不出来

第二题目测是 insertion sort，但是具体实现有待商榷 毕竟插入不是那么容易
我能想到的是先用O(n)时间拷贝成 linkedlist，然后开始插入排序，详情请见刷题网一摆四十期.
这样假设未排序好的元素数量占比不太多，时间复杂度会控制在O(kn)，这个应该是有证明的。

第一题我能想到的也是排序+hash...。不得不说我觉得写出来了可能就还行了，华人面试官看来真的。。。

family2018 发表于 2020-7-25 06:07
lz打听下时间线

啊，我这个稍微有点折腾，三月初猎头联系，说可以给准备时间，我之前在忙项目，要了四月底电话
，结果第一次电话还有点和面试官不同意见，没想到猎头说，恩，你简历很好，再店面一次吧，于是五月底有来一次。。然后就约到七月了，期间面了次亚麻得低一点职位，也挂了，不过亚麻那个就更扯淡。。就不吐槽了

hjy 发表于 2020-7-25 05:55
第一题到底是找存不存在两个数的平方和等于第三个数平方呢，还是给你第三个数平方，让你找两个数平方和等于 ...

找 存不存在 A方+B方 = C方， 这三个数。 True or False

sherryuhe 发表于 2020-7-25 05:40
这列没太看懂，是两道题的意思？

对，一个是删链表，简单吧，一个是 易思柳

conghao2016 发表于 2020-7-25 09:13
第二题目测是 insertion sort，但是具体实现有待商榷 毕竟插入不是那么容易
我能想到的是先用O(n)时间拷贝 ...

哈哈哈，哎面试这东西，尤其是大公司，就太应试了

第二题 好像可以用 m-way merge 来做。 扫一遍找出各段排好序的区间，然后再用一个priority Queue存起始值

1.2 is it missing this 条件： “ each element is at most k away from its target position”