狗家昂赛面筋

地点在太阳谷cloud,一共五轮,本来说是4轮tech加一轮bq,结果莫名其妙面了我五轮tech。。。哭

1.给一个只有0和1的矩阵,0表示墙,1表示路,给定起始、终点,求是否存在一条通路(深搜、广搜均可)
follow up1: 写出路径
follow up2: 把1换成2,3,4,5…代表通过这个点的cost,求最短路径(我当时第一反应用深搜,征得面试官同意以后写了代码,后来面试完了想了一下应该是迪杰斯特拉。。。哭again)
2. 白人小哥,一看就是超级聪明那种,题目太难叙述了,十分复杂就不写了,反正思考了半天才写出来
3. 本质上还是迪杰斯特拉,要写出完整的代码(面试官对代码扣的非常仔细),输入的表示、用的数据结构什么的需要自己和面试官沟通,不清楚有没有follow up,写好代码就已经到时间了。。。哭
4. 人非常nice的国人大哥,出了一道比较简单的链表表示数字,然后求和,比如1->2->3 + 3->2->1(给定两个链表的长度是相同的),不需要写代码,只要尽可能多的给出方法。
follow up: 分别用递归和迭代写一下,然后对算法进行尽可能的优化
5. 本来以为面试的是hr,结果又出了一道题。。。哭。是get字符串中连续出现超过三次的字母的起始index和结束index,比如aaabbb,返回{{0, 2}, {3, 5}}
follow up: 大意是返回所有的将连续出现三次的字符修改后的不超过三次的字符串,比如aaabbb->{ab, aab, abb, aabb} (回溯法)

感觉狗家还是很看重写代码的基本功的,面试官会很认真的看你的代码,所以写的时候尽量要小心,思考所有的反例,同时明确时间复杂度和空间复杂度。

楼主能说说第五轮的followup是什么意思吗

抱歉题目叙述的有点问题,是连续出现次数大于等于三次,就是说在第一问的时候不是得到了{{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.

第五轮:
hr questions and googlyness.