Airbnb 2018年春季E6 package

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货

最近看过此主题的会员

E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
查看: 2743|回复: 19
收起左侧

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

[复制链接] |试试Instant~ |关注本帖
我的人缘0
xuepanchen 发表于 2017-8-11 04:49:41 | 显示全部楼层 |阅读模式
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  100% (34)
 
 
0% (0)  踩

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

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

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

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;. 1point 3acres 论坛
    int PeekMax(); // Return the max value in the stack;
}
. From 1point 3acres bbs
自己一开始没有认真读题,以为和LC上的原题类似,就开始说解法。说到一半发现不对,连忙改口。这题其实不难,用一个linked_list按照插入的顺序来存所有插入的数字,这样方便前三个操作。然后再用一个priority_queue来存有序的数字,这里priority_queue可以存linked_list的指针,也就是iterator,这样方便在进行PopMax的时候快速在linked_list里找到要删除的数据。这个做法和LRU很相似。

问了一下各个操作的时间复杂度,然后简单实现了一下Push()和PopMax()。自己面到后来也有点懵了,感觉辜负了两位国人小哥的帮助。

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

. more info on 1point3acres祝各位找工工作,或是学习顺利。

评分

参与人数 1大米 +1 收起 理由
toazores + 1 感谢分享!

查看全部评分


上一篇:yelp skype interview
下一篇:[2017/08/10] Two Sigma电面面经

本帖被以下淘专辑推荐:

我的人缘0
FightForTomo 发表于 2017-8-11 05:06:39 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  53% (727)
 
 
46% (642)  踩
你做复杂了吧。. 围观我们@1point 3 acres
他家2018new grad什么时候开?
回复

使用道具 举报

我的人缘0
say543 发表于 2017-8-11 15:08:21 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  83% (31)
 
 
16% (6)  踩
楼主这个solution 因该没啥问题 所以pop Max logn 的要求就行了?
回复

使用道具 举报

我的人缘0
kqxqx 发表于 2017-8-12 01:28:57 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (38)
 
 
0% (0)  踩
跟层主类似的思路,用两个数据结构 list<int> 和 multimap<int, list<int>::iterator>,这样peek, peekMax都是O(1),push/pop/popMax都是o(log(n))
回复

使用道具 举报

我的人缘0
 楼主| xuepanchen 发表于 2017-8-12 02:49:36 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (34)
 
 
0% (0)  踩
say543 发表于 2017-8-11 15:08
楼主这个solution 因该没啥问题 所以pop Max logn 的要求就行了?

PopMax的复杂度是O(1)吧
回复

使用道具 举报

我的人缘0
 楼主| xuepanchen 发表于 2017-8-12 02:50:24 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (34)
 
 
0% (0)  踩
FightForTomo 发表于 2017-8-11 05:06
你做复杂了吧。
他家2018new grad什么时候开?

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

使用道具 举报

我的人缘0
FightForTomo 发表于 2017-8-12 02:56:41 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  53% (727)
 
 
46% (642)  踩
xuepanchen 发表于 2017-8-12 02:50
有什么别的方便的做法吗?
一般new grad都是九月开始吧,我也不是很清楚他们家是怎么样的。
.1point3acres网
没太看出来和原题不一样在哪唉。
你要是再用一个栈来维持到当前为止的最大值不就O(1)了么?
记得还有一个用一个栈就能实现出来的方法。或者C++里没有内置栈?不知道。
回复

使用道具 举报

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

这个题要求pop max,用栈做不能在O(1) pop max,原题只需要get max
Mobile Apps Category (English)728x90
回复

使用道具 举报

我的人缘0
FightForTomo 发表于 2017-8-12 04:32:25 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  53% (727)
 
 
46% (642)  踩
jingshihao 发表于 2017-8-12 03:50
这个题要求pop max,用栈做不能在O(1) pop max,原题只需要get max
. visit 1point3acres for more.
哦,这样。
回复

使用道具 举报

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

使用道具 举报

