虾图狗被svp废掉面经

g家三月联系在湾区的我，我表示想去虾图，于是电面，onsite，然后team match国人老板，然后svp就把我挂掉了。这不是求我贴面经么！

电面很简单，声测小白，求rgb最趋近的颜色，用一个hexdigit表示，比如输入是#AA0908,那么最接近的就是#AA1100,输出#A10

onsite五轮，第一轮白小哥，问题是如何在2dmatrix里设计好玩的迷宫，还有就是一堆围棋子有多少口气，黑白边界都要考虑。

第二轮南亚友人，链表倒数第n个item打印，推多米诺，求最后有多少多米诺骨

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

,C,D这样重合最多的。没什么想法，贪心硬做。。。

第五轮2d矩阵中最长递增序列。


补充内容 (2018-5-12 09:21):
跳舞毯那个题可以原地不动，比如序列AE,AE,AE,AE,解可以是A,A,A,A或者E,E,E,E

hychin 发表于 2018-5-12 09:52
你是CS专业的么。

我master是，本科李彦宏一个专业的XD
工作好几年了。

第四题可以转化为一个两点之间求最长路径的图问题：

1. 设输入是长度为n的序列：S(1), S(2), ..., S(n)
   
2. (每个元素都是A-E的集合，例如 S(1) = "B", S(2) = "AD")
   
3. 
   
4. 1. 对于每个S(i)，创建5个节点 Va(i), ..., Ve(i)   (对应A-E)
   
5. 
   
6. 2. 为了处理方便，先额外创建5个源节点 Va(0), ..., Ve(0)，和5个汇节点 Va(n+1), ..., Ve(n+1)
   
7. 
   
8. 3. 对于任意i ϵ [0, n]，对于任意x,y ϵ "ABCDE"
   
9.    创建一条边Vx(i) -> Vy(i+1)，当且仅当x与y在跳舞毯上相邻；
   
10.    然后，如果x在集合S(i)中，那么设定边的权值为1，否则为0。
    
11. 
    
12. 4. 将5个源节点合并为一个节点V(0)，5个汇节点合并成一个V(n+1)
    
13. 
    
14. 5. 求从V(0)到V(n+1)的最长路径
    

复制代码

求最长路径的方法一般是拓扑排序+DP，不过这里我们已经知道图的结构是每5个一层了，层内部不会有依赖关系，所以不用拓扑排序，直接创建两个长度为5的数组滚动DP就好。

时间复杂度O(n)，n是序列长度

".R...R.L...R..L.."这个里面9-11，13-14也应该是站着的吧？

谢谢分享 楼主在哪面的

devilnut 发表于 2018-5-12 09:08
谢谢分享 楼主在哪面的

虾图->西雅图
毕竟西雅图地便宜。。

第四题是什么意思…

devilnut 发表于 2018-5-12 09:10
第四题是什么意思…

求跟给定的跳舞序列重叠度最高的跳舞序列。
比如输入是ACD,E,BA,DE
你在每步都最好选给定序列里面的move，比如因为第二个是E，所以第一步C，D都可以，第二步选了E，所以第三步最好选B，那么第四步也选E，结果就是C,E,B,E
比如序列A,E,A,E，这个就很难满足，A,C,A,C是一个最优解。
忘了说可以原地不动，比如序列AE,AE,AE,AE,解可以是A,A,A,A或者E,E,E,E

第四题是说输出是依次踩的顺序吗？但为什么

比如序列（B,AD,BE,D)，最符合的就是B,A,B,C？
最后一个是因为D到不了，所以用了C吗？

ivyjwyu 发表于 2018-5-12 09:19
第四题是说输出是依次踩的顺序吗？但为什么

比如序列（B,AD,BE,D)，最符合的就是B,A,B,C？

对的对的，这个应该是一个move不能满足，第一步C的话，C,D,E,D也可以。

感觉第四题像DP啊

补充内容 (2018-5-12 09:22):
有待考证, 还没有仔细想

vegito2002 发表于 2018-5-12 09:21
感觉第四题像DP啊

像，当时没想出来，也许也能贪心做。

elfandi 发表于 2018-5-12 09:20
对的对的，这个应该是一个move不能满足，第一步C的话，C,D,E,D也可以。

一般是为啥SVP挂人。。楼主知道一般有哪些因素吗