Java程序员3面小米,被俩算法题难倒,微软员工6分钟解决,真丢脸

前些天再网上看了很多网友再谈论一个很有意思的问题,有关算法的。然后小编追根溯源终于扎到了这篇帖子。说是有位网友在面试小米Java岗三次后,终于挺进了第三轮面试,结果还是败在了两道算法题上面。

1、写个读方法和写方法,实现读写锁

2、一副从1到n的牌,每次从牌堆顶取一张放桌子上,再取一张放牌堆底,直到手机没牌,最后桌子上的牌是从1到n有序,设计程序,输入n,输出牌堆的顺序数组


Java程序员3面小米,被俩算法题难倒,微软员工6分钟解决,真丢脸


对于楼主所发的这个问题,网友们纷纷发表了自己的答案和看法。

有网友问道,是不是反着做一遍就行了。然后楼主把题目的意思又给他解释了一遍:“一副扑克牌中抽出13张从a到k然后把上面的一张抽出来放最低下,第二张是1拿出来摆桌上,再把最上面的一张抽出来放底下,第二张是2放桌上,以此类推把他们按照顺序都抽出来.怎么摆?”


Java程序员3面小米,被俩算法题难倒,微软员工6分钟解决,真丢脸


这时就有为网友给出了自己的答案,第二个问题,第一步:从1开始循环到n递增num,第二部,在第一步的循环内,数组中从0到n-1循环,每次从数组中跳过一个空白位置,插入数字num。还说道,6,7有问题,要跳过一个空白位。至于怎么跳。就是arr[i]=0就跳过一次,跳过的次数局部变量记录下。但是楼主并没有回复他,貌似也是一脸懵逼的。


Java程序员3面小米,被俩算法题难倒,微软员工6分钟解决,真丢脸


然后又蹦出来一名网友给出了一个不同的方法,第一遍从1开始步长为2,第二遍从2开始步长为4,第三遍从4开始步长为8,第m次从2的m-1次方开始,步长为2的m次方,m=(n+1)/2,直接出结果,模拟个蛋。这时,楼主也回复了他,觉得应该是正解。也有很多网友点赞,同时也表示是正解。


Java程序员3面小米,被俩算法题难倒,微软员工6分钟解决,真丢脸


很显然,这应该是解决问题的一种方法。那我们还有没有其他方法解决呢?接着往下看。

这时,一位自称是微软的程序员发表了条评论。

“取一个1~n的数组,这里为了说明取n=5。按照题目中的规则变换,得到数组:[1 3 5 4 2],将该数组下标与值互换得到[1 5 2 4 3],即为答案。解释:[1 3 5 4 2]的意义是,经过变换,原数组中3号位置的数字现在2号槽,原数组中5号位置的数字现在3号槽... 现在已知变换后的槽存放的是1~n,故只需将下标与值互换即可得到待求数组。

这道题还可以继续扩展:

1.变换规则更复杂使得无法逆向模拟还原原数组;

2.最终得到的序列可以扩展为任意序列。请大家以后不要黑微软是养老院了”

但是楼主貌似没理解全,问道你这些数字是数组的下标吗

后面这位微软的程序员也补充了一下,[]括起来的所有元素都是实际的数字(题目中牌上的数字)。下标从1开始


Java程序员3面小米,被俩算法题难倒,微软员工6分钟解决,真丢脸


小编看了下,63个赞稳坐第一,评论也有很多人都表示佩服,不愧是微软的程序员呀!

有人调了半小时才搞定这道题,思路是跟前面的微软大佬学的,确实这道题单纯逆向可解,但逆向确实有局限性,如果碰到难逆向的题就瞎了,多学一点思路,受教了。

不过有位网友表示,我一文科毕业的看大佬们回答好像看天书。

哈哈哈...


Java程序员3面小米,被俩算法题难倒,微软员工6分钟解决,真丢脸


对于上面网友们的看法和答案。大家有什么想要表达的呢?欢迎再下方评论区吐槽!

上一篇:【产品功能】配置网卡从此与关机无缘,弹性网卡支持热插拔功能


下一篇:教你用C语言编写万年历,程序员超乎你的想象!