狗狗MTV跪经

ICong 发表于 2018-2-1 16:52
https://www.careercup.com/question?id=18880663 回来发现是个面经题，感觉还是小tricky的，主要是要用h ...

这题感觉是union find吧

markpen 发表于 2018-4-3 02:40
楼主，第二轮， 第一小问，set里的字母可以重复吗？像这样[a, a, b, c, d]。

我觉得可以对char set建Trie，这样读一个单词查一个，也不用担心char set中是否有重复。
只是不知道复杂度是否符合要求

没太懂第四轮那道题。
1. 是说给的array要被分成若干个length为K的subarray，然后判断每个subarray里面是不是连续的整数么？
2. 还是说不管array里面的sequence，可以打乱顺序，只要最后把array分成若干个长为K的小array，然后它们里面都是连续整数就可以？
还有，同一位置的元素是不是只能出现在一个subarray里面？
谢谢谢谢！

第二轮第一题 求指正:

1. public class FindWordsInCharSet {
   
2.     public List<String> findWords(Set<String> dict, char[] chars) {
   
3.         int max = -1;
   
4.         int[] freq = new int[256];
   
5.         for (char c : chars) {
   
6.             freq[c - 'a']++;
   
7.         }
   
8.         Map<Integer, List<String>> map = new HashMap<>();
   
9.         for (String s : dict) {
   
10.             int[] checker = freq.clone();
    
11.             int i = 0;
    
12.             for (; i < s.length(); i++) {
    
13.                 int val = s.charAt(i) - 'a';
    
14.                 checker[val]--;
    
15.                 if (checker[val] < 0) {
    
16.                     break;
    
17.                 }
    
18.             }
    
19.             if (i == s.length()) {
    
20.                 addToMap(map, s);
    
21.                 max = Math.max(max, s.length());
    
22.             }
    
23.         }
    
24.         return map.get(max);
    
25.     }
    
26. }

复制代码

补充内容 (2018-4-9 08:08):
明显space不太好

可能用trie更好一些

迷彩的瓜皮帽 发表于 2018-4-9 07:58
第二轮第一题 求指正:

请问trie的思路是怎么样的？感觉trie是用来查prefix的，这题里的char都不是按顺序来的。。

另外在你的解法里，只保存长度最长的string或许空间会好些？

第三题peer(e1, e2)中， e1, e2是必须report给同一个direct manager吗？

第二轮  利口柒贰零

请问lz 第二轮第二题parent是怎么用到的

请问楼主第二轮第一题，set里的char应该是没有重复的吧。。。（他放在set里了么不是？） 那这个是不是暴力扫描dict里的每个单词，每次遇到一个字符就放进visited里，如果遇到visited的char或者是set里没有的就跳过看下一个词；如果合法就比较长度，更新result list； 不知道我是不是理解对了那个给的char set的设定，请楼主解惑，谢谢啦