今天下午刚面的,一个小时后收到recruiter的onsite邀请
题目先是max stack,然后楼主说见过类似的,说了一下思路,然后面试官很果断的换了一个题。。当时五味陈杂,不知道是不是说错话了哈哈,好久不演生疏了。
问题来了,有点基于read4那个系列的题,但是考点不同,这个是考data structure,给你一个Stream的class,提供byte[] read(int n)的api,就是说给你一个stream的object的话里面有固定size的byte,你不用care它哪来的,你只能call这个read api来不断地读,当里面剩的小于n的时候,就会返回size小于n的byte【】,甚至空array。然后问题来了,基于这个Stream class,如何定义一个新的class MultiStream,实现如下api,byte[] read(int n), void add(Stream s), void remove(Stream s), 使用例子如下。有一些问题开始是要跟面试官澄清一下的,以此来决定你怎么选取data structure来实现这个,理想的是add read remove都是constant time。remove开始我犹豫了挺久,问清楚了是根据reference来remove,怎么handle remove了正要下一个read的stream怎么办(没啥问题,记得更新一个cur或则head listnode就行了)。最终我选用的是double linkedlist和hashmap的结合,和LRU的思路类似,只不过这个省了queue。
m.add(s1) s1 = [0, 1, 2, 3]
m.add(s2) s2 = [0, 1, 2]
m.read(4) -> [0, 1, 2, 3]
m.read(4) -> [0, 1, 2]
m.read(5) -> []
m.read(2) -> []