Google Intern 面经 20150112

本想有了match再发个总结帖，现在感觉怕是淹没在pool里了。

先分享一下时间点，2014.12.01 内推，很快有recuiter联系，但当时available的时间窗只有一月的

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

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

---

总体来讲题很简单，运气不错，换了难题还真未必能进host match。。

Hope for the best.

1. public static void shuffle(String input){
   
2.         List<Character> characters = new ArrayList<Character>();
   
3.         for(char c:input.toCharArray()){
   
4.             characters.add(c);
   
5.         }
   
6.         StringBuilder output = new StringBuilder(input.length());
   
7.         while(characters.size()!=0){
   
8.             int rand = (int)(Math.random()*characters.size());
   
9.             
   
10.             output.append(characters.remove(rand));
    
11.         }
    
12.         
    
13.         
    
14.         String res = output.toString();
    
15.         for (int i=0; i<res.length()-1;i++) {
    
16.                 if (res.charAt(i) ==res.charAt(i+1)) {
    
17.                         System.out.println("not valid");
    
18.                         break;
    
19.                 }
    
20.         }
    
21.         System.out.println(res);
    
22.     }

复制代码

eval 发表于 2015-4-6 08:17
你的意思是“是否有多个valid的output？”吧？输出任意一个valid的答案即可。

比如这个解法，对于一种输入，对应着唯一一种输入。没有随机的过程。不知道lz怎么做的？
“先记录每个字符出现的次数，即该字符需要被填入生成字符串的次数
然后从第一位开始填空
然后每次从剩下的字母堆中选取剩余待填入次数最多、且与前一位字符不冲突的字符填入，这样可以确保剩余可填写的不同字符种类是最多的
如果没有其他不冲突的待填写字符就报错
最多是O(26n)或O(256n)
”

will_ym 发表于 2015-4-8 01:59
就是按照正常的随机化 从最后一个开始随机选一个index然后判断是否符合要求，如果符合要求的话exchange。 ...

我明白你说的算法：
        Random rnd = new Random();
           for (int i=size - 1; i>= 1; i--)
                swap(arr, i, rnd.nextInt(i-1));
这样随机交换之后不会出现相同字母变成邻居的情况么？

子矩阵是啥问题？咋dp？

houqingniao 发表于 2015-2-19 14:57
子矩阵是啥问题？咋dp？

其实就是部分和。容斥原理啥的。

请教一下第二题怎么解的？

will_ym 发表于 2015-2-20 04:29
请教一下第二题怎么解的？

hint：是否能shuffle成valid的字符串可以由每个字符出现的次数的关系确定。

eval 发表于 2015-2-20 11:12
hint：是否能shuffle成valid的字符串可以由每个字符出现的次数的关系确定。

搞定了，但是是O(n squre). 你当时做得是O(n) 么？

子矩阵的题可以用容斥，也可以维护一个一维的数组

tinalxj12 发表于 2015-2-21 15:01

这个感觉不太对呢，会产生相同的char相邻的情况吧

will_ym 发表于 2015-2-21 01:33
搞定了，但是是O(n squre). 你当时做得是O(n) 么？

先统计每个char的个数，如果有count > (size+1)/2, 那就是invalid的。然后剩下的就不会了。。求问怎么做的？