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 的大作中提到】
: 问了一下以前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 的大作中提到】
: 问了一下以前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 的大作中提到】
: 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 的大作中提到】
:
: Pushing s2 back to s1 is not necessary. You can keep elements in s2.
| y********9
发帖数: 130 | |
|
