Affirm 新鲜出炉电面

这个是一道地里出现过很多次的店面问题，小伙伴们可以在地里找找。楼主用的是UndirectedGraph方法解出来的。如果小伙伴有其他的解法求一个。发面经攒人品，求大家加米。

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

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

匿名者 发表于 2021-10-20 10:35
请问楼主可以提供一下undirectedgraph的思路么，我想的是用hashmap➕排序。返回value最大的。感觉时 ...

1.     private Map<String, Map<String, Integer>> graph = new HashMap<>();
   
2.     private Map<String, Integer> countMap = new HashMap<>();
   
3. 
   
4.     public void addWord(List<String> words) {
   
5.         Collections.sort(words);
   
6.         for (int i = 0; i < words.size(); i++) {
   
7.             String from = words.get(i);
   
8.             //if words are duplicated
   
9.             if (i != 0 && from.equals(words.get(i - 1))) {
   
10.                 continue;
    
11.             }
    
12. 
    
13.             for (int j = i + 1; j < words.size(); j++) {
    
14.                 String to = words.get(j);
    
15.                 //if words are duplicated
    
16.                 if (from.equals(to) || to.equals(words.get(j - 1))) {
    
17.                     continue;
    
18.                 }
    
19.                 //Adding from/to nodes
    
20.                 Map<String, Integer> toMap = graph.getOrDefault(from, new HashMap<>());
    
21.                 int count = toMap.getOrDefault(to, 0);
    
22.                 toMap.put(to, count + 1);
    
23.                 graph.put(from, toMap);
    
24. 
    
25.                 //Adding to/from nodes
    
26.                 Map<String, Integer> fromMap = graph.getOrDefault(to, new HashMap<>());
    
27.                 int fromCount = fromMap.getOrDefault(from, 0);
    
28.                 fromMap.put(from, fromCount + 1);
    
29.                 graph.put(to, fromMap);
    
30. 
    
31.                 countMap.put(from, Math.max(countMap.getOrDefault(from, 0), count + 1));
    
32.                 countMap.put(to, Math.max(countMap.getOrDefault(to, 0), fromCount + 1));
    
33.             }
    
34.         }
    
35.     }
    
36. 
    
37.     public Map<String, List<String>> printValue() {
    
38.         Map<String, List<String>> res = new HashMap<>();
    
39. 
    
40.         for (Map.Entry<String, Map<String, Integer>> entry : graph.entrySet()) {
    
41.             String from = entry.getKey();
    
42.             Map<String, Integer> toMap = entry.getValue();
    
43.             int maxCount = countMap.get(from);
    
44. 
    
45.             for (Map.Entry<String, Integer> toMapEntry : toMap.entrySet()) {
    
46.                 String to = toMapEntry.getKey();
    
47.                 int times = toMapEntry.getValue();
    
48. 
    
49.                 if (times == maxCount) {
    
50.                     List<String> list = res.getOrDefault(from, new ArrayList<>());
    
51.                     list.add(to);
    
52.                     res.put(from, list);
    
53.                 }
    
54.             }
    
55.         }
    
56.         return res;
    
57.     }

复制代码

请问楼主可以提供一下undirectedgraph的思路么，我想的是用hashmap➕排序。返回value最大的。感觉时间复杂度很高

匿名者 发表于 2021-10-20 11:51

谢谢大佬！

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

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

1. import collections
   
2. arr = [['a', 'b', 'c'],['b', 'c', 'd'], ['c', 'd', 'e']]
   
3. 
   
4. graph = collections.defaultdict(collections.Counter)
   
5.     for lst in arr:
   
6.         counter = collections.Counter(list(set(lst)))
   
7.         for elem in counter:
   
8.             counter[elem] -= 1
   
9.             graph[elem] += counter
   
10.             counter[elem] += 1
    
11.             print(counter)

复制代码

Python Hashtable of {neighbor: freq}

后面应该就很明朗了

for key in graph:
    maxFreq = max(graph[elem])
    cur = []
.....
....
....

1. from itertools import permutations
   
2. # Time compexity O(number of stirng * longest_string_length ^2)
   
3. # Space Complexity O(26 ^2)
   
4. def leeters_applying_most(string_list):
   
5.     matrix = [[0] * 26 for _ in range(26)]
   
6.     for string in string_list:
   
7.         for first, second in itertools.permutations(string, 2):
   
8.             rol_idx, col_idx = ord(first) - ord('a'), ord(second) - ord('a')
   
9.             matrix[rol_idx][col_idx] += 1
   
10.     res = defaultdict(list)
    
11.     for rol_idx in range(26):
    
12.         max_row_val = max(matrix[rol_idx])
    
13.         if max_row_val == 0:
    
14.             continue
    
15.         for col_idx in range(26):  
    
16.             if matrix[rol_idx][col_idx] == max_row_val:
    
17.                 res[chr(rol_idx + ord('a'))].append(chr(col_idx + ord('a')))
    
18.     return res
    
19. print(leeters_applying_most(["abc", "bcd", "cde"]))

复制代码

有一个偷鸡的做法，用python的库和list/dict comprehension，因为这些是底层c写的，虽然complexity更高但runtime并不慢，不知道面试中这样写行不行

1. from collections import defaultdict
   
2. from collections import Counter
   
3. 
   
4. def test(l):
   
5.     d=defaultdict(Counter)
   
6.     for i in l:
   
7.         for j in range(len(i)):
   
8.             for k in i[:j]+i[j+1:]:
   
9.                 d[i[j]][k]+=1
   
10.     return {i:[k for (k,v) in d[i].items() if v==max(d[i].values())] for i in d}

复制代码