MathWorks EDG 电面

楼主介绍项目的时候是自己选一个介绍吗

codeyy 发表于 2019-11-16 10:45
第一个题，感觉可以这样。

当enqueue时，交替地向两个stack push。

嗯。不错的想法！

yingnanzhou 发表于 2019-11-16 11:28
楼主介绍项目的时候是自己选一个介绍吗

是啊，字数补丁呀呀呀呀呀呀

想问问楼主，电面挂了会单独发email吗？我上周四面的今天发邮件告诉我 status update 然后我去applied job 里查发现 今天 update 了一下， application status 是 inprocess  job availability 是 open 这算是过了吗？

占个坑再回来看题！

codeyy 发表于 2019-11-16 10:45
第一个题，感觉可以这样。

当enqueue时，交替地向两个stack push。

穷人求加米。。。
没有太get到层主的点，但是受到了启发，queue::push和queue::pop的均摊时间复杂度都为O(1)，空间也不会超出元素个数
思路：同样的两个栈，一个pushStack，仅用于queue::push的时候将元素压入栈顶；另一个popStack，仅用于queue::pop，当调用queue::pop时，若popStack为空，则先将pushStack中的元素全部倒入popStack，再将popStack的栈顶出栈；
下面是模拟过程
queue::push 1: pushStack(1) popStack()
queue::push 2: pushStack(1, 2) popStack()
queue::push 3: pushStack(1, 2, 3) popStack()
queue::pop: pushStack() popStack(3, 2, 1) => pushStack() popStack(3, 2)
queue::push 4: pushStack(4) popStack(3, 2)
queue::pop: pushStack(4) popStack(3)
queue::pop: pushStack(4) popStack()
queue::pop: pushStack() popStack(4) => pushStack() popStack()

每个元素只会进出pushStack和popStack各一次，因此时间复杂度如开头所提