Suffix Array nlogn的构造是怎么样的? - JobHunting版 - 未名存档

本页内容为未名空间相应帖子的节选和存档，一周内的贴子最多显示50字，超过一周显示500字访问原贴

JobHunting版 - Suffix Array nlogn的构造是怎么样的?

相关主题
● 微软一个面试题	● amazon电面 + facebook 电面
● 问个老问题 Longest palindrome in a string	● G家的电面怎么准备啊？
● ms onsite 杯具，攒rp发面经	● heap sort的缺点是什么？和quick sort比
● 那个常见的histogram max rectangle 问题	● 问个算法题，关于区间 overlap的
● double link list, sort in nLog(n)	● 关于2D, 3D平面上点的问题？
● merge k个数组怎样的方法好？	● 说一题恶心题怎么用nlog n来解。
● 问个微软面试题	● 一题貌似在AMAZON和MICROSOFT都出现过的题目。
● divide array into two, sum of difference is min in O(N)	● 被狗家店面据的莫名其妙，发个面经吧

相关话题的讨论汇总
话题: nlogn话题: suffix话题: array话题: 构造话题: 算法

进入JobHunting版参与讨论

1

(共1页)

g*****i 发帖数: 2162	1 Wikipedia只给出了O(n)的算法reference,这个估计interview也写不出来. 谁能给个容易写的nlogn算法? 谢谢.
a********1 发帖数: 750	2 我想错了，是nlog^2n 当然还是比n^2好我晚上贴上来吧
a********1 发帖数: 750	3 http://apps.topcoder.com/forums/;jsessionid=5C6B808CD2584CDA983 【在 a********1 的大作中提到】 : 我想错了，是nlog^2n 当然还是比n^2好 : 我晚上贴上来吧
B*******1 发帖数: 2454	4 这哥们写的code也挺难学的，其实不就是qsort就好了？
a********1 发帖数: 750	5 主要是要用step＊2比较suffix 直接qsort 的复杂度是n^2 logn ，因为sorting nlogn, 每个compare是n 【在 B*******1 的大作中提到】 : 这哥们写的code也挺难学的，其实不就是qsort就好了？
B*******1 发帖数: 2454	6 觉得面试写这个差不多了。
a********1 发帖数: 750	7 嗯，，不过lz的问题是nlogn的构造感觉快的string算法的基本思想都差不多，就是把已知的比较结果发挥到极限。【在 B*******1 的大作中提到】 : 觉得面试写这个差不多了。
B*******1 发帖数: 2454	8 thanks. very helpful

1

(共1页)

进入JobHunting版参与讨论

相关主题
● 被狗家店面据的莫名其妙，发个面经吧	● double link list, sort in nLog(n)
● 没刷过题的伤不起啊	● merge k个数组怎样的方法好？
● 每次刷题都有新发现	● 问个微软面试题
● google phone interview question	● divide array into two, sum of difference is min in O(N)
● 微软一个面试题	● amazon电面 + facebook 电面
● 问个老问题 Longest palindrome in a string	● G家的电面怎么准备啊？
● ms onsite 杯具，攒rp发面经	● heap sort的缺点是什么？和quick sort比
● 那个常见的histogram max rectangle 问题	● 问个算法题，关于区间 overlap的

相关话题的讨论汇总
话题: nlogn话题: suffix话题: array话题: 构造话题: 算法

未名新帖统计// 7月16日

#	版面	帖数(主题数)
-	全站	4871 (796)
1	Military	3777 (569)
2	Stock	341 (51)
3	Joke	117 (17)
4	History	116 (3)
5	Automobile	100 (9)
6	USANews	55 (9)
7	Midlife	45 (1)
8	Headline	41 (41)
9	Dreamer	33 (13)
10	FleaMarket	32 (20)
11	Living	30 (7)

* 这里只显示发帖超过25的版面，努力灌水吧:-)