推荐:数据科学课程和书籍清单以及培训讲座


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 682|回复: 10
收起左侧

[2017/08/08] LinkedIn电面面经

[复制链接] |试试Instant~ |关注本帖
xuepanchen 发表于 2017-8-11 04:49:41 | 显示全部楼层 |阅读模式

2017(7-9月) 码农类 硕士 全职@Linkedin - 内推 - 技术电面 |Other在职跳槽

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

x
朋友的内推,面的是Infra组。面试官两位国人小哥,人很好,一直给提示,可惜自己面的一般。

1. 介绍现在自己做的事,Challenging Project。
2. What is Virtual Memory。
3. Coding。让你设计一个MaxStack,要求实现以下功能。
class MaxStack {
    int Pop(); // Pop the value on top of the stack;
    void Push(int); // Push a new value into the stack;
    int Peek(); // Return the value on top of the stack;

    int PopMax(); // Pop the max value in the stack;
    int PeekMax(); // Return the max value in the stack;
}

自己一开始没有认真读题,以为和LC上的原题类似,就开始说解法。说到一半发现不对,连忙改口。这题其实不难,用一个linked_list按照插入的顺序来存所有插入的数字,这样方便前三个操作。然后再用一个priority_queue来存有序的数字,这里priority_queue可以存linked_list的指针,也就是iterator,这样方便在进行PopMax的时候快速在linked_list里找到要删除的数据。这个做法和LRU很相似。
. 1point 3acres 璁哄潧
问了一下各个操作的时间复杂度,然后简单实现了一下Push()和PopMax()。自己面到后来也有点懵了,感觉辜负了两位国人小哥的帮助。

也是给大家提个醒,如果遇到貌似原题,不要高兴太早冲昏头脑。一定要把题目看清,看看有什么不同,想清楚了再继续。

祝各位找工工作,或是学习顺利。
FightForTomo 发表于 2017-8-11 05:06:39 | 显示全部楼层
你做复杂了吧。
他家2018new grad什么时候开?
回复 支持 反对

使用道具 举报

say543 发表于 2017-8-11 15:08:21 | 显示全部楼层
楼主这个solution 因该没啥问题 所以pop Max logn 的要求就行了?
回复 支持 反对

使用道具 举报

kqxqx 发表于 2017-8-12 01:28:57 | 显示全部楼层
跟层主类似的思路,用两个数据结构 list<int> 和 multimap<int, list<int>::iterator>,这样peek, peekMax都是O(1),push/pop/popMax都是o(log(n))
回复 支持 反对

使用道具 举报

 楼主| xuepanchen 发表于 2017-8-12 02:49:36 | 显示全部楼层
say543 发表于 2017-8-11 15:08
楼主这个solution 因该没啥问题 所以pop Max logn 的要求就行了?

PopMax的复杂度是O(1)吧
回复 支持 反对

使用道具 举报

 楼主| xuepanchen 发表于 2017-8-12 02:50:24 | 显示全部楼层
FightForTomo 发表于 2017-8-11 05:06.1point3acres缃
你做复杂了吧。
他家2018new grad什么时候开?

有什么别的方便的做法吗?
一般new grad都是九月开始吧,我也不是很清楚他们家是怎么样的。
回复 支持 反对

使用道具 举报

FightForTomo 发表于 2017-8-12 02:56:41 | 显示全部楼层
xuepanchen 发表于 2017-8-12 02:50
有什么别的方便的做法吗?
一般new grad都是九月开始吧,我也不是很清楚他们家是怎么样的。

没太看出来和原题不一样在哪唉。. more info on 1point3acres.com
你要是再用一个栈来维持到当前为止的最大值不就O(1)了么?
记得还有一个用一个栈就能实现出来的方法。或者C++里没有内置栈?不知道。
回复 支持 反对

使用道具 举报

jingshihao 发表于 2017-8-12 03:50:43 | 显示全部楼层
FightForTomo 发表于 2017-8-12 02:56
没太看出来和原题不一样在哪唉。
你要是再用一个栈来维持到当前为止的最大值不就O(1)了么?
记得还有一 ...

这个题要求pop max,用栈做不能在O(1) pop max,原题只需要get max
回复 支持 反对

使用道具 举报

FightForTomo 发表于 2017-8-12 04:32:25 | 显示全部楼层
jingshihao 发表于 2017-8-12 03:50
这个题要求pop max,用栈做不能在O(1) pop max,原题只需要get max

哦,这样。
回复 支持 反对

使用道具 举报

kangxinjob 发表于 2017-8-12 12:57:12 | 显示全部楼层
这个题用priority_queue 做不出吧? 如果你pop() 一个值从linkedlist,如果这个值不是最大值。你无法从priority_queue中删除这个值。好像要用双向linked_list和treemap来做,treemap的value是list的节点。不知道说的对不对,请指正。
回复 支持 反对

使用道具 举报

endofunctor 发表于 4 天前 | 显示全部楼层
两个实现都可以吧。。。
LC那个做法其实也可以用,popmax的时候用一个buffer保存在max element后面的元素,pop出来之后再push回去。这种方法可以用来应付popmax操作少的情况(popmax最坏O(N)时间复杂度,push pop getmax均为O(1));list+multiset的做法可以用来应付popmax操作比较多,push pop操作比较少的情况(getmax O(1), push/pop/popmax O(lgN))
回复 支持 反对

使用道具 举报

本版积分规则

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-8-20 20:00

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表