Google Intern 面经 20150112

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

shuffle是否要随机产生结果？还是对于固定输入，给出固定输出？

mm豆 发表于 2015-4-6 06:28
shuffle是否要随机产生结果？还是对于固定输入，给出固定输出？

你的意思是“是否有多个valid的output？”吧？输出任意一个valid的答案即可。

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

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

mm豆 发表于 2015-4-6 08:22
比如这个解法，对于一种输入，对应着唯一一种输入。没有随机的过程。不知道lz怎么做的？
“先记录每个字 ...

你的思路应该没有问题，我也就是sort+group了一下，然后在用你说的“填空”的方式构造了一个valid的输出；当然，之前要check一下是否有valid的输出。

跟 随机 有什么关系？

eval 发表于 2015-4-6 08:29
你的思路应该没有问题，我也就是sort+group了一下，然后在用你说的“填空”的方式构造了一个valid的输出 ...

比如输入是aabc，那么按照这种算法，结果就是abac。这种算法只有唯一的一种结果。如果随机的话，可以产生多个结果，比如 b a c a 等

mm豆 发表于 2015-4-6 08:39
比如输入是aabc，那么按照这种算法，结果就是abac。这种算法只有唯一的一种结果。如果随机的话，可以产生 ...

嗯，给出 一个 valid的output即可。

eval 发表于 2015-4-6 09:08
嗯，给出 一个 valid的output即可。

好的 谢谢啦～                    

mm豆 发表于 2015-4-6 06:24
就是先构造一个符合要求的字符串，然后再随机化.随机化怎么保证相邻字母不等？比如， 符合要求的字符串为 ...

就是按照正常的随机化 从最后一个开始随机选一个index然后判断是否符合要求，如果符合要求的话exchange。不过不知道这种方法是不是真正随机的shuffle

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));
这样随机交换之后不会出现相同字母变成邻居的情况么？

mm豆 发表于 2015-4-10 01:43
我明白你说的算法：
        Random rnd = new Random();
           for (int i=size - 1; i>= 1; i--)

Sorry I cannot type Chinese right now.
Just need a check before swap to make sure no same elements next to each other.