抱歉题目叙述的有点问题,是连续出现次数大于等于三次,就是说在第一问的时候不是得到了{{0,2},{3,5}}这两个嘛,可以理解成连续出现大于等于三次都是不合法的,题目让你输出所有合法的可能字符串。所以follow up就是先调用第一问得出的函数得到这个vector of pairs(lz用c++,python就是list of tuple这样),然后遍历一遍原来的字符串,当index属于得到的不合法范围的时候用backtrack继续,因为有两种可能嘛,要么只出现一次,要么最多连续出现两次。
第一轮:
given a 2D matrix containing X, Y and 0. Find the shortest distance between any X and Y.
solved using bfs o(mmnn) and suggested early pruning ideas. coded and then interviewer asked further optimization. suggested a dfs and dp approach to bring it down to o(mn) didnt have time to code it.
第二轮:
Given a number N find the first N non confusing numbers.
suggested a check function for every number until we have N non confusing numbers. follow up to improve this included bactracking to generate confusing number till N. did not code it out of time.
第三轮:
Implement a generic queue using linked list.
find the maximal regtangle in a histogram.
implemented a queue. suggested the optimal solution with monotonically increasing stack for second question but didn’t have time to code
第四轮:
Given a large file, process it in chunks and omit the black listed words from the file.
added as many cases as he asked until we ran out of time.