Yelp 電面

昨天結束了, yelp skype 面試。

印度姊姊人挺和善的。
題目是給你一組，人名的list.
你需要把他兩兩配對。

我一開始com

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

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

請加點大米。加大米不扣你分 謝謝

1. import random
   
2. 
   
3. def get_user(users, end_index):
   
4.     idx = random.randint(0,end_indx)
   
5.     user = users[idx]
   
6. 
   
7.     # remove user1 from the list
   
8.     users[idx] = users[end_indx]
   
9.     end_indx-=1
   
10.     reutrn user, end_indx
    
11. 
    
12. def match_beans(users, last_n_pairs):
    
13.     """
    
14.     Randomly pairs up a list of usernames.
    
15.    
    
16.     :param users: A non-empty list of unique usernames
    
17.     :returns: A list of tuples representing pairs
    
18.         e.g. [('Jen', 'Kevin'), ('Alan', 'Rachel'), ('Da', 'Neha')]
    
19.     """
    
20.     # Validate input
    
21.     if not users:
    
22.         return []
    
23.     #
    
24.    
    
25.     history = set()
    
26.     for pair_lst in last_n_pairs:
    
27.         for pair in pair_lst:
    
28.             history.add(sorted(pair))
    
29.    
    
30.    
    
31.     output = []
    
32.     end_indx = len(users)-1
    
33.    
    
34.     while end_indx > 0:        
    
35.         # pick user1        
    
36.         user_1, end_indx = get_user(users, end_indx):
    
37.         # pick user2
    
38.         user_2,end_indx = get_user(users, end_indx):
    
39.         pair= sorted(user_1,user_2)
    
40.         if pair not in history:
    
41.             output.append(pair)
    
42.         else:
    
43.             end_indx+=2
    
44.    
    
45.     # check remaining
    
46.     if end_indx==0:
    
47.         output.append((users[0],None))
    
48.    
    
49.     return output
    
50. 
    
51. 
    
52. 
    
53. 
    
54. 
    
55. for i in range(100):
    
56.     test_users = ['Alan', 'Da', 'Jen', 'Kevin', 'Neha', 'Rachel']
    
57.     print(match_beans(test_users))
    
58.    
    
59. test_users = ['Alan', 'Da', 'Jen', 'Kevin', 'Neha']
    
60. print(match_beans(test_users))   
    
61. 
    
62. test_users = []
    
63. print(match_beans(test_users))   
    
64. 
    
65. # O(T) : o(n^2)
    
66. 
    
67. 
    
68. # We dont want same two users meeting more than once every n weeks.
    
69. # n = 2
    
70. # input last 2 weeks matches
    
71. last_n_pairs = [
    
72.     [('Alan', 'Kevin'), ('Jen', 'Da'), ('Neha', 'Rachel')]
    
73.     [('Da', 'Alan'), ('Neha', 'Rachel'), ('Jen', 'Kevin')]
    
74. ]

复制代码

请问随机配对的话，能不能把list拆成两份然后直接用 random.shuffle(list)，人后再用指针遍历，O(n)复杂度。
这样会不会太简单了哈哈

1. const people1 = [{id: 'Alan', team: 'a'}, {id: 'Da', team: 'a'}, {id: 'Jen', team: 'c'},
   
2. {id: 'Kevin', team: 'd'}, {id: 'Neha', team: 'm'}, {id: 'Rachel', team: 'q'}, {id: 'Tom', team: 'a'}]
   
3. 
   
4. const people2 = [{id: 'Alan', team: 'a'}, {id: 'Da', team: 'a'}]
   
5. 
   
6. console.log('result=', matchBeans(people1))
   
7. 
   
8. console.log('result=', matchBeans(people2))

复制代码

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

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

题目没有看懂 怎么配对？

mhsasd 发表于 2019-4-7 00:13
题目没有看懂 怎么配对？

剛開始就是 randomized 配對。真覺簡單
follow-up的配對 是不能跟上K 回合裡面有重複

能举个例子吗？ 还是没太看懂题目什么意思 。 谢谢楼主

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

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

请问不对list做delete 不是后面generate 出很多没用的index吗？就是已经配对过的user index.

如果list中是奇数个元素，怎么 亮亮配对啊？会有重复吧