Linkedin Onsite

say543 发表于 2016-12-10 15:52
make sense 多谢分享用一个一维array因该就能解... 不过time complexity 因该是o(mn) 这样因该没有比先 ...

不能先sort，因为题目要求必须是按原先的顺序的一一对应的。比如a1 对应b3, a2对应b9, a3对应b17
如果sort b数组的话是不符合题目要求的。

a中的每个元素都得用上，b的长度大于等于a，a中每个元素到b里面选一个对应的元素（必须按顺序取）使的差值的之和为最小。
我是举例子，math.abs(a1-b3)＋math.abs(a2-b9)+math.abs(a3-b17)为最小，不能sort是因为如果sort了，a和b的顺序就被打乱了。比如上面的例子，不能取a1-b3, a2-b1这种是不合法的。

最后一题pinkdatura 说的对，不好意思也没讲清楚

HR告诉我现在在 team match, 感觉一定是面试遇到的国人哥哥姐姐帮忙放水了。 求问最近哪个组有坑， 有没有可能match不上的？

simonwoo 发表于 2016-12-12 08:55
谢谢你的解答. 原来是这样，楼主完全没说清楚啊，你是怎么知道的?

因为我也被面了这题，还有
http://www.1point3acres.com/bbs/thread-212481-1-1.html
这个第4轮的第三题，中国小哥问的，一点都木有放水的意思，而且全是新题
我面的比楼主早一周可是到现在还没消息，估计悲剧了5555

pinkdatura 发表于 2016-12-12 13:18
因为我也被面了这题，还有
http://www.1point3acres.com/bbs/thread-212481-1-1.html
这个第4轮的第三 ...

" 实现一个maxstack 功能有pop peek peekMax popMax, popMax要求O(1) 应该是挂在这上了 最后没想出来popMax O(1)怎么做"      
恍然大悟..这题你有想出o(1) 吗...遇到国人真的是...

say543 发表于 2016-12-13 15:53
" 实现一个maxstack 功能有pop peek peekMax popMax, popMax要求O(1) 应该是挂在这上了 最后没想出来pop ...

根据我和小哥的讨论，最多还是所有操作是o(logn)只有peekmax()和peek()有o(1), 我用了一个treemap key是大小，value是doubly linkedlist node加上一个doubly linkedlist的结构做的，因为涉及到增删treemap是不可能做奥o(1)的