狗狗家挂经

各位新年快乐哦！！

发一个圣诞前的狗家挂经，自己实在是比较水加上面试的运气也是不怎么好，华丽丽的挂掉了

第一轮 一个华裔，题目是找一个以第一个str的后缀和第二个str的前缀match的最长str   
ex:  hellow   owabc 这个就返回2

第二轮 应该是个白人小哥。面经题，棋盘放旗子，第一列0-15，第二列15-30 每一个不能重复，follow up是如果有很多棋盘怎么办，以及怎么优化
（感觉问怎么优化的时候说了几个常规的感觉面试官都不是很满意，一直问还有没有其他的）

第三轮 应该是个中国大哥，以前从来没见过的题，很难描述，大致是几个函数，getValue(), left(), getParent(), getN

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

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

x，结果面完就知道了，第一轮和第五轮都答的特别不好。无论如何move on了已经。好好准备其他家面试！！

好心人求大米啊啊啊啊啊啊啊啊啊，有一些其他公司onsite要准备~~ 再次祝大家新年快乐！！

mrzhu 发表于 2019-1-2 06:37
是啊，看着简单的题往往不好做

第一题 应该用 rolling hash，hash1 从第一个str的尾巴开始 hash2 从第二个str的 头开始。碰到hash1==hash2 的时候 做一个实际的compare确认， 可以linear time， 这个算法写起来和理解起来都比KMP简单很多.        楼主能详细说一下围棋题目吗 。

第一题用类似kmp的方法做？

mrzhu 发表于 2019-1-2 12:13
不好意思我题说的不是很清楚，每一个点的门可以朝四个方向开，问改变哪一个门的方向可以通过

补充内容 ( ...

嗯嗯。那我感觉只要从两边搜索一遍就行了

第一题估计我当场也就只能做出brutal force的解法  

minaj 发表于 2019-1-2 06:34
第一题估计我当场也就只能做出brutal force的解法

是啊，看着简单的题往往不好做

mrzhu 发表于 2019-1-2 06:37
是啊，看着简单的题往往不好做

这题有啥办法，two pointer吗

第一题应该是把第一个string连在第二个后面做kmp，kmp数组最后位置的结果就是答案

第一题用trie怎么样  将自己加入 且每次reverse看看prefix, 也就是dfs trie

应该不会要让用KMP来解，不然完全就是为难人，把第一个string的substring(i, str.length()) d加到Trie里面，对第二个String做搜索就行了. 这种比暴力姐快一些，如果面试官不满意要你用trie，那就是运气不好了。。。

第一题是典型的KMP，找最长proper suffix同时也是prefix

第五轮等价于：我们去掉一个门，可以通过 吧？