双卡双待iphone，不支持同运营商双卡！！！ - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>PDA - 掌中宝

双卡双待iphone，不支持同运营商双卡！！！

双卡双待iphone，不支持同运营商双卡！！！# PDA - 掌中宝

C*72018-09-19 07:09

1 楼

国女，第一题找n个数中最大的k个，我说用size为k＋1的min heap，放满，然后循环里
不断
poll和add。她觉得结果不对，我就写了下伪码示意（她没让我写代码，我是为了给她
讲明白）
minHeap(k+1)
for(){
heap.poll();
heap.add();
}
她认为不正确，说如果先遇到前k大的结果就不对了（此处我也不知道她在想什么），
我就给她解释＋测试，她又想到别的情况，换各种测试，10多分钟浪费在这，她终于觉
得好像没错。中间我试图给她个台阶，说quick select方法更快，但她完全不理会，继
续纠缠heap的正确性。后来终于跟我说，她想要的解法时size为k的heap，循环里先
peek再根据情况add。如果是讨论复杂度我完全理解，为什么方法不一样就认为是错的
，水平实在很让我吃惊，到最后也没跟我提quick select方法，目测已经超出了她的知
识范围
第二题不知从哪粘过来的，背景还是红色的。。在string末尾添加字符串，使原string
成为回文，返回需要添加的最小string。跟leetcode的Shortest Palindrome差不多，
那题我是一次过的。循环中两种情况：以字母为中心；以字母间隔为中心。她问我为什
么要考虑第二种情况，我是连画图，再举例，她愣是不明白，最后说要回去再想想。
结果给我来个据信。各位不用怀疑我面试中的态度，我是绝对耐心＋各种给台阶说可能
是我没说清
又一次不得不提到烙印，对比实在太明显，前一天推特电面，merge k个iterator of
list，也是用的heap，中间对iterator的操作跟他的要求有点出入，改了一遍，之后给
了onsite

p*b2018-09-19 07:09

2 楼

像支持双卡双待的新苹果手机在国内是肯定会非常火的，但是咱们这些华人也独爱双卡
双待啊，我也一样，也准备入手一个双卡双待的机器，因为我现在用的就是双卡双待。
有一件事大家是不清楚的，就是关于苹果的这个双卡双待，如果说你不了解的话我可以
保证你的双卡双待跟单卡单带不会有太大的区别。
苹果新手机的双卡双待是“不支持同一个运营商双卡的”，能不能明白什么意思？打比
方说，你有两个联通的手机号，这在苹果手机里面是行不通的，必须一个是联通一个是
移动才行。

j*82018-09-19 07:09

3 楼

k size min heap就可以阿，为啥你要用k+1
不过有时候是这样，当你已经有一个预期的答案，而对方给了一个不一样的，有的人会
一时半会反应不过来

【在 C*7 的大作中提到】

: 国女，第一题找n个数中最大的k个，我说用size为k＋1的min heap，放满，然后循环里
: 不断
: poll和add。她觉得结果不对，我就写了下伪码示意（她没让我写代码，我是为了给她
: 讲明白）
: minHeap(k+1)
: for(){
: heap.poll();
: heap.add();
: }
: 她认为不正确，说如果先遇到前k大的结果就不对了（此处我也不知道她在想什么），

t*y2018-09-19 07:09

4 楼

估计是esim的限制
大陆版的物理双卡应该是可以的吧

I*g2018-09-19 07:09

5 楼

报上名字来。

【在 C*7 的大作中提到】

C*72018-09-19 07:09

6 楼

k＋1在循环里很好写，比较直观的想到的，她要是说space用多了或者不是最优解，我
完全理解，可是时间都浪费在验证正确性上了。这么简单的操作，还非要我一个数一个
数的演示，演示了至少5个test case她才放心，简直把我雷翻了

【在 j*****8 的大作中提到】

: k size min heap就可以阿，为啥你要用k+1
: 不过有时候是这样，当你已经有一个预期的答案，而对方给了一个不一样的，有的人会
: 一时半会反应不过来

C*72018-09-19 07:09

7 楼

电话一开始说了个名字，没记住，我倒是也很想找她聊一聊

【在 I*******g 的大作中提到】

: 报上名字来。

m*n2018-09-19 07:09

8 楼

你这个是不对吧，需要先add()后poll(). 试试K＝1，输入3，2，1，你的结果是1.

