9月4号google电面【已挂】

wenqiang88 发表于 2015-9-12 00:16
有道理。如果满足的话，怎么样返回这个permutation比较快呢？

感觉应该先把最高频的每个MinDist个就填一个 剩下的慢慢填就行了 我想下code怎么写

这题类似的以前没遇到过的话 面试当场要想通确实挺难的

gp89757 发表于 2015-9-12 00:21
感觉应该先把最高频的每个MinDist个就填一个 剩下的慢慢填就行了 我想下code怎么写

感觉还是要用heap

首先判断有没有合法输出，只要比较最高频出现的次数t，要求的间隔k，和总长度n之间是否满足n > (t-1)*k就可以了。

打印结果的话，可以先申请一个长度为n的，然后按照高频往低频打印，如果当前位置已经被占，就往后挪一位。

感觉这种方式打印效率略低，有没有更高的方法？

无论如何，电面问这个，有点变态啊。

补充内容 (2015-9-13 01:40):
这个打印方式有点趋向于greedy，暂时没想到更好的。

http://www.geeksforgeeks.org/rea ... st-d-distance-away/

mint0715 发表于 2015-9-13 06:37
http://www.geeksforgeeks.org/rearrange-a-string-so-that-all-same-characters-become-at-least-d-distan ...

对这个到处都能碰到原题的世界无奈了，这以后面试就是比谁看的多么，通刷CC150， geeksforgeeks，leetcode，lintcode...

edna 发表于 2015-9-13 06:44
对这个到处都能碰到原题的世界无奈了，这以后面试就是比谁看的多么，通刷CC150， geeksforgeeks，leetcod ...

我挂过这道题，所以挂完查了一下。

mint0715 发表于 2015-9-13 06:37
http://www.geeksforgeeks.org/rearrange-a-string-so-that-all-same-characters-become-at-least-d-distan ...

我的天啊，居然是原题。谢谢你挖出来！
这么看来面试官看来还是对我很厚道的了？

discoveryi 发表于 2015-9-11 13:46
总的来说，认为你的思路是正确的，不过有两个问题。

一问：为什么（除了最后一个row）不check？

回答
1. 因为第i row 只要check 和i+1 row 的关西所以最后一个row 不用check 这样就可以保证条件都成立
2. 我这边是assume都会有解然后这个算法保证找到的解是valid的

恩 是该想想怎么写checking function...

这边是string or char我觉得没有差别

say543 发表于 2015-9-11 13:13
LZ 我的解法式先统计character 的出现次数出现次数最高的代表我至少要有几个parts 然后再根据次数从高到 ...

第一个例子是错的啊，如果是aaa, bb, cc然后间距是3，那么abcabca是合法的，但是你这个返回了个fail？