我的人缘0
endofunctor 发表于 2017-8-16 13:33:31 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  95% (21)
 
 
4% (1)  踩
两个实现都可以吧。。。
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))
回复

使用道具 举报

我的人缘0
LZJ981 发表于 2017-8-24 12:36:28 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (39)
 
 
0% (0)  踩
kangxinjob 发表于 2017-8-12 12:57
这个题用priority_queue 做不出吧? 如果你pop() 一个值从linkedlist,如果这个值不是最大值。你无法从prio ...

Java的PriorityQueue有原生的remove(),复杂度是O(logn). 面试官不给用的话自己实现也不是特别复杂~
回复

使用道具 举报

我的人缘0
sansi 发表于 2017-8-30 13:34:43 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (34)
 
 
0% (0)  踩
LZJ981 发表于 2017-8-24 12:36 来源一亩.三分地论坛.
Java的PriorityQueue有原生的remove(),复杂度是O(logn). 面试官不给用的话自己实现也不是特别复杂~

priorityQueue 的remove() 是remove 栈顶元素,时间复杂度是log(n)。 但当从那个正常的stack里pop() 的时候,对应的元素也要在priorityQueue里删掉,需要调用remove(Element),这个操作时间复杂度是O(n)的。
用linkedList +TreeMap,key是数字,value是ListNode的话,无法处理数字重复的时候,所以value得改成List<ListNode>.
Code 如下,欢迎指正:
  1. class MaxStack {. From 1point 3acres bbs
  2.         ListNode head;
  3.         ListNode tail;
  4.         TreeMap<Integer, LinkedList<ListNode>> treeMap;
  5.         int size;
  6.         public MaxStack() {.留学论坛-一亩-三分地
  7.                 head = new ListNode(0);. 围观我们@1point 3 acres
  8.                 tail = new ListNode(0);
  9.                 head.next = tail;.留学论坛-一亩-三分地
  10.                 tail.prev = head;
  11.                 treeMap = new TreeMap<Integer, LinkedList<ListNode>>();
  12.                 size = 0;
  13.         }
  14.        
  15.         public int pop() {. from: 1point3acres
  16.                 if (tail.prev == head) {
  17.                         return 0; //no elements to pop out.
  18.                 }
  19.                 ListNode node = tail.prev;
  20.                 ListNode prev = node.prev;
  21.                 prev.next = tail;
  22.                 tail.prev = prev;. 留学申请论坛-一亩三分地
  23.                 treeMap.get(node.val).removeLast();//First in last out. the same order as the usual stack presented by the linkedList. O(1) time.
  24.                 if (treeMap.get(node.val).size() == 0) {
  25.                         treeMap.remove(node.val);.本文原创自1point3acres论坛
  26.                 }. From 1point 3acres bbs
  27.                 size--;
  28.                 return node.val;
  29.         }. From 1point 3acres bbs
  30.        
  31.         public void push(int x) {. 围观我们@1point 3 acres
  32.                 ListNode node = new ListNode(x);
  33.                 ListNode prev = tail.prev;
  34.                 prev.next = node;.1point3acres网
  35.                 node.prev = prev;
  36.                 node.next = tail; 来源一亩.三分地论坛.
  37.                 tail.prev = node;
  38.                 if (!treeMap.containsKey(node.val)) {. 牛人云集,一亩三分地
  39.                         treeMap.put(node.val, new LinkedList<ListNode>());
  40.                 }
  41.                 treeMap.get(node.val).add(node);
  42.                 size++;
  43.         }
  44.        
  45.         public int peek() {
  46.                 return tail.prev.val;
  47.         }
  48.         .1point3acres网
  49.         public int popMax() {
  50.                 int max = treeMap.lastKey();
  51.                 ListNode node = treeMap.get(max).removeLast(); //both removeLast() and removeFirst() are fine here.. visit 1point3acres for more.
  52.                 if (treeMap.get(max).size() == 0) {
  53.                         treeMap.remove(max);
  54.                 }. 1point3acres
  55.                 ListNode prev = node.prev;
    . visit 1point3acres for more.
  56.                 ListNode next = node.next;
  57.                 prev.next = next;
  58.                 next.prev = prev;
  59.                 node.prev = null;. from: 1point3acres
  60.                 node.next = null;. Waral 博客有更多文章,
  61.                 size--;. from: 1point3acres
  62.                 return max; //or node.val;. from: 1point3acres
  63.         }
  64.        
  65.         public int peekMax() {
  66.                 return treeMap.lastKey();
  67.         }
  68.         . 牛人云集,一亩三分地
  69.         public int size() {
  70.                 return size;
  71.         }
  72.        
  73.         public boolean isEmpty() {
  74.                 return size == 0;
  75.         }
  76. }

  77. class ListNode {
  78.         int val;
  79.         ListNode prev;
  80.         ListNode next;
  81.         public ListNode (int val) {
  82.                 this.val = val;
  83.         }
复制代码
回复

使用道具 举报

我的人缘0
LZJ981 发表于 2017-8-31 09:33:03 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (39)
 
 
0% (0)  踩
sansi 发表于 2017-8-30 13:34
priorityQueue 的remove() 是remove 栈顶元素,时间复杂度是log(n)。 但当从那个正常的stack里pop() 的时 ...

赞!对,正常来说remove priorityQueue任意元素是O(n),是因为找到该元素花费O(n),再删除该元素花费O(logn),总的来说还是O(n). 但是该题我们可以省去找到该元素的花费O(n), 直接删除即可,也就是O(logn). 错误的话还请指正
回复

使用道具 举报

我的人缘0
sansi 发表于 2017-8-31 12:50:03 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (34)
 
 
0% (0)  踩
LZJ981 发表于 2017-8-31 09:33
赞!对,正常来说remove priorityQueue任意元素是O(n),是因为找到该元素花费O(n),再删除该元素花费O(lo ...
. 1point 3acres 论坛
对的。remove 任意元素理论上可以做到O(log(n)), 但Java 自带的priorityQueue remove(Object E) 的复杂度就是O(n). 参见Implementation note https://docs.oracle.com/javase/7 ... /PriorityQueue.html。 要做到O(log(n)) 得自己实现。
回复

使用道具 举报

我的人缘0
toazores 发表于 2017-9-10 07:19:53 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (1)
 
 
0% (0)  踩
感谢楼主分享, 楼主店面是什么环境里coding?是google docs吗,还是什么?
回复

使用道具 举报

我的人缘0
jessebest 发表于 2017-9-25 12:09:01 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  70% (12)
 
 
29% (5)  踩
请问java里面,在priorityqueue里面存的pair, 是integer 和 listnode吗?如果是这样,当pop max的时候,要把这个listnode删掉。 如果是singly linked list, 就要遍历一下找node?如果是doubly linked list, 就是O(1)删除?
回复

使用道具 举报

我的人缘0
xinzh7868 发表于 2017-10-3 04:02:29 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (1)
 
 
0% (0)  踩
MaxStack 这一题用BST的思想,用treemap写。不会的话就写一个node带5个指针,自建BST。
回复

使用道具 举报

我的人缘0
zws1818918 发表于 2017-12-7 15:15:29 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  76% (19)
 
 
24% (6)  踩
sansi 发表于 2017-8-30 13:34
priorityQueue 的remove() 是remove 栈顶元素,时间复杂度是log(n)。 但当从那个正常的stack里pop() 的时 ...

. more info on 1point3acres这里的peekmax是O(logn) 对吧?
回复

使用道具 举报

我的人缘0
jwssdwed 发表于 2018-1-16 03:06:46 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  83% (26)
 
 
16% (5)  踩
sansi 发表于 2017-8-30 13:34
priorityQueue 的remove() 是remove 栈顶元素,时间复杂度是log(n)。 但当从那个正常的stack里pop() 的时 ...

我用doublelinkedlist和heap不就可以做到remove是logn嘛???
. 1point 3acres 论坛
有错希望指正
回复

使用道具 举报

游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

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

custom counter

GMT+8, 2018-7-17 17:29

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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