【在 C*7 的大作中提到】

C*72018-09-19 07:09

9 楼

是，我省略了先把heap放满，电话里说了，她也不是对这块有质疑

【在 m*****n 的大作中提到】

: 你这个是不对吧，需要先add()后poll(). 试试K＝1，输入3，2，1，你的结果是1.

m*n2018-09-19 07:09

10 楼

我也错了，她说的先比再加才是对的。

【在 m*****n 的大作中提到】

: 你这个是不对吧，需要先add()后poll(). 试试K＝1，输入3，2，1，你的结果是1.

s*r2018-09-19 07:09

11 楼

打算聊啥

【在 C*7 的大作中提到】

: 电话一开始说了个名字，没记住，我倒是也很想找她聊一聊

C*72018-09-19 07:09

12 楼

问问为什么不给过，第二题想明白没有

【在 s*****r 的大作中提到】

: 打算聊啥

s*r2018-09-19 07:09

13 楼

heap不是先比再加吗，也许LZ的heap比较特殊，反正俺没看懂他的pseudo code

【在 m*****n 的大作中提到】

: 我也错了，她说的先比再加才是对的。

j*82018-09-19 07:09

14 楼

对，那个国女的是对的
本来就是k size heap，每次先和peek 比较，然后再插入或者discard

【在 m*****n 的大作中提到】

: 我也错了，她说的先比再加才是对的。

C*72018-09-19 07:09

15 楼

是，我同意这解法正确。我的解法在哪里会有错？她最后也同意我解法没错，她给的测
试都没问题

【在 j*****8 的大作中提到】

: 对，那个国女的是对的
: 本来就是k size heap，每次先和peek 比较，然后再插入或者discard

b*52018-09-19 07:09

16 楼

傻逼。自己好好再去想想。 K+1就不用peek，再compare，再决定嫁不嫁。。。

【在 s*****r 的大作中提到】

: heap不是先比再加吗，也许LZ的heap比较特殊，反正俺没看懂他的pseudo code

s*r2018-09-19 07:09

17 楼

晕倒，计算可比存储cheap得多，计算能力是resource里面最cheap的
俺大概知道为啥被据了

【在 b**********5 的大作中提到】

: 傻逼。自己好好再去想想。 K+1就不用peek，再compare，再决定嫁不嫁。。。

b*52018-09-19 07:09

18 楼

你傻逼啊， k和K+1，滚他妈的一边去！！！！还有，你认为这个heap是存在哪里的
？？！！

【在 s*****r 的大作中提到】

: 晕倒，计算可比存储cheap得多，计算能力是resource里面最cheap的
: 俺大概知道为啥被据了

C*72018-09-19 07:09

19 楼

汗，她给我讲了她的方法以后，我给她分析了两种复杂度，她的在某些情况下更好一些
，如果早讨论复杂度，我也不是不能想到她的方法。再说有quick select快吗？

【在 s*****r 的大作中提到】

: 晕倒，计算可比存储cheap得多，计算能力是resource里面最cheap的
: 俺大概知道为啥被据了

s*r2018-09-19 07:09

20 楼

他的code还是有bug，第K+1个数不比就踢走，然后去比K和K-1

【在 b**********5 的大作中提到】

: 你傻逼啊， k和K+1，滚他妈的一边去！！！！还有，你认为这个heap是存在哪里的
: ？？！！

b*52018-09-19 07:09

21 楼

我觉得你和那个中国女面试官，有一比，估计更蠢。。。

【在 s*****r 的大作中提到】

: 他的code还是有bug，第K+1个数不比就踢走，然后去比K和K-1

s*r2018-09-19 07:09

22 楼

你再认真想想，别光发泄

【在 b**********5 的大作中提到】

: 我觉得你和那个中国女面试官，有一比，估计更蠢。。。

C*72018-09-19 07:09

23 楼

莫非heap是靠手动排序的？

【在 s*****r 的大作中提到】

: 他的code还是有bug，第K+1个数不比就踢走，然后去比K和K-1

s*r2018-09-19 07:09

24 楼

child node无序，需要比较两次才能决定谁是最小的

【在 C*7 的大作中提到】

: 莫非heap是靠手动排序的？

f*e2018-09-19 07:09

25 楼

不管怎么样，总要给第二个电面麻。。太无情了。。

