整理过谷歌高频面筋

求加米

1）

扫地机器人

给一个扫地机器人，还有三个function：

move(), which returns boolean value. 涓€浜�-涓夊垎-鍦帮紝鐙鍙戝竷

turn_left(k), which make robot turns left k times.

turn_right(k), which make robot turns right k times.

Design an algorithm to make robot clean up all room. Timecomplexity, linear in term of room space.

一个机器人在一个未知的房间，自己也不知道自己一开始在什么位置。提供了四个API：

turnRight，turnLeft： 向右，向左转

move：向目前的方向走一格，不是墙返回true，是墙就留在在原地，返回false,

clean：清理当前格子。

鏉ユ簮涓€浜�.涓夊垎鍦拌鍧�.

用这些API来清理整个未知的房间，最后返回原点。. more info on 1point3acres.com

2）

给你一个迷宫，里面有很多门，很多房间，房间里面有很多锁，求能不能到达终点。corner case是你现在到了一个门可能打不开，可是未来如果拿到了这个门的钥匙要回去那个门打开说不定能到终点。所以要dfs+2个map记录拿到的钥匙，和每个门需要什么钥匙（一个门可以有不同的钥匙）

3）

字典中所有单词长度为5而且每个单词都没有重复字母，实现一个function可以生成下一个猜测的词。就是每次你猜一个词，然后会得到有几个字母匹配的结果，然后你再猜下一个词，直到猜中为止，希望能尽可能的少猜

. visit 1point3acres.com for more.

. 涓€浜�-涓夊垎-鍦帮紝鐙鍙戝竷

4）

Choose a random point from one single rectangle. Choose a random point from multiple rectangles, if there isno overlapping among them. Choose a random point from multiple rectangles, if there isoverlapping among them.

5）

设计一个class存储股票价格。支持update某个timestamp的价格。query目前价格以及历史最高价格。

6）

定义说两个string是buddies如果他们只有两个字母不一样且这两个字母交换后就可以变成一样的，比如converse和conserve这样，然后让写一个func判断两个string是不是buddies，楼主就给了一个O(n)的算法，写完之后小哥又问我要测我的代码的话我会选哪些testcase

7）

给一个word list，有一个char stream, 如果stream中出现list中的word要return true。

8）. 鍥磋鎴戜滑@1point 3 acres

<span style="font-size: 10pt; font-family: Arial;" data-sheets-value="{"1":2,"2":"(1) 给定一个List of Node，每个node都是双向链表的node。比如 (NN NNN N N )这个list中每个N都是一个Node，但是可以看到并不是所有的node都是连起来的，求这个list中connected components的个数，这个例子中答案就是4，因为有两组连着的node，加上两个单独的node。（给的node顺序都是随机的，不一定是像图中那样顺序连着的，每个node都可能和任一node连着）。"}" data-sheets-userformat="{"2":4480,"10":2,"11":4,"15":"arial,sans,sans-serif"}">给定一个List of Node，每个node都是双向链表的node。比如 (N<->N N<->N<->N N N )这个list中每个N都是一个Node，但是可以看到并不是所有的node都是连起来的，求这个list中connected components的个数，这个例子中答案就是4，因为有两组连着的node，加上两个单独的node。（给的node顺序都是随机的，不一定是像图中那样顺序连着的，每个node都可能和任一node连着）。