图森fullstack二面面经

贡献一个TuSimple full stack二面跪经攒rp
上周五面的（Nov. 30），还是国人小哥，直接做题。一个排序后的长度为N的int list

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

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

，6，面试官说都可以，但选出的错误数字的个数和k有关。听起来是个很关键的hint，但是慧根不够，从这个角度出发我没有任何想法...攒rp攒rp，希望看到的好心人给我加米加米，谢谢

我一面是这道题。。没见过，开始思路和你一样，但是面试官好心提示我说直接找出改变的值非常困难，然后我就想别的方法，先想出的是前面那位说的把数组分裂成k个单调的子数组再merge,写了代码后面试官再问有没有更好的方法，然后又说了一个用栈的方法。思路就是遍历， 每次遍历和栈顶元素比较，碰到比栈顶小的数就把栈顶元素pop,和当前值一起存到另一个数组。这样一遍遍历下来得到两个数组，可以保证存在栈里的数组是单调的，另一个数组的size应该是O（k）,然后sort一下，merge 两个数组。复杂度是 n+klogk.

我也考到了这道题 改变k个数字的位置 你想想 最后就相当于merge k个sorted list这样就变成leetcode原题了 可以做到nlogk

zaczhang 发表于 2019-2-21 06:18
我一面是这道题。。没见过，开始思路和你一样，但是面试官好心提示我说直接找出改变的值非常困难，然后我就 ...

请教一个问题
比如像数组 5 7 8 1 2
K 可能2， 也可能是3.
那我们怎么确定 “另一个数组的size应该是O（k）“



补充内容 (2019-3-9 06:52):
如果每次 加进去的STACK上面的数 和比它小的数， 那最后不是变成 K * 2了？

ruy1su 发表于 2018-12-3 08:10
我也考到了这道题 改变k个数字的位置 你想想 最后就相当于merge k个sorted list这样就变成leetcode原题了  ...

写作业写得记忆混乱...对，面试官提示说不用binarysearch，我写的时候第二部分用了一般的merge...你的意思就是原list能split成order正确的sublist，然后merge？这么一说这题很正常，还是我太菜了orz，谢谢层主！

这题应该用heap来做，建一个大小为k的min heap，然后从左往右每次pop最小的，push进去新元素，时间复杂度klogN

请问楼主一面是什么时候？几天后通知二面

hulei125 发表于 2018-12-3 10:21
请问楼主一面是什么时候？几天后通知二面

他家比较快，Nov.14一面，Nov.16通知二面

lhy5442 发表于 2018-12-3 10:01
这题应该用heap来做，建一个大小为k的min heap，然后从左往右每次pop最小的，push进去新元素，时间复杂度kl ...

好主意，完全没想到heap。面试时的感觉就是走错路了，但是又没有其它选择/眼泪。不过我觉得是大小k+1的min heap和O(Nlog(k+1))，不知道有没有理解错

Elsa_Diana 发表于 2018-12-3 08:28
写作业写得记忆混乱...对，面试官提示说不用binarysearch，我写的时候第二部分用了一般的merge...你的意 ...

没事 我也跪了哈哈哈 他们家bar挺高的 希望你能收到好消息 祝找工顺利！

ruy1su 发表于 2018-12-3 16:26
没事 我也跪了哈哈哈 他们家bar挺高的 希望你能收到好消息 祝找工顺利！

同祝顺利~

刚刚考到这题，，后悔赶due没有好好看面经。面试官要求的时间复杂度是N + klogk，所以用minHeap做是不可以的，还是要先找到错误的k个数字。