N*****N
发帖数: 1605 | 1 【 以下文字转载自 JobHunting 讨论区 】
发信人: fololunsia (我心飞扬), 信区: JobHunting
标 题: 【讨论】两道非常难的Google面试题
发信站: BBS 未名空间站 (Fri May 4 22:20:51 2007)
都是堆栈操作
1. Design an efficient algorithm to sort elements in a stack in either
ascending/descending order, using only pop(), top(), push(), isEmpty(),
isFull(). Do not use any auxiliary stacks or arrays.
2. 如何高效地用 two 堆栈 to simulate a 队列 要求O(1)时间内。 |
t*****l
发帖数: 39 | 2 耐斯曼开始玩算法了，呵呵
【在 N*****N 的大作中提到】
: 【 以下文字转载自 JobHunting 讨论区 】
: 发信人: fololunsia (我心飞扬), 信区: JobHunting
: 标 题: 【讨论】两道非常难的Google面试题
: 发信站: BBS 未名空间站 (Fri May 4 22:20:51 2007)
: 都是堆栈操作
: 1. Design an efficient algorithm to sort elements in a stack in either
: ascending/descending order, using only pop(), top(), push(), isEmpty(),
: isFull(). Do not use any auxiliary stacks or arrays.
: 2. 如何高效地用 two 堆栈 to simulate a 队列 要求O(1)时间内。
|
N*****N
发帖数: 1605 | 3 呵呵，让你们玩，我玩不转啊
【在 t*****l 的大作中提到】
: 耐斯曼开始玩算法了，呵呵
|
T******n
发帖数: 56 | 4 太专业了
【 以下文字转载自 JobHunting 讨论区 】
发信人: fololunsia (我心飞扬), 信区: JobHunting
标 题: 【讨论】两道非常难的Google面试题
发信站: BBS 未名空间站 (Fri May 4 22:20:51 2007)
都是堆栈操作
1. Design an efficient algorithm to sort elements in a stack in either
ascending/descending order, using only pop(), top(), push(), isEmpty(),
isFull(). Do not use any auxiliary stacks or arrays.
2. 如何高效地用 two 堆栈 to simulate a 队列 要求O(1)时间内。
【在 N*****N 的大作中提到】
: 【 以下文字转载自 JobHunting 讨论区 】
: 发信人: fololunsia (我心飞扬), 信区: JobHunting
: 标 题: 【讨论】两道非常难的Google面试题
: 发信站: BBS 未名空间站 (Fri May 4 22:20:51 2007)
: 都是堆栈操作
: 1. Design an efficient algorithm to sort elements in a stack in either
: ascending/descending order, using only pop(), top(), push(), isEmpty(),
: isFull(). Do not use any auxiliary stacks or arrays.
: 2. 如何高效地用 two 堆栈 to simulate a 队列 要求O(1)时间内。
|
o********r
发帖数: 775 | 5 2)
Stack input, stack output.
For element x entering queue:
input.push(x);
For element x leaving queue:
if (output.empty()) {
while (!input.empty()) output.push(input.pop());
}
output.pop(); |
B*********r
发帖数: 267 | 6 学习学习
这个偶不懂啊
是计算机专业的么？
【在 N*****N 的大作中提到】
: 呵呵，让你们玩，我玩不转啊
|
i**********c
发帖数: 22 | 7 it is amortized O(1),
I don't know whether it is allowed
【在 o********r 的大作中提到】
: 2)
: Stack input, stack output.
: For element x entering queue:
: input.push(x);
: For element x leaving queue:
: if (output.empty()) {
: while (!input.empty()) output.push(input.pop());
: }
: output.pop();
|
i**********c
发帖数: 22 | 8
1. the only one I can think of is to use recursion,
but it is actually using the system stack
【在 N*****N 的大作中提到】
: 【 以下文字转载自 JobHunting 讨论区 】
: 发信人: fololunsia (我心飞扬), 信区: JobHunting
: 标 题: 【讨论】两道非常难的Google面试题
: 发信站: BBS 未名空间站 (Fri May 4 22:20:51 2007)
: 都是堆栈操作
: 1. Design an efficient algorithm to sort elements in a stack in either
: ascending/descending order, using only pop(), top(), push(), isEmpty(),
: isFull(). Do not use any auxiliary stacks or arrays.
: 2. 如何高效地用 two 堆栈 to simulate a 队列 要求O(1)时间内。
|
D****g
发帖数: 2860 | 9 amortized O(1) is the best you can get.
【在 i**********c 的大作中提到】
: it is amortized O(1),
: I don't know whether it is allowed
|
m****0
发帖数: 30 | 10 For 1, is recursive approach allowed? |
o********r
发帖数: 775 | 11 Not sure。 However, recursive is using system stacks.
【在 m****0 的大作中提到】
: For 1, is recursive approach allowed?
|
D****g
发帖数: 2860 | 12
what does this exactly mean? O(1) space?
【在 N*****N 的大作中提到】
: 【 以下文字转载自 JobHunting 讨论区 】
: 发信人: fololunsia (我心飞扬), 信区: JobHunting
: 标 题: 【讨论】两道非常难的Google面试题
: 发信站: BBS 未名空间站 (Fri May 4 22:20:51 2007)
: 都是堆栈操作
: 1. Design an efficient algorithm to sort elements in a stack in either
: ascending/descending order, using only pop(), top(), push(), isEmpty(),
: isFull(). Do not use any auxiliary stacks or arrays.
: 2. 如何高效地用 two 堆栈 to simulate a 队列 要求O(1)时间内。
|
o********r
发帖数: 775 | 13 I think so (or O(logn)). It will be straightforward if it is O(n)
【在 D****g 的大作中提到】
:
: what does this exactly mean? O(1) space?
|
N*****N
发帖数: 1605 | 14 Don't know. Recurssion is the first thing come to my mind but also I noticed
that it need system stack. Not sure.
【在 D****g 的大作中提到】
:
: what does this exactly mean? O(1) space?
|
