Stripe电面

第一问类似于953. Verifying an Alien Dictionary，需要保持顺序，直接用index作为顺序即可。然后可以用minHeap或者TreeSet来实现排序即可

1. 
   
2. private static final String SPLITTER = ", ";
   
3.     public List<String> getSupportedLanguagesForBoth(String headers, Set<String> supportedLanguagesForSever) {
   
4.         List<String> res = new ArrayList<>();
   
5.         if (headers == null || headers.isEmpty() || supportedLanguagesForSever == null || supportedLanguagesForSever.isEmpty())  {
   
6.             return res;
   
7.         }
   
8.         String[] supportedLanguagesForClient = headers.split(SPLITTER);
   
9.         int n = supportedLanguagesForClient.length;
   
10.         Map<String, Integer> orderMap = new HashMap<>();
    
11.         for (int i = 0; i < n; i++) {
    
12.             orderMap.put(supportedLanguagesForClient[i], i);
    
13.         }
    
14.         PriorityQueue<String> minHeap = new PriorityQueue<>((a, b) -> Integer.compare(orderMap.get(a), orderMap.get(b)));
    
15.         for (String serverLanguage: supportedLanguagesForSever) {
    
16.             if (orderMap.containsKey(serverLanguage)) {
    
17.                 minHeap.offer(serverLanguage);
    
18.             }
    
19.         }
    
20.         while (!minHeap.isEmpty()) {
    
21.             res.add(minHeap.poll());
    
22.         }
    
23.         return res;
    
24.     }
    

复制代码

Falldawn 发表于 2021-6-13 00:25
第一问类似于953. Verifying an Alien Dictionary，需要保持顺序，直接用index作为顺序即可。然后可以用min ...

第一问根本不需要排序，直接遍历

1. 
   
2. private static final String SPLITTER = ", ";
   
3.     public List<String> getSupportedLanguagesForBoth(String headers, Set<String> supportedLanguagesForSever) {
   
4.         List<String> res = new ArrayList<>();
   
5.         if (headers == null || headers.isEmpty() || supportedLanguagesForSever == null || supportedLanguagesForSever.isEmpty())  {
   
6.             return res;
   
7.         }
   
8.         String[] supportedLanguagesForClient = headers.split(SPLITTER);
   
9.         int n = supportedLanguagesForClient.length;
   
10.         for (String curLang: supportedLanguagesForClient) {
    
11.             if (supportedLanguagesForSever.contains(curLang)) {
    
12.                 res.add(curLang);
    
13.             }
    
14.         }
    
15.         return res;
    
16.     }
    

复制代码

第二问只需要多加一个HashMap用来存<tag, all Language tags>就可以了，由于不能删set还要去重，那就再加一个set来判断之前结果是否加过了，否则可以用List.contains耗时间

1. private static final String SPLITTER = ", ";
   
2. public List<String> getSupportedLanguagesForBoth2(String headers, Set<String> supportedLanguagesForSever) {
   
3.         List<String> res = new ArrayList<>();
   
4.         Set<String> resSet = new HashSet<>();
   
5.         if (headers == null || headers.isEmpty() || supportedLanguagesForSever == null || supportedLanguagesForSever.isEmpty())  {
   
6.             return res;
   
7.         }
   
8.         Map<String, Set<String>> tagMap = new HashMap<>();
   
9.         for (String curLang: supportedLanguagesForSever) {
   
10.             String curTag = curLang.substring(0, 2);
    
11.             tagMap.putIfAbsent(curTag, new HashSet<>());
    
12.             tagMap.get(curTag).add(curLang);
    
13.         }
    
14.         String[] supportedLanguagesForClient = headers.split(SPLITTER);
    
15.         for (String curLang: supportedLanguagesForClient) {
    
16.             if (supportedLanguagesForSever.contains(curLang)) {
    
17.                 resSet.add(curLang);
    
18.                 res.add(curLang);
    
19.             } else if (tagMap.containsKey(curLang)){
    
20.                 for (String s: tagMap.get(curLang)) {
    
21.                     if (resSet.add(s)) {
    
22.                         res.add(s);
    
23.                     }
    
24.                 }
    
25.             }
    
26.         }
    
27.         return res;
    
28.     }
    

复制代码

第三问，那就直接多加一个条件判断，把其他所有语言加进来，这里也要去重

1. private static final String SPLITTER = ", ";
   
2. private static final String WILD_CARD = "*";
   
