Linkedin 电面

第一题： verify BST
第二题：implement Stack<T&

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

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

andomRemove如何实现O(1)?

简单测了测好像没啥问题

1. # No capacity limit, no error returned for empty pop attempts
   
2. from collections import defaultdict
   
3. from random import randrange
   
4. 
   
5. class RandomDeleteStack:
   
6.     def __init__(self):
   
7.         self.stack = []
   
8.         self.memo = defaultdict(list)
   
9.         self.numVals = 0
   
10. 
    
11.     def push(self, x):
    
12.         self.stack.append(x)
    
13.         self.memo[x].append(self.numVals)
    
14.         self.numVals += 1
    
15. 
    
16.     def pop(self):
    
17.         if self.numVals > 0:
    
18.             x = self.stack[-1]
    
19.             self.memo[x].pop()
    
20.             self.stack.pop()
    
21.             self.numVals -= 1
    
22. 
    
23.     def randomDelete(self):
    
24.         if self.numVals > 0:
    
25.             if self.numVals > 1:
    
26.                 t = randrange(self.numVals)
    
27.                 x = self.stack[t]
    
28.                 swapNum = self.stack[-1]
    
29.                 self.memo[swapNum].append(t)
    
30.                 self.stack[t] = swapNum
    
31.             self.numVals -= 1
    
32.             return self.stack.pop()
    

复制代码

daguanyuan 发表于 2018-1-11 09:04
直接设置为null 没有关系，平均下来就是O(1).不知道他能不能接受。如果要移动位置，肯定就不是常数能解决 ...

不好意思 回复的太草率了。可不可以这样：stack是一个双向链表，380结构之前存index,现在改为node 的引用，380里的的map存node 引用到380结构中的数组的index?这样既可以做random remove 也可以根据node 做删除操作（这支持pop的常数花费）

jerrytjz 发表于 2018-1-11 07:48
leetcode 380, 我自己做是用arraylist加hashmap实现的，但是这种做法delete需要用tail item代替deleted i ...

leetcode 380的那个数据结构就是我说的random remove collection, 在补充里面我已经澄清了;
这个数据结构不是用来存stack的值（换句话说，这个数据机构不是直接用来作为stack，因为按照你说的那个原因，顺序会变动。），而是用来存stack中已经有的element的索引值，push 操作会把新的index 添加到380的数据结构中，pop操作会到380的结构中删除当前stack的top的索引值；randomremove操作会去380中找到要删除的index,删除掉，然后回到stack，把index的对应的element设为null。所以stack的pop操作需要检查一下当前top的element 是不是null，平均下来，不影响pop的时间复杂度。

用random remove collection来存储stack中的有效数字的index, random remove collection的删除，查找和添加都是O(1)，所以stack的push 和pop操作也是1. 再看randomRemove, 因为在random remove collection的random remove 的操作是O（1）,所以在它操作完这一步骤，顺便返回删除的值，此时的值就是对应stack的index, 把对应的index的值设为null.
想了很多方法才最后想到用random remove collection的，不知道这中间有没有错。如果在店面，我肯定挂，一下子想不太到。

补充内容 (2018-1-11 07:34):
random remove collection 就是 leetcode 380 要求设计的数据结构

daguanyuan 发表于 2018-1-11 07:23
用random remove collection来存储stack中的有效数字的index, random remove collection的删除，查找和添加 ...

leetcode 380, 我自己做是用arraylist加hashmap实现的，但是这种做法delete需要用tail item代替deleted item。这就不适用于Stack。

请教random remove collection是什么？有什么连接吗？
另外，是先random选择一个index，然后再O(1) delete吗? 你提到“对应的index值设为null”，那之后的pop()到这个null的位置是不是要继续pop()直到不是null？这样pop()就不是O(1)了。

daguanyuan 发表于 2018-1-11 07:56
leetcode 380的那个数据结构就是我说的random remove collection, 在补充里面我已经澄清了;
这个数据结 ...

非常感谢！我还有个问题是，如果random remove collection用作index of stack的处理，Stack本身需要用什么data structure 存Element？如果只是普通的Stack structure或者LinkedList，那么index在pop后会整体更新；如果Stack本事是ArrayList，那就直接用两个头和尾的index指针就可以了，不再需要random remove collection，removeRandom只需要找到 index=start+random.nextInt(curSize),然后标记Element为null就够了。

我在面试时候说了这个想法，可是面试官意思是这样Stack中间可能会都是null，导致pop不是O(1).

jerrytjz 发表于 2018-1-11 08:24
非常感谢！我还有个问题是，如果random remove collection用作index of stack的处理，Stack本身需要用什 ...

直接设置为null 没有关系，平均下来就是O(1).不知道他能不能接受。如果要移动位置，肯定就不是常数能解决了。记得给我加米啊：）

第二题如果是用C++的话 感觉可以用list<T>来存 删除的话可以获取一个随机数 然后erase掉这个iterator

fr42k 发表于 2018-1-11 09:53
第二题如果是用C++的话 感觉可以用list来存 删除的话可以获取一个随机数 然后erase掉这个iterator

list内部实现是双向链表， 删除操作本身是o(1)，
产生随机数后locate那个iterator节点其实需要o(n)