Akuna Quant Research NG 2023 OA

Akuna Quant Research OA，三道算法题，一个小时，第三题全部Test Cases AC不算特别直接（暴力解部分Test Cases会超时），所以题量不算小。

1. Frequency Sort
用Counter()计算出items中各元素的频率，然后在排序时将频率作为自定义规则，比较简单

Python3:

1. def itemSort(items):
   
2.     freq_counter = Counter(items)
   
3.     # Sort by frequency and then by value
   
4.     return = sorted(items, key=lambda x: (freq_counter[x], x))

复制代码

2. Delivery Management System
Dijkstra应用题。
因为图为无向图，所以建图时注意同一条边的两个方向都要加。
heap里放的tuple第一个值均为1（图为无权图），第二个值为节点号-1（原始节点号从1开始），如此heap在pop元素时就会先按照距离再按照节点号。
【无权图也可以直接用BFS，这里为了省事直接默写了Dijkstra】
注意：题目不是返回距离，而是除初始节点外的访问顺序（即每个节点pop出heap的顺序），因此在每个节点刚被pop出heap时记录答案。


Python3:

1. import heapq
   
2. 
   
3. def order(city_nodes, city_from, city_to, company):
   
4.     graph = [[] for _ in range(city_nodes)]
   
5.     for i in range(len(city_from)):
   
6.         graph[city_from[i] - 1].append((1, city_to[i] - 1))
   
7.         graph[city_to[i] - 1].append((1, city_from[i] - 1))
   
8.     heap = [(0, company - 1)]
   
9.     distance = [city_nodes + 1 for _ in range(city_nodes)]
   
10.     distance[company - 1] = 0
    
11.     city_order = []
    
12.     while heap:
    
13.         cur = heapq.heappop(heap)
    
14.         if cur[1] + 1 != company:
    
15.             city_order.append(cur[1] + 1)
    -baidu 1point3acres
16.         for vertex in graph[cur[1]]:
    
17.             if distance[cur[1]] + vertex[0] < distance[vertex[1]]:
    
18.                 distance[vertex[1]] = distance[cur[1]] + vertex[0]
    
19.                 heapq.heappush(heap, (distance[vertex[1]], vertex[1]))
    
20.     return city_order
    
21. 
    
22. city_nodes = 5
    
23. city_from = [1, 2, 2]
    
24. city_to = [2, 3, 4]
    
25. company = 1
    
26. print('Case in description: ', order(city_nodes, city_from, city_to, company))
    
27. city_nodes = 5
    
28. city_from = [1, 1, 2, 3, 1]
    
29. city_to = [2, 3, 4, 5, 5]
    
30. company = 1
    
31. print('Test Case 0: ', order(city_nodes, city_from, city_to, company))
    
32. city_nodes = 3
    
33. city_from = [1]
    
34. city_to = [2]
    
35. company = 2
    
36. print('Test Case 1: ', order(city_nodes, city_from, city_to, company))

复制代码

3. Extraordinary Substrings
这道题感觉不算是纯粹的滑动窗口，因为两重for循环是把所有可能的子串都遍历了一遍。但符合滑动窗口特质的地方是第8行和第10行，即每次变更

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

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

, 26):
        string_int[chr(ord('a') + i)] = (i - 2) // 3 + 2
   
    extraordinary = 0
    for i in range(length):
        string_sum = 0
        for j in range(i, length):
            string_sum += string_int[input_str[j]]
            if not string_sum % (j - i + 1):
                extraordinary += 1
   
    return extraordinary

print(countSubstrings('abcd')) # 6
print(countSubstrings('bdh')) # 4
print(countSubstrings('abcd')) # 6
```

太强了楼主，你不上岸谁上岸！

第二题代码只能看到一半 and 看不到第三题…？谢谢lz！

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

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

咦，代码出现问题，不知道为什么，都只有第一行……我尝试修复一下

补充内容 (2023-08-31 15:26 +08:00):

已修复完毕

匿名用户 发表于 2023-9-4 10:31
.. 第二题代码只能看到一半 and 看不到第三题…？谢谢lz！

咦，方便发一下你那里的界面长啥样不？我这里看着内容是完整的呀

825344491 发表于 2023-09-05 10:40:01
咦，方便发一下你那里的界面长啥样不？我这里看着内容是完整的呀

就 🈚️了

你好！请问做的时候会录屏吗？

匿名用户 发表于 2023-9-5 12:38
就 🈚️了

感谢反馈！已经补充哈！你再看看可不可以

newds 发表于 2023-9-5 18:47
你好！请问做的时候会录屏吗？

不会的不会的

body117 发表于 2023-9-29 05:47
太强了楼主，你不上岸谁上岸！

谢谢大佬！一起加油哇！