c*****t 发帖数: 93 | 1 问了一下以前project的biggest challenge
coding题没做好。他先问了怎么用stack来实现queue。我说用两个stack来做
然后他说amortized time complexity是多少。我说insert, remove都是O(1)
然后他问worst case time complexity for remove是多少,这个我以为他是让我算每
个case中最差的那个remove是多少,我说可能是n/2吧,或者是sqrt(n),我说不不太清
楚。没想到他其实是让我求每个case中,remove总共需要的时间,答案是O(3n)。在这
个问题上纠结时间挺长的
总之这块根本准备的时候没看过。没想到会问这么细。而且面试官是俄国人,口音很重
,也有一定问题。
祝同学们都面试好运! | l********t 发帖数: 878 | | k****r 发帖数: 807 | | o***d 发帖数: 313 | 4 worst case of removal???
就是所有的都在第一个stack里吧?然后is O(n)阿,为什么O(3n)?
【在 c*****t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 问了一下以前project的biggest challenge : coding题没做好。他先问了怎么用stack来实现queue。我说用两个stack来做 : 然后他说amortized time complexity是多少。我说insert, remove都是O(1) : 然后他问worst case time complexity for remove是多少,这个我以为他是让我算每 : 个case中最差的那个remove是多少,我说可能是n/2吧,或者是sqrt(n),我说不不太清 : 楚。没想到他其实是让我求每个case中,remove总共需要的时间,答案是O(3n)。在这 : 个问题上纠结时间挺长的 : 总之这块根本准备的时候没看过。没想到会问这么细。而且面试官是俄国人,口音很重 : ,也有一定问题。 : 祝同学们都面试好运!
| j*****y 发帖数: 1071 | 5 armortized 是 O(n) 吧?
两个 stack: s1, s2
s2 is empty.
enque: s1.push
deque: pop s1 to s2 until s1 is empty, s2.pop(). then push s2 back to s1
until s2 is empty
for the amortized time: T(n). firstly T(n) <= O(n)
But we can show T(n) >= \Omega(n)
enque n times, then enque(time cost is 1 ), deque(time cost is 3(n + 1)),
enque(time cose is 1), deque(time cost is 3(n + 1)),...., in this case, the
average time cose >= \Omega(n)
So the amortized cost is O(n)
【在 c*****t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 问了一下以前project的biggest challenge : coding题没做好。他先问了怎么用stack来实现queue。我说用两个stack来做 : 然后他说amortized time complexity是多少。我说insert, remove都是O(1) : 然后他问worst case time complexity for remove是多少,这个我以为他是让我算每 : 个case中最差的那个remove是多少,我说可能是n/2吧,或者是sqrt(n),我说不不太清 : 楚。没想到他其实是让我求每个case中,remove总共需要的时间,答案是O(3n)。在这 : 个问题上纠结时间挺长的 : 总之这块根本准备的时候没看过。没想到会问这么细。而且面试官是俄国人,口音很重 : ,也有一定问题。 : 祝同学们都面试好运!
| O******i 发帖数: 269 | 6 印象中俄国人的题目都比较难,人家毕竟出过闵可夫斯基,马尔科夫,切比雪夫,辛钦
... | l*****a 发帖数: 559 | 7
Pushing s2 back to s1 is not necessary. You can keep elements in s2.
【在 j*****y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : armortized 是 O(n) 吧? : 两个 stack: s1, s2 : s2 is empty. : enque: s1.push : deque: pop s1 to s2 until s1 is empty, s2.pop(). then push s2 back to s1 : until s2 is empty : for the amortized time: T(n). firstly T(n) <= O(n) : But we can show T(n) >= \Omega(n) : enque n times, then enque(time cost is 1 ), deque(time cost is 3(n + 1)), : enque(time cose is 1), deque(time cost is 3(n + 1)),...., in this case, the
| j*****y 发帖数: 1071 | 8 got it. thanks.
【在 l*****a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : Pushing s2 back to s1 is not necessary. You can keep elements in s2.
| y********9 发帖数: 130 | |
|