Pinterest新鲜上门挂经

一共四轮,从十点面到一点,不知道为什么hr没给安排午饭
第一轮是三姐,问了一道识别text是否safe。 假设有一个black list, 里面有一些phrase, 比如[“machine guns”, “world war i”], 再给一个输入的pintext,如果pintext里有完整的phrase, 就判断为unsafe. 注意,"i love world war i"是unsafe的,但"world war ii"是safe的,因为是以word为单位match的。
第二轮是三哥,问了一道类似开心消消乐的题,只是board是固定的,不会有新的东西掉落。感觉是面试官拍脑袋想出来的,他自己也各种不清楚…
第三轮是个白人小姐妹,问了string array的共同最长前缀。
第四轮给一些pair, 代表(employee, manager), 然后按照organizaition的结构打印。比如[2, 1],[1, 0], [3, 0], [0, 0], 0是自己的manager, 就代表他是CEO,输出是:
0
|_1
|_2
|_3

最后祝大家offer多多!

在parse每个pair的过程中就可以同时知道哪个是CEO(即indegree为0的点)。Parse pair的过程就是建立graph,可以用adjacency-list 来表示这个graph。然后从CEO这个点做BFS就可以了。如果这些pair里包括跨级的关系,需用topological sort来最终打印关系表。

楼主什么时候面的啊?

第一题和我面的一模一样,连例子都一样

请问是怎么做的呀~一个一个查contains嘛?

就是建立个Trie,但不同的是我TRie里面的每个元素是单词不是字母

会不会出现【2 0】?不一定是直接上级?

第三轮是说有很多string求最长共同prefix?

这题是不是就是建树的意思呀

想请教一下 算法时间复杂度是不是 (pintext 的长度 * blacklist 里最长的的sentence的长度)?

建有向graph bfs?