b*****1
发帖数: 23 | 1 感觉难度不亚于G
第一题
2D matrix 1D形式的transpose O(1) space.
比如 [1, 2, 3, 4, 5, 6]表示
[1, 2, 3]
[4, 5, 6]
转置后
[1, 4]
[2, 5]
[3, 6]
返回
[1, 4, 2, 5, 3, 6]
完全不会
第二题 convex hull
勉强写了code
但是面试官都是manager级的，说convex hull的时候她们也不太懂，不知道想什么 | H**********5
发帖数: 2012 | | z*********n
发帖数: 1451 | 3 感觉软家题目一直都不简单，但是他家好像你答个80分就过，一线的得答个95才过。上
回面他家出了个矩阵乘法，那个算法早就忘了，最后naive for循环做的，也过了。 | W***o
发帖数: 6519 | 4 软家那么多team/group，而且又没有固定题库，我觉得难度比FB这种有题库的，光从题
目难度本身来看要难一点；
但是他们面试的侧重点不太一样，软家好像考察思路和交流更多一点，FB这种要求bug
free更高；
面fb，只要lc刷了前300题，再多看看面经，之后就看表演技术和运气了，呵呵 | f*****n
发帖数: 2126 | 5 lol。思维过程---都不需要了这是。
【在 z*********n 的大作中提到】
: 感觉软家题目一直都不简单，但是他家好像你答个80分就过，一线的得答个95才过。上
: 回面他家出了个矩阵乘法，那个算法早就忘了，最后naive for循环做的，也过了。
| z*********n
发帖数: 1451 | 6
你正好练练呗，就做做naive矩阵乘法，20分钟，看看能不能bug free？
【在 f*****n 的大作中提到】
: lol。思维过程---都不需要了这是。
| f*****n
发帖数: 2126 | 7 并不去微软。
【在 z*********n 的大作中提到】
:
: 你正好练练呗，就做做naive矩阵乘法，20分钟，看看能不能bug free？
| t*********r
发帖数: 63 | | z*********n
发帖数: 1451 | | r*****s
发帖数: 1815 | 10 如果不考虑运行时间的话（时间换空间，基本是平均 O(N^4) )
以下不是人话讲解，不用纸笔比较麻烦。。。
那么对于每一个点，沿着其置换群走一圈，肯定回到该点，第一次走的时候先看该点是
不是置换群中最早的一个点。如果是就可以再走一遍进行置换。举例子来说，题目中的
1 2 3 4 5 6 -> 1 4 2 5 3 6
1一看直接换成1，这个不说了
处理到index = 1的时候不断算当前元素应该置换到什么位置，可以得知
2->3->5->4->2的下标(1->2->4->3->1)形成一个置换群，而
2所在的位置idx=1是最早的
一个，所以做一次置换，形成
1 4 2 5 3 6
然后再到下一个idx=2,一看这不是置换群中第一个元素，那么就不进行置换，直到6.
也就是说，WxH->HxW, idx -> idx%W*H 加 idx/W
如果能证明这个变换总是先增后减（我直觉上是，正在找规律），那么O(1)时间可以知
道当前idx是不是一个置换群的第一个元素。则马上可以降低复杂度到N^2
(找到反例了。。。 4x7 idx=2 : 2->14->17->11->23->26->20-&
gt;5->8->2)增减若干次，所以每次必须重新判断。。。
妈的，这道题是十年前我面试MSRA的时候manager给我出的题，时隔这么多年终于破案了
突然有一种茫然的感觉。。。妈的。。
: 还能这么操作？你上段代码，或者跑个例子看看？
【在 z*********n 的大作中提到】
:
: 还能这么操作？你上段代码，或者跑个例子看看？
|
|