C*72018-09-19 07:09

26 楼

peek和poll都是取heap里最小值，只是决定插入不插入的区别，比较两次是什么意思

【在 s*****r 的大作中提到】

: child node无序，需要比较两次才能决定谁是最小的

l*32018-09-19 07:09

27 楼

。。。半瓶醋可以不发言，但是最好不要乱发言

【在 s*****r 的大作中提到】

: 晕倒，计算可比存储cheap得多，计算能力是resource里面最cheap的
: 俺大概知道为啥被据了

l*32018-09-19 07:09

28 楼

size k 的heap和size k+1的heap，空间复杂度是一样的，你的方法没有问题。如果她
说你的方法空间复杂度不如她的，那就只能呵呵了，遇到这样的不懂装懂的，你也没有
办法

【在 C*7 的大作中提到】

: 汗，她给我讲了她的方法以后，我给她分析了两种复杂度，她的在某些情况下更好一些
: ，如果早讨论复杂度，我也不是不能想到她的方法。再说有quick select快吗？

s*r2018-09-19 07:09

29 楼

你个二货，知道heap.add()怎么写吗，你要能写出来，就知道为啥会fail他

【在 l****3 的大作中提到】

: 。。。半瓶醋可以不发言，但是最好不要乱发言

C*72018-09-19 07:09

30 楼

poll包含siftdown，add包含siftup，你想说啥到底

【在 s*****r 的大作中提到】

: 你个二货，知道heap.add()怎么写吗，你要能写出来，就知道为啥会fail他

b*52018-09-19 07:09

31 楼

你是new cop？这个switsuer屁都不懂的，你跟它去纠结？！我狗儿子放的屁，都
要比他的帖子有营养

【在 C*7 的大作中提到】

: poll包含siftdown，add包含siftup，你想说啥到底

C*72018-09-19 07:09

32 楼

哈哈，我这不是想看看他是咋误解的，仿佛回到了面试当天

【在 b**********5 的大作中提到】

: 你是new cop？这个switsuer屁都不懂的，你跟它去纠结？！我狗儿子放的屁，都
: 要比他的帖子有营养

C*72018-09-19 07:09

33 楼

我知道你咋想的了，你是不是认为pq初始化的时候还没有排序，第一个poll取不到最小
值？但initialize pq都是一个一个add进去的，莫非能快捷无序初始化？

【在 s*****r 的大作中提到】

: 你个二货，知道heap.add()怎么写吗，你要能写出来，就知道为啥会fail他

L*s2018-09-19 07:09

34 楼

大家为什么都用min heap呢？
min heap时间复杂度是 O(n*log k) = O (log(k^n)) 啊
用max heap的话时间复杂度是 O(n+ k*log n) = O(n+ log(n^k)) 啊
你们不知道 k^n 一般远大于 n^k吗？所以用max heap更快啊
另外Frederickson有一篇文章说用max heap可以达到O(n+k*log k).
http://www.sciencedirect.com/science/article/pii/S0890540183710
(文章中是求n个数中最小的k个，所以文章中用min heap, 如果是求最大的k个就用max
heap)

C*72018-09-19 07:09

35 楼

会不会n太大放不下。这个题给了n大约在几十万，k大约在几千，但讨论中没提到

max

【在 L*********s 的大作中提到】

: 大家为什么都用min heap呢？
: min heap时间复杂度是 O(n*log k) = O (log(k^n)) 啊
: 用max heap的话时间复杂度是 O(n+ k*log n) = O(n+ log(n^k)) 啊
: 你们不知道 k^n 一般远大于 n^k吗？所以用max heap更快啊
: 另外Frederickson有一篇文章说用max heap可以达到O(n+k*log k).
: http://www.sciencedirect.com/science/article/pii/S0890540183710
: (文章中是求n个数中最小的k个，所以文章中用min heap, 如果是求最大的k个就用max
: heap)

w*12018-09-19 07:09

36 楼

说说我的见解，估计纠结在第一个题，因为我个人认为很可能是面试官想考你的东西没
考出来，所有最后导致“被黑”
从面试的过程来看，她好像不需要你写代码。那么她想要的考的大概是想看看你都知道
有多少种方法(至少3种吧，多多益善)可以做出来，然后再问问每种方法的复杂度，她
的本意并不是想纠结于具体的代码。可能最后不知道怎么就聊到具体的代码然后去
argue了。如果回答的时候先问问这些，可能结果会好很多。
不过说实话，面试的时候哪能想这么多。LZ有实力，肯定能找到好工作。

