Pinterest新鲜上门挂经

一共四轮，从十点面到一点，不知道为什么hr没给安排午饭
第一轮是三姐，问了一道识别text是否safe。 假设有一个black list, 里面有一些phrase, 比如[&q

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

[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来最终打印关系表。

1. import unittest
   
2. 
   
3. class TrieNode:
   
4.     def __init__(self):
   
5.         self.table = dict()
   
6.         self.phraseEnd = False
   
7. 
   
8. 
   
9. class Trie:
   
10.     def __init__(self):
    
11.         self.root = TrieNode()
    
12. 
    
13.     def insertPhrase(self, phrase):
    
14.         node = self.root
    
15.         words = phrase.split(' ')
    
16. 
    
17.         for word in words:
    
18.             if word not in node.table:
    
19.                 node.table[word] = TrieNode()
    
20.             node = node.table[word]
    
21. 
    
22.         node.phraseEnd = True
    
23. 
    
24.     def search(self, words):
    
25.         node = self.root
    
26. 
    
27.         for word in words:
    
28.             if node.phraseEnd:
    
29.                 return True
    
30.             if word not in node.table:
    
31.                 return False
    
32.             node = node.table[word]
    
33.         return node.phraseEnd
    
34. 
    
35. 
    
36. class Solution:
    
37.     def isSafe(self, blackList, pintext):
    
38.         if not blackList or not pintext:
    
39.             return True
    
40.         
    
41.         trie = Trie()
    
42.         for phrase in blackList:
    
43.             trie.insertPhrase(phrase)
    
44.         
    
45.         pintextWords = pintext.split(" ")
    
46.         for i in range(len(pintextWords)):
    
47.             if trie.search(pintextWords[i:]):
    
48.                 return False
    
49.         return True
    
50. 
    
51. class SolutionTest(unittest.TestCase):
    
52.     def testIsSafe(self):
    
53.         sol = Solution()
    
54.         blackList = ["machine guns", "world war i"]
    
55.         self.assertFalse(sol.isSafe(blackList, "i love world war i"))
    
56.         self.assertTrue(sol.isSafe(blackList, "world war ii"))
    
57. 
    
58. if __name__=='__main__':
    
59.     unittest.main()

复制代码

补充内容 (2018-10-24 14:13):
试着用Trie的思路做了第一个pintext safe的问题

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

楼主什么时候面的啊？

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

Tyrant89 发表于 2018-10-24 05:00
第一题和我面的一模一样，连例子都一样

请问是怎么做的呀～一个一个查contains嘛？

FML 发表于 2018-10-24 07:04
请问是怎么做的呀～一个一个查contains嘛？

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

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

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

pandami 发表于 2018-10-24 07:27
会不会出现【2 0】？不一定是直接上级？

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

Tyrant89 发表于 2018-10-24 07:16
就是建立个Trie，但不同的是我TRie里面的每个元素是单词不是字母

想请教一下 算法时间复杂度是不是 （pintext 的长度 * blacklist 里最长的的sentence的长度）？

FML 发表于 2018/10/24 07:35:58


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

建有向graph bfs？