Square新鲜面经 (3.3.2020)

今天上午刚刚结束的电面，趁着还记得赶紧发个帖，求大米~现在还不到188分还有好多帖子不能看。。。

电面题目：

让写一个程序，实现这样一个功能：

你已经有一个单词，比如apple

然后用户依次输入一个char, a - z之间的

如果正确，那console显示：You’ve entered correctly, the

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

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

，所以+3分。

要求在猜完所有字母以后，返回得到的总分。

这里需要实现一个Trie，然后用这个来记录分数。我自己没有写完时间就到了，Trie还是不太熟练，不过感觉面试官还算满意，不知道能不能过。

follow up 也是一个字母一个字母的猜吗？猜完一个再猜另一个？

cee 发表于 2020-3-11 09:44
follow up 也是一个字母一个字母的猜吗？猜完一个再猜另一个？

嗯嗯一样的，只是算分的方式不一样。

请问楼主后面有去onsite嘛.. 先给楼主加米了

请问楼主后来去了吗？后边的面试都被问到什么问题了？

谢谢lz的题目！！
我把lz的题写了一下，大家可以交流！！
第一个子问题：猜一个单词

1. class Solution:
   
2.     def __init__(self, groundtruth_word):
   
3.         self.groundtruth_word = groundtruth_word
   
4.         self.input_word = ""
   
5.     def take_input(self):
   
6.         char = input('Guess a char: ')
   
7.         prevL = len(self.input_word)
   
8.         if char == self.groundtruth_word[prevL]:
   
9.             self.input_word += char
   
10.             print("You've entered correctly, the current is  "  + self.input_word)
    
11.         else:
    
12.             print("You've entered wrong, the current is  "  + self.input_word)
    
13.     def checkLenth(self):
    
14.         if len(self.input_word) == len(self.groundtruth_word):
    
15.             return True
    
16.         else:
    
17.             return False
    
18. 
    
19. S = Solution('apple')
    
20. while(not S.checkLenth()):
    
21.     S.take_input()
    
22. print('Successful ! Program exit.')
    
23. sys.exit()

复制代码

第二个子问题，猜一个list 返回分数

1. import sys
   
2. 
   
3. #Define Trie Node
   
4. class Node:
   
5.     def __init__(self):
   
6.         self.children = {} #key:char #val: tree Node
   
7.         self.val = 0
   
8.         self.isEnd = False
   
9.         
   
10. #Define Trie
    
11. class Trie:
    
12.     def __init__(self):
    
13.         """
    
14.         Initialize your data structure here.
    
15.         """
    
16.         self.dummy = Node()
    
17. 
    
18.     def insert(self, word: str) -> None:
    
19.         """
    
20.         Inserts a word into the trie.
    
21.         """
    
22.         head = self.dummy
    
23.         for idx, char in enumerate(word):
    
24.             if char not in head.children:
    
25.                 head.children[char] = Node()
    
26.             head = head.children[char]
    
27.             head.val += 1
    
28.             if idx == len(word)-1:
    
29.                 head.isEnd = True
    
30.         
    
31.     def search(self, word: str) -> bool:
    
32.         """
    
33.         Returns if the word is in the trie.
    
34.         """
    
35.         head = self.dummy
    
36.         for idx, char in enumerate(word):
    
37.             if char not in head.children:
    
38.                 return False
    
39.             head = head.children[char]
    
40.             if idx == len(word) - 1:
    
41.                 return head.isEnd
    
42.         
    
43.     def startsWith(self, prefix: str) -> bool:
    
44.         """
    
45.         Returns if there is any word in the trie that starts with the given prefix.
    
46.         """
    
47.         head = self.dummy
    
48.         for idx, char in enumerate(prefix):
    
49.             if char not in head.children:
    
50.                 return False
    
51.             head = head.children[char]
    
52.             if idx == len(prefix) - 1:
    
53.                 return True
    
54.    
    
55.     def obtainScore(self, prefix: str) -> bool:
    
56.         head = self.dummy
    
57.         score = 0
    
58.         for idx, char in enumerate(prefix):
    
59.             if char not in head.children:
    
60.                 return score
    
61.             head = head.children[char]
    
62.             score += head.val
    
63.             if idx == len(prefix) - 1:
    
64.                 return score
    
65.         
    
66. class Solution:
    
67.     def __init__(self, groundtruth_word, trie):
    
68.         self.trie = trie
    
69.         self.input_word = ""
    
70.         
    
71.     def take_input(self):
    
72.         char = input('Guess a char: ')
    
73.         if char == 'EXIT!!':
    
74.             print('The author wants to exit')
    
75.             return True
    
76.    
    
77.         if self.trie.startsWith(self.input_word + char):
    
78.             self.input_word += char
    
79.             print("There indeed exists word with prefix "  + self.input_word + " in the list")
    
80.         else:
    
81.             print("There is not word with prefix  "  + self.input_word + char + " in the list")
    
82.         print('The current score is ' + str(trie.obtainScore(self.input_word)))
    
83.         if self.trie.search(self.input_word):
    
84.             print("The word " + self.input_word + " is in the list! Exit")
    
85.             return True
    
86.         print(' ')
    
87.         
    
88.         return False
    
89.         
    
90. List = ['apple', 'air', 'ad', 'bc']
    
91. trie = Trie()
    
92. for word in List:
    
93.     trie.insert(word)
    
94. 
    
95. S = Solution('apple', trie)
    
96. while(True):
    
97.     Exit = S.take_input()
    
98.     if Exit:
    
99.         sys.exit()
    

复制代码