脸熟二面新鲜出炉

刚刚结束的二轮电面,竟然没打视频,害得我调了半天还整理了发型
烙印,人挺好的,两道题

第一个题 是个 insert delete randomset 变种, 具体叫做 phone number waitlist 就是要first come first serve 光解释就花了半天时间, 通话质量真的不好, 设计一个class 比如说输入一个 string, 比如’666-55-444’’, 要实现一个 add函数 ,就把它加进去,你可以假设没有重复, 然后实现一个poll() 函数, 把第一个放进去的string poll 出来, 最后还有一个remove函数, remove 当前存的任意一个 string, 举个例子
add(‘233’)
add(‘873’)
add(‘888’)
remove(‘873’)
poll(): 输出233
poll(): 输出888
add(‘253’)
然后我只把优化了remove部分优化了, 但是相应的就把poll()给变成O(n)了 不过还是好一些
第二题 就是 copy tree 设计一个TreeNode, TreeNode直接调用 root.copy() 返回一个tree shallow copy 就可以
第二题时间不够了 就剩不到10分钟,于是就直接转成list再重建了

请问楼主remove 是怎么优化的啊

问下第二题有原题嘛

不知道 直接inplace 建树还没见过, 应该可以用 hashtable+dfs?

我是在后边新加了个0, 然后每次和该删除的元素换 但是这样最坏的情况就是 poll()的时候也有好多0 操作就变成O(n)了

第一题就是简化的lru吧,建个double linkedlist,所有操作一个都能O(1)了

lz问了面试官多久会有消息了么

lru 怎么random access 啊

楼主用的是arraylist吗

哇跟我的一面一样的题目,但面我的是美国小哥