亚麻跪经4.2

3.2提交OA2，3.27才给survey，4.2面，今儿挂。

VO：
面试官是个亚洲人，但不确定是不是国人，交流很顺畅也很愉快。。然而没什么用

BQ两道：
在tight ddl的情况下take risk，展现Ownership的一个项目。

十五分钟讲完，全程交流很开心。。然后直接Coding，问了四道题：
1. reverse string，伞思思
2. valid

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

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

果有人知道怎么O(n)解，麻烦告诉我！！

挂了就怪自己菜，面试经验也不足，而且投晚了没赶上好时候，Amazon真是用提莫真实体验告诉我们speed matters。。

祝大家都有好的工作，求加米，好多积分限制200的看不了了

lz，我也是一轮vo，4/1面的今天早上收到据信，希望我们都能在之后拿到大包裹！加油

四道题！！我能写两道就不错了，祝楼主后面好运

python Manacher solution

1. def fix_palindrome(s):
   
2.     N = len(s)
   
3.     count = 0
   
4.     for center in range(N-1, 2 * N - 1):
   
5.         left = int(center/2)
   
6.         right = left + center % 2
   
7.         right_length = len(s[right:])
   
8. 
   
9.         # print(s[:left+1][-right_length:], s[right:][::-1])
   
10.         if s[:left+1][-right_length:] == s[right:][::-1]:
    
11.             break
    
12.         count += 1
    
13. 
    
14.     return count

复制代码

少年。加油

ON: Manacher or KMP

longest palindrome substring ends at the last index?

蠡口上有类似的是从前面补字母使得新的string成为回文

我感觉。。。其实没什么挂点啊。。。LZ加油，会有的

最后一题想了想理论有O(N）做法，就是取个反，然后转为和原字符串求2个字符串前缀和后缀的公共部分，然后用后缀数组+LCP+单调匹配求解，补充长度为全长度-公共部分长度...当然我相信这不可能是面试官想考察的= =...不知道有没有更简单的...
(主要刚想了一道求2个字符串前缀和后缀公共部分的题...套过来= =...

风妖精 发表于 2019-4-5 02:26
最后一题想了想理论有O(N）做法，就是取个反，然后转为和原字符串求2个字符串前缀和后缀的公共部分，然后用 ...

我靠，厉害！！感觉不是想考这个，查了查好像要考是马拉车这种算法。不过多谢你

Wyf2222 发表于 2019-4-5 02:05
ON: Manacher or KMP

好像好真可以，多谢大佬