转发: 狗狗 昂赛

  1. 给定一些 string pair,比如 mammal / dog, mammal / cat, dog / bulldog, dog / terrier。其实后者是前者的一些子类,要求按层级输出基于这些关系。比如
mammal
     dog
          bulldog
          terrier
     cat

其中输入可以保证某个类,不会被属于两个类,比如不会出现 [mammal / cat, pet / cat],因为此时 cat 属于两个类

  1. 给定一些单词,比如 [“apple”, “banana”, …],面试官此时已经提示单词数量超级多。然后实现一个 function 名为: singleTypo,输入为一个字符串,比如 “axple”。如果这个单词可以由之前的单词列表中的一个单词通过修改一个字母得到,就返回 true,比如 apple 修改第二个字母可以得到 axple。如果输入是 aple 则返回 false,因为需要删除一个字母才行,而题目只能要求修改一个字母。同样, accle 也不行。因为要从 apple 修改第二第三个字母得到。

  2. 午饭。CMU 国人大佬

  3. 面试官迟到 15 分钟。面试时间实际为 30 分钟。给定一个 picture (二维)。里面有一些有色的像素,保证所有像素是相连的(上下左右相连),且只有一个联通块。返回一个最小矩阵,这个矩阵能包含所有的有色 pixel。

  4. 给定一个棋盘,里面有一些棋子。你能移走这个棋子,当且仅当这个棋子的同行同列有其它棋子。要求最多能移走多少棋子。

谢谢lz的分享,说一下我的思路,如果有错的地方欢迎指出来

  1. Topological sort
  2. 对dictionary建立trie tree,写一个helper function,input是string & trie node,output是判断string是否在tree中出现,main function只要for i in range(input string length), 判断一下i之前的substring在trie中有没有出现过,以及helper (i 之后的substring, current trie node) 是不是return tree, loop中有一个return true就可以返回true了。
  3. 维护一个int array 来记录有色像素点的 xmin, xmax, ymin, ymax, 在dfs/bfs遍历像素点的时候update array 最后输出 array围起来的矩阵
  4. 高频,connected component

第一题会出现mammal terrier这种跨级的pair吧?

第二题用trie吗 是不是可以把目标词挨个字母改了进去搜索

没必要改目标字符啊 直接建完trie去搜索就好了吧

[来自官方APP]

第一轮可以拓扑排序,但是如果一个类不会被两个父类同时指向,拓扑排序就显得多余了,直接建树做层序遍历输出也可以吧
第二轮是lc 676,对字典建trie,然后单词挨个字母改,然后进trie做搜索。
第三轮是lc 302,最优解用binary search找边界,O(mlogn+nlogm)。
第四轮,同行或同列的棋子算在一个联通块里面,通过不同的联通块数量求解

直接建树的话是不是得事先知道root是哪一个才行?

第四輪不是很懂 有沒有好心人解釋一下?

我认为是需要的

直接建树的话有一个dummy root就行了,遇到dummy root下的节点属于其他父亲的话移除掉,最后从dummy root开始遍历