狗家2020 summer实习 店面 挂经

我也不知道是内推还是海投, 反正海投之后没多久就收到店面通知.

一面: 国人小哥, 英语清晰流利,交流很愉快.直接上题.很简单的dfs题.思考了几分钟开始写. 写完跑了两个test. 问了时间复杂度, O(nm).题目如下.

Follow up:
固定 safe patterns , 多次查询(bomb, disarm pattern), 怎么做.
我的做法是记录每次查询的Bomb 到 disarm pattern dfs的路径,路径上每两个patterns 之间标记为连通的, 下次查询直接看bomb2 和 disarm patterns 之间是否连通.

二面: 国人大叔,英语烂到听不懂,然后话又少,全程都是我主动找话说, 题目也非常偏.一上来就问我是不是学过编译原理(可能是简历上提到过), 我说是,然后他说是的话这题就简单了.



提示了要用递归调用, 没想出来,就按自己的思路来写了, 类似文本分析器. 时间不够, 写完了大的框架, 并用已经写完的函数跑了两个例子. 写完的那部分问题不大.

六天之后收到店面加面.

加面:
外国人,英语听得...吃力, 题目也很偏, 很长, 花了20分钟才大概搞清楚. 大概意思就是给一个无向连同图, 每个顶点可以有无限个邻接顶点,各个顶点的名字可能一样, 比如这样的图:
A - B - A    I
       |     |   /
      C - D - G
           /   \
        E    C
要求设计一个算法,从任何一个点开始,输出图中所有的点.  
没做出来, 因为我的出发点在dfs或者bfs. 但是"各个顶点的名字可能一样", 这样就不能简单地dfs 或者 bfs, 因为我没想出怎么给每个点分配一个unique id, 有了id 才能标记这个点为visited, 从而避免陷入无限search.
面试官又说不用写代码, 写思路就好, 然后又说不用分配unique id...
最后跟面试官说没遇到过这种类似的题,他说我们看重的是你解决问题的过程.

不用等结果,肯定会挂在加面
. ----
感想:
很倒霉, 最后两个面试, 给我一道中规中矩的题可能就能过...
二面和加面的题都不是一面这种常规题. 正如加面说的那样, 面试官更看重解决问题的思路.如果遇到加面那种没有思路的题,应该问面试官一些例子,让他用这个例子来step by step 解释一下题目,这样做应该会有好一点的思路.


补充内容 (2019-11-26 10:24):
加面: 每个节点都只能跟直接领节点通信,也就是只知道直接领节点是哪些. 每个节点也只有一个字母,没有坐标或者有序的编号之类的.

patpat, 楼主已经很不错了, 狗家题取决于面试官,运气, 三面可以使用节点的地址作为唯一id吗? 不需要为每个节点分配唯一的id

woooooooks 发表于 2019-11-26 09:32
patpat, 楼主已经很不错了, 狗家题取决于面试官,运气, 三面可以使用节点的地址作为唯一id吗? 不需要为每个 ...

谢谢! 节点没有地址, 每个节点都只知道直接邻接点是哪些

真过分。。加面可以看这个贴子（第五轮），有一些讨论

https://www.1point3acres.com/bbs/thread-568676-1-1.html

yiliaobailiao 发表于 2019/11/26 13:16:22
真过分。。加面可以看这个贴子（第五轮），有一些讨论

https://www.1point3acres.com/bb...

我去，多看面经就好了！

yiliaobailiao 发表于 2019/11/26 13:16:22
真过分。。加面可以看这个贴子（第五轮），有一些讨论

https://www.1point3acres.com/bb...

加面你有思路么？

可不可以用hashCode() 来设一个唯一值？

tanlion 发表于 2019/11/26 14:16:00
可不可以用hashCode() 来设一个唯一值？

不可以的，因为名字可能一样。比如C-A-B-A-B-A，你怎么区分两个B呢？

请问LZ面的岗位是research还是SDE？

今天天气不错 发表于 2019/12/04 13:44:19
请问LZ面的岗位是research还是SDE？

是SDE.