10月28,K神开课讲数据科学,你来吗?


一亩三分地论坛

 找回密码
 获取更多干活,快来注册
Babeltime游戏工作室招工程师、美术和策划
Tubi TV招安卓、前端和机器学习工程师
把贵司招聘信息放这里
查看: 1285|回复: 15
收起左侧

[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。. from: 1point3acres.com/bbs
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;. Waral 鍗氬鏈夋洿澶氭枃绔,

    int PopMax(); // Pop the max value in the stack;
    int PeekMax(); // Return the max value in the stack;
}. 1point 3acres 璁哄潧

自己一开始没有认真读题,以为和LC上的原题类似,就开始说解法。说到一半发现不对,连忙改口。这题其实不难,用一个linked_list按照插入的顺序来存所有插入的数字,这样方便前三个操作。然后再用一个priority_queue来存有序的数字,这里priority_queue可以存linked_list的指针,也就是iterator,这样方便在进行PopMax的时候快速在linked_list里找到要删除的数据。这个做法和LRU很相似。

问了一下各个操作的时间复杂度,然后简单实现了一下Push()和PopMax()。自己面到后来也有点懵了,感觉辜负了两位国人小哥的帮助。
. from: 1point3acres.com/bbs
也是给大家提个醒,如果遇到貌似原题,不要高兴太早冲昏头脑。一定要把题目看清,看看有什么不同,想清楚了再继续。
-google 1point3acres
祝各位找工工作,或是学习顺利。

评分

1

查看全部评分

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. 1point 3acres 璁哄潧
楼主这个solution 因该没啥问题 所以pop Max logn 的要求就行了?
. more info on 1point3acres.com
PopMax的复杂度是O(1)吧
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

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

没太看出来和原题不一样在哪唉。
你要是再用一个栈来维持到当前为止的最大值不就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 发表于 2017-8-16 13:33:31 | 显示全部楼层
两个实现都可以吧。。。
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))
回复 支持 反对

使用道具 举报

LZJ981 发表于 2017-8-24 12:36:28 | 显示全部楼层
kangxinjob 发表于 2017-8-12 12:57
这个题用priority_queue 做不出吧? 如果你pop() 一个值从linkedlist,如果这个值不是最大值。你无法从prio ...
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
Java的PriorityQueue有原生的remove(),复杂度是O(logn). 面试官不给用的话自己实现也不是特别复杂~
回复 支持 反对

使用道具 举报

sansi 发表于 2017-8-30 13:34:43 | 显示全部楼层
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 {
  2.         ListNode head;
  3.         ListNode tail;
  4.         TreeMap<Integer, LinkedList<ListNode>> treeMap;. more info on 1point3acres.com
  5.         int size;
  6.         public MaxStack() {
  7.                 head = new ListNode(0);
  8.                 tail = new ListNode(0); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  9.                 head.next = tail;. from: 1point3acres.com/bbs
  10.                 tail.prev = head;
  11.                 treeMap = new TreeMap<Integer, LinkedList<ListNode>>();
  12.                 size = 0;
  13.         }
  14.        
  15.         public int pop() {
  16.                 if (tail.prev == head) {. 1point 3acres 璁哄潧
  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);. Waral 鍗氬鏈夋洿澶氭枃绔,
  26.                 }
  27.                 size--; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  28.                 return node.val;
  29.         }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  30.         .1point3acres缃
  31.         public void push(int x) {
  32.                 ListNode node = new ListNode(x);
  33.                 ListNode prev = tail.prev;
  34.                 prev.next = node;
  35.                 node.prev = prev;
  36.                 node.next = tail;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  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++;. from: 1point3acres.com/bbs
  43.         }
  44.         . more info on 1point3acres.com
  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.
  52.                 if (treeMap.get(max).size() == 0) {
  53.                         treeMap.remove(max);
  54.                 }
  55.                 ListNode prev = node.prev;
  56.                 ListNode next = node.next;
  57.                 prev.next = next;
  58.                 next.prev = prev;
  59.                 node.prev = null;
  60.                 node.next = null;
  61.                 size--;
  62.                 return max; //or node.val;
  63.         }
  64.        
  65.         public int peekMax() {
  66.                 return treeMap.lastKey();. 1point3acres.com/bbs
  67.         }
  68.        
  69.         public int size() {
  70.                 return size;
  71.         }
  72.        
  73.         public boolean isEmpty() {
  74.                 return size == 0;. 鍥磋鎴戜滑@1point 3 acres
  75.         }
  76. }
    . 鍥磋鎴戜滑@1point 3 acres

  77. class ListNode {. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  78.         int val;
  79.         ListNode prev;
  80.         ListNode next;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  81.         public ListNode (int val) {
  82.                 this.val = val;
  83.         }
复制代码
回复 支持 反对

使用道具 举报

LZJ981 发表于 2017-8-31 09:33:03 | 显示全部楼层
sansi 发表于 2017-8-30 13:34
priorityQueue 的remove() 是remove 栈顶元素,时间复杂度是log(n)。 但当从那个正常的stack里pop() 的时 ...
. 1point3acres.com/bbs
赞!对,正常来说remove priorityQueue任意元素是O(n),是因为找到该元素花费O(n),再删除该元素花费O(logn),总的来说还是O(n). 但是该题我们可以省去找到该元素的花费O(n), 直接删除即可,也就是O(logn). 错误的话还请指正
回复 支持 反对

使用道具 举报

sansi 发表于 2017-8-31 12:50:03 | 显示全部楼层
LZJ981 发表于 2017-8-31 09:33. 鍥磋鎴戜滑@1point 3 acres
赞!对,正常来说remove priorityQueue任意元素是O(n),是因为找到该元素花费O(n),再删除该元素花费O(lo ...

对的。remove 任意元素理论上可以做到O(log(n)), 但Java 自带的priorityQueue remove(Object E) 的复杂度就是O(n). 参见Implementation note https://docs.oracle.com/javase/7 ... /PriorityQueue.html。 要做到O(log(n)) 得自己实现。
回复 支持 反对

使用道具 举报

toazores 发表于 2017-9-10 07:19:53 | 显示全部楼层
感谢楼主分享, 楼主店面是什么环境里coding?是google docs吗,还是什么?
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-9-20 13:51

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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