狗家店面加面（还是跪了）

三哥的确太坑了… 楼主下次面要先装逼用最蠢的方法做… 不过即使是这样要是三哥想挂你也没辙~

个人感觉这题加面电面题三哥问的不过分，的确是很正常的followup。3次reverse的解法已经很常见了，如果就凭这个当作加面结果肯定不合适，所以面出这种程度的followup是意料之中的。

其实换一个角度想，如果你不知道3次reverse的话，你会怎么做呢？其实有一个非常straight forward的做法：不是要移动K位么？那么我先存下a[ 0 ], 然后每次让 a[ i ] 和 a[ (i + d) % n ]交换就行了。这个做法的确能过掉很多input，但是对于n和k不互质的情况，模拟一下就会出问题。问题出在哪？出在交换了已经移动的位上了。怎么办？多模拟几组互质的数据就会发现，当我交换着交换着发现我回到了起始点的时候，就可以停下，然后从起始点下一位开始再开始相同的交换过程就可以了。

上面这个解法就是所谓的最大公约数解法，因为最终其实分成了 gcd(n, k) 组。但是掰开了就是一个最简单情况的优化而已，而且只要面试官给点提示肯定能做出来。

巧妙的解法容易被记住因为这种解法往往是把不相关的点联系在了一起，然后我们却绝对不能忘记应该如何一步步的从最原始的解法优化到一个满足各种限制的解法。能想出巧妙解法却无法追根溯源的人，你能信任他能够把一个慢吞吞的服务一步步优化到亿级服务么？

没有偏袒三哥的意思，但是大家在面试的时候还是要摆正心态啊。说句实在话，有些国人面试官黑的比三哥还狠。曾经看过一个很优秀的面试者，3个三哥1个国人面试，面试之后觉得三哥关要跪，结果三哥全部strong yes，只有国人是no。最让人蛋疼的是国人的理由：这个面试者不够谦虚。

nevets 发表于 2016-10-28 01:05
个人感觉这题加面电面题三哥问的不过分，的确是很正常的followup。3次reverse的解法已经很常见了，如果就凭 ...

这位兄弟说的我服，我也是怪自己能力不够。心态也是没能摆正好。感谢你的建议。

很早以前也遇到过相同的事情，所以就记住了以后刷题一定要看最好的解法，不要AC了就不管了。
也是同一题，同样的解法

wangxy 发表于 2016-10-28 01:44
很早以前也遇到过相同的事情，所以就记住了以后刷题一定要看最好的解法，不要AC了就不管了。
也是同一题， ...

当初欠的债，现在都是要还的。谢谢指点。

楼主move on 感觉这题难度还好 楼主要面linkedin实习吗

道理都懂。。但是如果一开始想的方法是三次reverse，再想到gcd真的好难啊

求问reverse的方法怎么处理k>nums.size()?

nevets 发表于 2016-10-28 01:05
个人感觉这题加面电面题三哥问的不过分，的确是很正常的followup。3次reverse的解法已经很常见了，如果就凭 ...

深深体会过被香港人黑，反而老印都很公平