https://docs.google.com/document/d/1qxA2wps0IhVRWULulQ55W4SGPMu2AE5MkBB37h8Dr58
第四轮：白人小哥，google工作5年，之前3个面试官好像都是swe，这个是seti，上来自我介绍了一下，然后直接开始上题目，skip iterator,定义个class如下：
class SkipIterator {
public SkipIterator(Iterator itr);
boolean hasNext();
Integer next();
void skip(int num);
}
传入的迭代器让我看作是在一个List<Integer>上面的迭代器，主要说下skip函数，输入参数是个int，表示下一个数字等于num的需要被跳过，就是当作这个list中下一个num不存在，skip可能被多次调用,skip(5),skip(5)表示后面的两个5都不要了。
思路：
当面试官说skip可以多次调用时直接想到的用map存放skip调用的频率，所以思路也很直接Map<Integer, Integer>，key是需要被跳过的数字，value是接下来多少个key需要被跳过，然后用一个Integer curr缓冲下一个integer，skip每调用一次频率加一，每跳过一次key，key的value减一。然后我设计的iterator中是next中call hasNext，hasNext负责找下一个合法元素，但是正确解法应该用另一个函数去专门找下一个合法元素。
估计是挂在了这一轮，当时代码写得有点凌乱，也没有口头跑一下保证一定work，写完面试官直接让我想test case，根本不让double check，估计是因为他是seti，比较看中这点。
正确解法应该用一个函数去专门找下一个合法元素：
class SkipIterator {
private Iterator<Integer> itr;
private boolean hasNext;
private Integer nextElement;
private Map<Integer, Integer> map = new HashMap<>();
public SkipIterator(Iterator<Integer> itr) {
this.itr = itr;
findNext();
}
public boolean hasNext() {
return hasNext;
}
public Integer next() {
if(!hasNext) return null;
Integer tmp = nextElement;
findNext();
return tmp;
}
public void skip(int num) {
if(hasNext) {
if(nextElement == num) {
findNext();
} else {
map.put(num, map.getOrDefault(num, 0) + 1);
}
}
}
private void findNext() {
hasNext = false;
nextElement = null;
while(itr.hasNext()) {
Integer e = itr.next();
if(map.containsKey(e)) {
map.put(e, map.get(e) - 1);
if(map.get(e) == 0) map.remove(e);
} else {
hasNext = true;
nextElement = e;
return;
}
}
}
}
