g*********e
发帖数: 14401 | 1 昨天面的。上来先问我简历上的OS project。
之后开始coding，问了一个走迷宫的问题。在一个bool array里面寻找两点的path，并
打印。
我写了一个DFS递归+visited array寻找。
之后他问我complexity。我说空间时间都是O(mn)。
他说我的code时间不是O(mn),我看了下发现我的是exponential，就跟他说了，然后忙
改了下，就是visited set以后不再reset。这样就是polynomial time。他还算满意。
之后他问我如果这个迷宫很大，该怎么处理。我想了下说就分成若干小block,每台机器
算每个小block里可能的boundry to boundry path,并存在一个list里面。这样相邻的
block就可以交流对方的path，然后拓展当前path(我也没完全想出个solution）
他让我写每台机器算block里path和互相交流的过程的伪代码。说类似remote
procedure call。
我瞎写了下，大致就是对每个block边界上的点每对pair求path, 并且有个优化，在寻
找path的过程中如果路径其他边界点，直接添加该path.
然后写机器间交流的伪代码，我更乱写了，大致是根据相邻机器的path list拓展当前
机器的global path.并不停的expand global path list.
最后我问了他几个technical问题。
求分析我这样还有戏吗？ |
g*********e
发帖数: 14401 | |
d*******d
发帖数: 2050 | 3 恕我直言，这个表现很勉强。不过电面的门槛比较低，还有点希望。
不过这个表现在onsite是完全没戏的。
【在 g*********e 的大作中提到】
: 昨天面的。上来先问我简历上的OS project。
: 之后开始coding，问了一个走迷宫的问题。在一个bool array里面寻找两点的path，并
: 打印。
: 我写了一个DFS递归+visited array寻找。
: 之后他问我complexity。我说空间时间都是O(mn)。
: 他说我的code时间不是O(mn),我看了下发现我的是exponential，就跟他说了，然后忙
: 改了下，就是visited set以后不再reset。这样就是polynomial time。他还算满意。
: 之后他问我如果这个迷宫很大，该怎么处理。我想了下说就分成若干小block,每台机器
: 算每个小block里可能的boundry to boundry path,并存在一个list里面。这样相邻的
: block就可以交流对方的path，然后拓展当前path(我也没完全想出个solution）
|
g*********e
发帖数: 14401 | 4
你这说的我拔凉拔凉的，罢了，老实去亚麻了。
【在 d*******d 的大作中提到】
: 恕我直言，这个表现很勉强。不过电面的门槛比较低，还有点希望。
: 不过这个表现在onsite是完全没戏的。
|
g*********e
发帖数: 14401 | 5
请教，我这个表现主要哪里比较欠缺？去onsite的话要加强什么？谢谢了！
【在 d*******d 的大作中提到】
: 恕我直言，这个表现很勉强。不过电面的门槛比较低，还有点希望。
: 不过这个表现在onsite是完全没戏的。
|
d*******d
发帖数: 2050 | 6 加强白板coding.
onsite 重点考査白板coding,题目不会很难，但必须一次写出来能直接编译运行出正确
结果，不能有bug.
大约都是你碰到的找path那个难度的。
从你对那个题的回答看，你算法基本功不是特别扎实，有待加强。
【在 g*********e 的大作中提到】
:
: 请教，我这个表现主要哪里比较欠缺？去onsite的话要加强什么？谢谢了！
|
g*********e
发帖数: 14401 | 7
哦 谢谢！
【在 d*******d 的大作中提到】
: 加强白板coding.
: onsite 重点考査白板coding,题目不会很难，但必须一次写出来能直接编译运行出正确
: 结果，不能有bug.
: 大约都是你碰到的找path那个难度的。
: 从你对那个题的回答看，你算法基本功不是特别扎实，有待加强。
|
