亚麻3月 北美面经

huang_anthea 发表于 2020-4-6 12:26
我突然想到，dfs是这样的吗？

输入如果是 -》 [a,b],,[e,f],[l,o]...

1. from collections import Counter
   
2. from collections import namedtuple
   
3. 
   
4. # return True if word can be formed
   
5. # false otherwise
   
6. def dfs(tuples, d):                # both are
   
7.         if len(d) == 0:                # all letters found match
   
8.                 return True
   
9. 
   
10. 
    
11.         if len(tuples) == 0:        # no more avaliable tuples to choose
    
12.                 return False
    
13. 
    
14. 
    
15.         for char, count in d.items():
    
16.                 candidate_tuples = [t for t in tuples if char in t]                # all the tuples contain this
    
17.                 for t in candidate_tuples:
    
18.                         d[char] -= 1
    
19.                         if d[char] == 0:
    
20.                                 del d[char]
    
21. 
    
22.                         tuples[t] -= 1
    
23.                         if tuples[t] == 0:
    
24.                                 del tuples[t]
    
25. 
    
26.                         if dfs(tuples, d):
    
27.                                 return True
    
28. 
    
29.                         # backtracking
    
30.                         d[char] = d.get(char, 0) + 1
    
31.                         tuples[t] = tuples.get(t, 0) + 1
    
32. 
    
33.         return False
    
34. 
    
35. 
    
36. def main(lst_of_tupules, target):
    
37.         # first, change the tuples into a dictionary, since only the count of each letter matters
    
38.         d = Counter(target)                        # "hello" => {"h": 1, "e": 1, "l": 2, "o":1}
    
39.         tuples = Counter(lst_of_tupules)                # [("a", "b"), ("c", "d"), ("c", "d")]                =>  {("a", "b"): 1, ("c", "d"): 2}
    
40.         return dfs(tuples, d)
    
41. 
    
42. 
    
43. """Let the size of tuples be n, let the lenght of target word be n,
    
44. Time: O(m ** n), Exponential
    
45. Space: O(m + n), since we create two additional dictionary
    
46. """
    
47. 
    
48. 
    
49. if __name__ == '__main__':
    
50.         Test = namedtuple('Test', ['tuples_lst', 'target_word'])
    
51.         test1 = Test(tuples_lst = [("a", "b"), ("c", "d"), ("h", "e")], target_word="ade")
    
52.         assert(main(test1.tuples_lst, test1.target_word) == True)
    
53. 
    
54.         test2 = Test(tuples_lst = [("a", "b"), ("c", "d"), ("h", "e")], target_word="hello")
    
55.         assert(main(test2.tuples_lst, test2.target_word) == False)
    
56. 
    
57.         test3 = Test(tuples_lst = [("h", "e"), ("f", "e"), ("l", "e"), ("l", "e"), ("m", "n"), ("o", "h")], target_word="hello")
    
58.         assert(main(test3.tuples_lst, test3.target_word) == True)
    
59. 
    
60.         test4 = Test(tuples_lst = [("h", "e"), ("f", "e"), ("l", "e"), ("l", "e"), ("m", "n")], target_word="hello")
    
61.         assert(main(test4.tuples_lst, test4.target_word) == False)
    
62. 
    
63.         test5 = Test(tuples_lst = [("t", "e"), ("p", "u"), ("a", "b"), ("c", "d"), ("m", "n")], target_word="tupac")
    
64.         assert(main(test5.tuples_lst, test5.target_word) == False)
    
65. 
    
66.         test6 = Test(tuples_lst = [("t", "e"), ("p", "u"), ("a", "b"), ("c", "d"), ("u", "p")], target_word="tupac")
    
67.         assert(main(test6.tuples_lst, test6.target_word) == True)
    
68. 
    
69.         test7 = Test(tuples_lst = [("t", "e"), ("p", "u"), ("a", "b"), ("c", "d"), ("p", "u")], target_word="tupac")
    
70.         assert(main(test7.tuples_lst, test7.target_word) == True)
    
71. 
    
72. 
    

复制代码

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

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

Hhh123 发表于 2020-4-6 14:10
楼主是new grad吗 怎么面的这么难

研究生刚毕业， 不过走的是社招。 难不难看主观吧， recuriter 确实说过机器人组bar 高一些。 不过被拒还是只能怪自己水平不够，还得继续提高。

面试加油

jerrydream 发表于 2020-4-6 21:55
刚刚的回复不懂为什么发不出来

我是从target word 开始search.  target word 里的每一个letter, 都从t ...

谢谢楼主啦

huang_anthea 发表于 2020-4-7 10:09
谢谢楼主啦

客气 面试加油

请问dictionary里存的是什么， 比如key和value到底是什么可以产生memo的效果， 谢谢了

请问第一轮是system design还是ood？online的话需要画图吗？感觉楼主很接近了，下一个面试肯定成功！

jerrydream 发表于 2020-4-6 21:59
研究生刚毕业， 不过走的是社招。 难不难看主观吧， recuriter 确实说过机器人组bar 高一些。 不过被拒还 ...

嗯嗯嗯 好 ，谢谢楼主

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

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

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

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