Google Intern 电面 10/3

请问楼主第一轮第三题是怎么做的呢

kin332026 发表于 2016-10-31 13:55
请问楼主第一轮第三题是怎么做的呢

假设一定有解的情况下，可以看成一个贪心问题，"aaaabbbccd" 每次从string的第1位开始check s.charAt(i) != s.charAt(i - 1), 如果找到相等的就从后面抓一个和s.charAt(i - 1)不等的swap一下，prev = i - 1, 此时s.substring(0, prev +1)就满足条件，后面的递归处理就好，所以时间复杂度是O(N)

1. public static String nextNonRepeatPermutation(String s){
   
2.       if(s == null || s.length() < 2) return s;
   
3.       int i = 1;
   
4.       while(i < s.length() && s.charAt(i) != s.charAt(i - 1)){
   
5.         i++;
   
6.       }
   
7.       if(i == s.length()) {
   
8.         return s;
   
9.       }else{
   
10.         char prev = s.charAt(i);
    
11.         int from = i;
    
12.         while(i < s.length() && s.charAt(i) == prev){
    
13.           i++;
    
14.         }
    
15.         s = swap(s, from, i);
    
16.         return s.substring(0, from) + nextNonRepeatPermutation(s.substring(from));
    
17.       }
    
18.     }
    
19.     public static String swap(String s, int from ,int to){
    
20.       if(s == null || from < 0 || to >= s.length()) return s;
    
21.       char[] arr = s.toCharArray();
    
22.       char tmp = arr[from];
    
23.       arr[from]= arr[to];
    
24.       arr[to]= tmp;
    
25. 
    
26.       return new String(arr);
    
27.     }

复制代码

补充内容 (2016-11-1 00:52):
感觉还是用堆实现起来最简单确保正确：
把字符出现频率统计出来，扔在一个堆里。每次取出前两个频率高的字母，配成一对，次数减一，扔回堆。

syjohnson 发表于 2016-11-1 00:40
假设一定有解的情况下，可以看成一个贪心问题，"aaaabbbccd" 每次从string的第1位开始check s.charAt(i)  ...

不好意思，这个代码"aaabbbccc"时有bug

想问下楼主，第一轮第一题是什么个思路啊，是类似leetcode上 find peak element那一套题吗？假定edge之后再二分法？

谢啦。

syjohnson 发表于 2016-10-31 09:34
个人觉得第二轮第二题既然说到内存放不下了，面试官是想听你说external sort吧？另外minHeap也是O(N)

minheap O(N) 应该需要fibonacci heap做到插入O（1）？求问external sort具体？

MicX 发表于 2016-11-2 08:05
minheap O(N) 应该需要fibonacci heap做到插入O（1）？求问external sort具体？

正常heap建树就是O(N)啊， wiki external sort讲的就很好

syjohnson 发表于 2016-11-3 07:19
正常heap建树就是O(N)啊， wiki external sort讲的就很好

维护的时候不是要不停insert吗？

syjohnson 发表于 2016-11-3 07:19
正常heap建树就是O(N)啊， wiki external sort讲的就很好

以及怎么heap啊？我有看到说分成小包每个都建个k大小的heap，再merge。可是觉得比如包1的k+1和包2的k+1...加在一起比其他大呢？还是说分包的时候保证了数据在不同的包里不会重复？