一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 2841|回复: 18
收起左侧

狗家店面加面(还是跪了)

  [复制链接] |试试Instant~ |关注本帖
1451427216 发表于 2016-10-27 05:13:11 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 硕士 实习@Google - 内推 - 技术电面 |Fail其他

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
好吧,题目很简单。
右移array  k 位, in-place
input: {0, 1, 2, 3, 4}, k = 2
output: {3, 4, 0, 1, 2}

我算是体会到了烙印的无耻了。
这题几分钟写完了。用的是 三步反转法,  
reverse(nums.begin(),nums.begin()+left);
reverse(nums.begin()+left,nums.end());
reverse(nums.begin(),nums.end());

这个算法变量赋值是O(3N)次。
接下来他一直叫我优化到变量赋值是O(N)次。

最后也没把code写完。
还是实力不够,move on吧。
大家加油。
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴



评分

18

查看全部评分

本帖被以下淘专辑推荐:

nevets 发表于 2016-10-28 01:05:56 | 显示全部楼层
个人感觉这题加面电面题三哥问的不过分,的确是很正常的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。最让人蛋疼的是国人的理由:这个面试者不够谦虚。

评分

1

查看全部评分

回复 支持 4 反对 0

使用道具 举报

 楼主| 1451427216 发表于 2016-10-28 01:41:59 | 显示全部楼层
nevets 发表于 2016-10-28 01:05
个人感觉这题加面电面题三哥问的不过分,的确是很正常的followup。3次reverse的解法已经很常见了,如果就凭 ...

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

评分

2

查看全部评分

回复 支持 1 反对 0

使用道具 举报

MicX 发表于 2016-11-6 18:36:02 | 显示全部楼层
求问reverse的方法怎么处理k>nums.size()?
回复 支持 0 反对 1

使用道具 举报

finerve 发表于 2016-10-27 05:27:17 | 显示全部楼层
变量赋值O(3n)次还叫in-place么..?你帖子里的代码是不是符合他要求的?
回复 支持 反对

使用道具 举报

yxyxyx 发表于 2016-10-27 05:31:03 来自手机 | 显示全部楼层
http://www.geeksforgeeks.org/array-rotation/
回复 支持 反对

使用道具 举报

 楼主| 1451427216 发表于 2016-10-27 05:32:36 | 显示全部楼层
finerve 发表于 2016-10-27 05:27
变量赋值O(3n)次还叫in-place么..?你帖子里的代码是不是符合他要求的?

兄弟,我是3次reverse操作,没有用到其他变量,这也不叫in place? 他说我的是 in place 的。 只是swap交换里会涉及到赋值开销。
回复 支持 反对

使用道具 举报

 楼主| 1451427216 发表于 2016-10-27 05:41:31 | 显示全部楼层
yxyxyx 发表于 2016-10-27 05:31
http://www.geeksforgeeks.org/array-rotation/

看了链接,我的是第四种方法, O(N),space O(1). 然并卵。想要挂你,分分钟挂你。
回复 支持 反对

使用道具 举报

yxyxyx 发表于 2016-10-27 06:26:05 来自手机 | 显示全部楼层
1451427216 发表于 2016-10-26 17:41
看了链接,我的是第四种方法, O(N),space O(1). 然并卵。想要挂你,分分钟挂你。
. 1point 3acres 璁哄潧
嗯,three way partition是线性时间复杂度,array赋值次数是2n。链接里的第三种解法也是线性复杂度,array赋值次数是n。

所以我估计那个三哥大概是想问你链接里的第三种解法。
回复 支持 反对

使用道具 举报

 楼主| 1451427216 发表于 2016-10-27 06:38:50 | 显示全部楼层
yxyxyx 发表于 2016-10-27 06:26
嗯,three way partition是线性时间复杂度,array赋值次数是2n。链接里的第三种解法也是线性复杂度,arra ...

满足他要求的就只有第三种和第四种了。第三种的code看起来很不美观啊。还是实力没到火侯啊,早知道刚开始先装作不会这道题了。
回复 支持 反对

使用道具 举报

 楼主| 1451427216 发表于 2016-10-27 06:40:49 | 显示全部楼层
还请看面经的同学给点大米吧,这并不会减少你们的大米,每人每天都有一定的打赏额度。写面经不易,希望大家给点动力。
回复 支持 反对

使用道具 举报

iammajian 发表于 2016-10-27 07:42:20 | 显示全部楼层
第三种好难... 坏阿三
回复 支持 反对

使用道具 举报

huai10 发表于 2016-10-27 08:04:22 | 显示全部楼层
虽然题目很坑吧,但你还没法反驳
回复 支持 反对

使用道具 举报

lic10 发表于 2016-10-27 08:30:51 | 显示全部楼层
三哥的确太坑了… 楼主下次面要先装逼用最蠢的方法做… 不过即使是这样要是三哥想挂你也没辙~
回复 支持 反对

使用道具 举报

wangxy 发表于 2016-10-28 01:44:56 | 显示全部楼层
很早以前也遇到过相同的事情,所以就记住了以后刷题一定要看最好的解法,不要AC了就不管了。
也是同一题,同样的解法
回复 支持 反对

使用道具 举报

 楼主| 1451427216 发表于 2016-10-28 01:58:11 | 显示全部楼层
wangxy 发表于 2016-10-28 01:44
很早以前也遇到过相同的事情,所以就记住了以后刷题一定要看最好的解法,不要AC了就不管了。
也是同一题, ...

当初欠的债,现在都是要还的。谢谢指点。
回复 支持 反对

使用道具 举报

bobyuwenchen 发表于 2016-11-4 10:45:59 | 显示全部楼层
楼主move on 感觉这题难度还好 楼主要面linkedin实习吗
回复 支持 反对

使用道具 举报

xxxxx56789 发表于 2016-11-6 03:21:20 | 显示全部楼层
道理都懂。。但是如果一开始想的方法是三次reverse,再想到gcd真的好难啊
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-7 21:07

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表