果家 两轮背靠背

新鲜热腾腾的面经！果家组招，不透露组名啦～ 背靠背两轮视频 - hr提前告知，如果第一轮答不好就不会有第二轮的那种。。。第一轮结束中间有一个小时，等第二轮小哥出不出现= = 然后出现了lol
每一轮都是coderpad上写，并且要跑test case


1. 简历 + design pattern / mock code + 算

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

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

]     -->       [2, 5, 8]
      [7, 8, 9]                 [3, 6, 9]


求加米呀呀呀呀！！！

第一题旅行家问题，用mask状态位压缩dp n*2^n复杂度

1. def numSquarefulPerms(n):
   
2.     if n == 0:
   
3.         return []
   
4.    
   
5.     visited = [False]*(n+1)
   
6.     graph = {x:[] for x in range(1, n+1)}
   
7.     for i in range(1, n+1):
   
8.         for j in range(1, i):
   
9.             s = i+j
   
10.             if helper(s):
    
11.                 graph[i].append(j)
    
12.                 graph[j].append(i)
    
13. 
    
14.     res = []
    
15.     for x in graph:
    
16.         dfs(graph, visited, n, res, [x], x)
    
17.     return res
    
18. 
    
19. def helper(n):
    
20.     x = n
    
21.     while x*x > n:
    
22.         x = (x+n//x)//2
    
23.     return x*x == n
    
24. 
    
25. def dfs(graph, visited, n, res, path, i):
    
26.     if len(path) == n:
    
27.         res.append(path[:])
    
28.         return
    
29.    
    
30.     visited[i] = True
    
31.     for j in graph[i]:
    
32.         if not visited[j]:
    
33.             dfs(graph, visited, n, res, path + [j], j)
    
34.     visited[i] = False
    
35. 
    
36. for n in range(21):
    
37.     print(n, numSquarefulPerms(n))

复制代码

1. (0, [])
   
2. (1, [[1]])
   
3. (2, [])
   
4. (3, [])
   
5. (4, [])
   
6. (5, [])
   
7. (6, [])
   
8. (7, [])
   
9. (8, [])
   
10. (9, [])
    
11. (10, [])
    
12. (11, [])
    
13. (12, [])
    
14. (13, [])
    
15. (14, [])
    
16. (15, [[8, 1, 15, 10, 6, 3, 13, 12, 4, 5, 11, 14, 2, 7, 9], [9, 7, 2, 14, 11, 5, 4, 12, 13, 3, 6, 10, 15, 1, 8]])
    
17. (16, [[8, 1, 15, 10, 6, 3, 13, 12, 4, 5, 11, 14, 2, 7, 9, 16], [16, 9, 7, 2, 14, 11, 5, 4, 12, 13, 3, 6, 10, 15, 1, 8]])
    
18. (17, [[16, 9, 7, 2, 14, 11, 5, 4, 12, 13, 3, 6, 10, 15, 1, 8, 17], [17, 8, 1, 15, 10, 6, 3, 13, 12, 4, 5, 11, 14, 2, 7, 9, 16]])
    
19. (18, [])
    
20. (19, [])
    
21. (20, [])

复制代码

[/i][/i][/i][/i]

五年后挖坟写一下第一题：

1. def numSquarefulPerms(n):
   
2.     def isSqr(num):
   
3.         x = int(num**0.5)
   
4.         return x * x == num
   
5. 
   
6.     def dfs(curr_path, used):
   
7.         if len(curr_path) == n:
   
8.             ans.append(curr_path[:])
   
9.             return
   
10.         for next_num in range(1, n + 1):
    
11.             if next_num in used or not isSqr(curr_path[-1] + next_num):
    
12.                 continue
    
13.             used.add(next_num)
    
14.             dfs(curr_path + [next_num], used)
    
15.             used.remove(next_num)
    
16. 
    
17.     ans = []
    
18.     for i in range(1, n + 1):
    
19.         dfs([i], {i})
    
20.     return ans

复制代码

ywangriley 发表于 2020-5-30 13:53
第一题还挺有意思，除了dfs一个个试，能不能用hamiltonian path？

是dfs做的，hamiltonian path我觉得可以

这第一题是久久六的马甲题，比原题简单，无需去重。还可以用DP做，DFS做完后，面试官没问能否优化吗？

tinlittle 发表于 2020-5-31 08:53
这第一题是久久六的马甲题。还可以用DP做，DFS做完后，面试官没问能否优化吗？

因为前面20min都在讨论简历和design pattern，最后写完跑完就只剩5min问问题了

看来感觉时间还是挺紧张的呢，第一题DFS的话感觉可以用hashmap优化，谢谢分享！

求积分求积分！看不到具体题目诶。 楼主方便回复一下具体题目吗？

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

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

请问楼主怎么拿到果家面试的，海投还是内推呢？谢谢

还将旧时意 发表于 2020-6-12 07:23
请问楼主怎么拿到果家面试的，海投还是内推呢？谢谢

hr LinkedIn 联系的