# 狗家昂赛面筋

1.给一个只有0和1的矩阵，0表示墙，1表示路，给定起始、终点，求是否存在一条通路（深搜、广搜均可）
2. 白人小哥，一看就是超级聪明那种，题目太难叙述了，十分复杂就不写了，反正思考了半天才写出来
4. 人非常nice的国人大哥，出了一道比较简单的链表表示数字，然后求和，比如1->2->3 + 3->2->1（给定两个链表的长度是相同的），不需要写代码，只要尽可能多的给出方法。
5. 本来以为面试的是hr，结果又出了一道题。。。哭。是get字符串中连续出现超过三次的字母的起始index和结束index，比如aaabbb，返回{{0, 2}, {3, 5}}
follow up: 大意是返回所有的将连续出现三次的字符修改后的不超过三次的字符串，比如aaabbb->{ab, aab, abb, aabb} （回溯法）

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.