L*s2018-09-19 07:09

37 楼

嗯有道理，如果n是非常非常大的stream，确实只能用min stack

【在 C*7 的大作中提到】

: 会不会n太大放不下。这个题给了n大约在几十万，k大约在几千，但讨论中没提到
:
: max

l*g2018-09-19 07:09

38 楼

我觉得楼主的算法是正确的，不过复杂度比k size的要高一些，特别是遇到前k是最大
的情况，做了很多无用的add和poll。

h*k2018-09-19 07:09

39 楼

这贴就是胡扯了。

【在 s*****r 的大作中提到】

: 晕倒，计算可比存储cheap得多，计算能力是resource里面最cheap的
: 俺大概知道为啥被据了

L*s2018-09-19 07:09

40 楼

你这是拿k+1的worst case和k比
两个算法average复杂度，各自worst case复杂度都是同样量级，差别很小
楼主的算法也完全正确

【在 l********g 的大作中提到】

: 我觉得楼主的算法是正确的，不过复杂度比k size的要高一些，特别是遇到前k是最大
: 的情况，做了很多无用的add和poll。

xt2018-09-19 07:09

41 楼

为什么不用partition来做呢？

【在 C*7 的大作中提到】

l*g2018-09-19 07:09

42 楼

我同意，但是对于任何的case, K size的算法都一定不会比k+1的差，这就是区别。

【在 L*********s 的大作中提到】

: 你这是拿k+1的worst case和k比
: 两个算法average复杂度，各自worst case复杂度都是同样量级，差别很小
: 楼主的算法也完全正确

L*s2018-09-19 07:09

43 楼

不一定吧，在前k+1个数是最大的情况下，K size就比k+1 size的差.比如
n=9, k=5,
输入[4,5,6,7,8,9,1,2,3]

【在 l********g 的大作中提到】

: 我同意，但是对于任何的case, K size的算法都一定不会比k+1的差，这就是区别。

p*62018-09-19 07:09

44 楼

这话都敢说
[在 swjtuer (灌水和coding都要敲键盘) 的大作中提到：]
：晕倒，计算可比存储cheap得多，计算能力是resource里面最cheap的
：
：...........

T*U2018-09-19 07:09

45 楼

纠结速度和空间优化的话，这题最优是quick select, lz了然于心

max

【在 L*********s 的大作中提到】

l*i2018-09-19 07:09

46 楼

能
长度n的数组建堆是O(n), 从空堆一个一个加进去是nlogn

【在 C*7 的大作中提到】

: 我知道你咋想的了，你是不是认为pq初始化的时候还没有排序，第一个poll取不到最小
: 值？但initialize pq都是一个一个add进去的，莫非能快捷无序初始化？

f*n2018-09-19 07:09

47 楼

k=2
input={2 1 4 3}
k+1=3
minHeap(k+1)={4 3 2}
for(){
heap.poll(); // 2 is pop out so the minHeap becomes {4 3}
heap.add(); // 1 is add to minHeap so it becomes {4 3 1}
}
the heap still needs to pop out the top min to become correct result {4 3}.

h*k2018-09-19 07:09

48 楼

是哦，如果LZ的态度方面没什么问题，应该再给个机会

【在 f**********e 的大作中提到】

: 不管怎么样，总要给第二个电面麻。。太无情了。。

w*22018-09-19 07:09

49 楼

当时没明白别人的算法，事后想想总该明白了。国女怎么样都该给个机会。

【在 h******k 的大作中提到】

: 是哦，如果LZ的态度方面没什么问题，应该再给个机会

l*s2018-09-19 07:09

50 楼

国女本来就想安安静静地考个quick sort交差，你们给人家出难题，这事闹的。
前两天哥面试一家，题目写hashtable，哥选了prime number做array的长度，阿三实在
不明白为什么，哥于是老老实实改成2000，皆大欢喜。不过阿三反应很快，上网搜了一
下马上说我说得对。总之，面试就低调点，别呛火。

【在 w**2 的大作中提到】

: 当时没明白别人的算法，事后想想总该明白了。国女怎么样都该给个机会。