R**y
发帖数: 72 | 1 TripAdvisor, 旅游内容生成推荐类网站
phone Interview 两题
Array rotation.
Index i -> index i + k, 数组旋转 这题比较容易
找出一个string 最长的回文子串
没见过，直接跪了，后来发现这题比较经典，其实解法也比较直接
1. 暴力解法 C(n,2) 选出start 与 end 的index，然后判断这个sub string是不是回
文，返回最长长度的start 与 end index O(n^3)
2. 高级解法，选出可能结果回文的中心index，然后利用这个 middle index 对称构造
substring，找出最长长度的 start 与 end index O(n^2)
3. 构造suffix tree, 然后找出最长回文子串 O(n) 这种解法暂时不熟悉
第二题没答好，暴力解法都解错了，当时一紧张，都不知道如何动手了，暴力解法的思
想反倒是最直接，最通俗的，可惜了。
应该被默剧了，默默的安慰自己了
--------------------------------
我发现板上大家的关注点都在AMFLG上面了，其实还是有很多优秀的企业的 |
l***i
发帖数: 1309 | 2 problem 2, Manacher's algorithm can do O(n) without suffix tree. |
z***2
发帖数: 66 | |
r*********n
发帖数: 4553 | 4 3. 构造suffix tree, 然后找出最长回文子串 O(n) 这种解法暂时不熟悉
是不是用suffix tree找字符串和反字符串的longest common substring？ |
z*f
发帖数: 293 | |
x*****0
发帖数: 452 | |
i******r
发帖数: 793 | 7 以前电面过，写了个程序，自己感觉完全正确
结果面试官说我不够practised，拒了 |
R**y
发帖数: 72 | 8 TripAdvisor, 旅游内容生成推荐类网站
phone Interview 两题
Array rotation.
Index i -> index i + k, 数组旋转 这题比较容易
找出一个string 最长的回文子串
没见过，直接跪了，后来发现这题比较经典，其实解法也比较直接
1. 暴力解法 C(n,2) 选出start 与 end 的index，然后判断这个sub string是不是回
文，返回最长长度的start 与 end index O(n^3)
2. 高级解法，选出可能结果回文的中心index，然后利用这个 middle index 对称构造
substring，找出最长长度的 start 与 end index O(n^2)
3. 构造suffix tree, 然后找出最长回文子串 O(n) 这种解法暂时不熟悉
第二题没答好，暴力解法都解错了，当时一紧张，都不知道如何动手了，暴力解法的思
想反倒是最直接，最通俗的，可惜了。
应该被默剧了，默默的安慰自己了
--------------------------------
我发现板上大家的关注点都在AMFLG上面了，其实还是有很多优秀的企业的 |
j****1
发帖数: 99 | |
c******t
发帖数: 391 | 10 LZ能讲下数组旋转的detail么？ 是让inplace rotate一个array？ |