3. public List<String> getSupportedLanguagesForBoth3(String headers, Set<String> supportedLanguagesForSever) {
   
4.         List<String> res = new ArrayList<>();
   
5.         Set<String> resSet = new HashSet<>();
   
6.         if (headers == null || headers.isEmpty() || supportedLanguagesForSever == null || supportedLanguagesForSever.isEmpty())  {
   
7.             return res;
   
8.         }
   
9.         Map<String, Set<String>> tagMap = new HashMap<>();
   
10.         for (String curLang: supportedLanguagesForSever) {
    
11.             String curTag = curLang.substring(0, 2);
    
12.             tagMap.putIfAbsent(curTag, new HashSet<>());
    
13.             tagMap.get(curTag).add(curLang);
    
14.         }
    
15.         String[] supportedLanguagesForClient = headers.split(SPLITTER);
    
16.         for (String curLang: supportedLanguagesForClient) {
    
17.             if (supportedLanguagesForSever.contains(curLang)) {
    
18.                 resSet.add(curLang);
    
19.                 res.add(curLang);
    
20.             } else if (tagMap.containsKey(curLang)){
    
21.                 for (String s: tagMap.get(curLang)) {
    
22.                     if (resSet.add(s)) {
    
23.                         res.add(s);
    
24.                     }
    
25.                 }
    
26.             } else if (curLang.equals(WILD_CARD)) {
    
27.                 for (String s: supportedLanguagesForSever) {
    
28.                     if (resSet.contains(s)) {
    
29.                         res.add(s);
    
30.                     }
    
31.                 }
    
32.             }
    
33.         }
    
34.         return res;
    
35.     }
    

复制代码

第4问有点麻烦，首先需要排序，用max Heap，其次排序需要根据tag对应的q值，需要一个HashMap，最后还需要一个set记录已经去重，后面遇到*号不要再加了
所有测试都通过了

1. 
   
2. private static final String SPLITTER = ", ";
   
3. private static final String WILD_CARD = "*";
   
4. private static final String WEIGHT_SEPARATOR = ";";
   
5.     public List<String> getSupportedLanguagesForBoth4(String headers, Set<String> supportedLanguagesForSever) {
   
6.         List<String> res = new ArrayList<>();
   
7.         if (headers == null || headers.isEmpty() || supportedLanguagesForSever == null || supportedLanguagesForSever.isEmpty())  {
   
8.             return res;
   
9.         }
   
10.         Map<String, Set<String>> tagMap = new HashMap<>();
    
11.         for (String curLang: supportedLanguagesForSever) {
    
12.             String curTag = curLang.substring(0, 2);
    
13.             tagMap.putIfAbsent(curTag, new HashSet<>());
    
14.             tagMap.get(curTag).add(curLang);
    
15.         }
    
16.         Map<String, Double> weightMap = new HashMap<>();
    
17.         PriorityQueue<String> maxHeap = new PriorityQueue<>((a, b) -> Double.compare(weightMap.get(b), weightMap.get(a)));
    
18.         Set<String> tagSetAlreadySet = new HashSet<>();
    
19.         String[] supportedLanguagesForClient = headers.split(SPLITTER);
    
20.         for (String curHeaderTag: supportedLanguagesForClient) {
    
21.             String[] curHeaderTagArray = curHeaderTag.split(WEIGHT_SEPARATOR);
    
22.             String curTag = curHeaderTagArray[0];
    
23.             double curTagWeight = Double.parseDouble(curHeaderTagArray[1].substring(2));
    
24.             if (supportedLanguagesForSever.contains(curTag)) {
    
25.                 tagSetAlreadySet.add(curTag);
    
26.                 weightMap.put(curTag, curTagWeight);
    
27.                 maxHeap.offer(curTag);
    
28.             } else if (tagMap.containsKey(curTag)){
    
29.                 for (String curLang: tagMap.get(curTag)) {
    
30.                     if (tagSetAlreadySet.add(curLang)) {
    
31.                         weightMap.put(curLang, curTagWeight);
    
32.                         maxHeap.offer(curLang);
    
33.                     }
    
34.                 }
    
35.             } else if (curTag.equals(WILD_CARD)) {
    
36.                 for (String curLang : supportedLanguagesForSever) {
    
37.                     if (!tagSetAlreadySet.contains(curLang)) {
    
38.                         weightMap.put(curLang, curTagWeight);
    
39.                         maxHeap.offer(curLang);
    
40.                     }
    
41.                 }
    
42.             }
    
43.         }
    
44.         while (!maxHeap.isEmpty()) {
    
45.             res.add(maxHeap.poll());
    
46.         }
    
47.         return res;
    
48.     }
    

复制代码

Falldawn 发表于 2021-6-13 00:25
第一问类似于953. Verifying an Alien Dictionary，需要保持顺序，直接用index作为顺序即可。然后可以用min ...

没必要这么复杂吧，直接在headers里顺序看是不是支持， 是的话加到res里不就行了？

lloydrodman 发表于 2021-6-20 02:26
没必要这么复杂吧，直接在headers里顺序看是不是支持， 是的话加到res里不就行了？

是，我后面的帖子写了

想问一下楼主 店面是需要编译通过这种吗？

use priority queues

我只搞了三问。多谢楼主分享