Google新加坡Office Hangout面背靠背面

新加坡谷歌第一次hangout interviews，背靠背两轮各45min，刚刚面完，如果有next step的话再约接下来两轮。

第一位面试官华人兄弟，直入主题没让自我介绍。

设计一个能Snapshot的Map类，有get(), put()这两个map的基础功能，同时也有 int snapshot() 这个function，记录当前的snapID下的map的状态，就像截个图（想象一下），返回的是当前的snapID，用一个count来计数就行。
接着就是实现一个getSnapShotValue函数，输入key和snapID，要返回这个snapID对应的key对应

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

比较紧张吧，注重交流，谈论思路是最重要的，这次面试学到了。不知道有没有后面面试的机会了，保佑。

最后作小诗一首吧，送给有缘人：

尚遇潇湘谷
天道有九歌
保境安何求
佑道谁无过


补充内容 (2019-2-20 05:46):
Update一下，一周后收到了拒信，说实话有点不甘心因为题目都做出来了，和谷歌无缘了吧

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

coconickking 发表于 2019-2-11 14:24
有一个小问题，第二题如果用deque维持单调盏，push时worst case不是O（n）吗

看均摊时间复杂度是O(1)的

hi 祝顺利！

有一个小问题，第二题如果用deque维持单调盏，push时worst case不是O（n）吗

单调栈，需要维护两个吧？一个大的，一个小的。

大的单调栈，保存递减的（<=栈首的），如果当前pop的值是最大的，则这个栈也需要pop。

zdzapple 发表于 2019/02/11 14:38:41
单调栈，需要维护两个吧？一个大的，一个小的。

大的单调栈，保存递减的（<=栈首的），如果当前pop的值是最大的，则这个栈也需要pop。

对的 you are right

coconickking 发表于 2019/02/11 14:24:02
有一个小问题，第二题如果用deque维持单调盏，push时worst case不是O（n）吗

我也是这么觉得 当时也和小哥解释了，但是我想不出更好的方法了……

上天保佑，谷歌求过！