d****o
发帖数: 1055 | 1 我还是好好看一下suffix tree吧。怎么没有懂呢。
n^ |
|
s*********e
发帖数: 197 | 2 用suffix array，可以有O(nlogn)。在programming pearls第二版的15.2有详细讨论。 |
|
l*****a
发帖数: 14598 | 3 有一次研究重复子串/最长子串的题目，在网上查到一篇文章
才知道这些题目都可以用suffix tree解决 |
|
c****g
发帖数: 85 | 4 刚好我也看到programming pearls这章。
string sorting 需要O(n^2*logn)？不是吧。而是和平均字符串d相关。
string array的结构满简单，容易理解的。还没看suffix tree。貌似没书讲，只能
google了。
/2。 |
|
W******g
发帖数: 887 | 5 啊？怎么实现？KMP? fingerprint? suffix trie? 直接比较？ |
|
a*******y
发帖数: 1040 | 6 这个你怎么写build suffix tree的code？不可能当场完成吧，我觉得还得有另外个方
法来写code |
|
b*******d
发帖数: 750 | 7
写N^2的方法来build suffix tree应该不是很难？ |
|
a*******y
发帖数: 1040 | 8 ok， I got it
use a suffix array, then sort it( remember index when you sort), now
repeated substring must occur in neigbor, compare two by two to find two
they have common prefix, and if the common prefix length equal to their
index difference +1 , that would be the answer |
|
g****y
发帖数: 240 | 9 for each "famous" number sequence, construct a suffix tree for it? |
|
b*******d
发帖数: 750 | 10 除了上边说的suffix tree之外，
一个比较粗的想法:
很多“famous” sequence都是指数级增长，所以越界是比较快的（assume，相信几百
万个这样数之后就overflow了，那么存下来也就是几个M而已）。对于很大的数，可以
直接标记是否他们是fabonacii数or not。对比较短的数列，标记几个level的inverted
index，如上边说的3连续，4连续，5连续，6连续。6连续的话就已经是shingle了，算
得上是finger print了，查询可以非常快的。 |
|
p*****2
发帖数: 21240 | 11 感觉这种题考到的概率基本为零吧？尤其是需要你编码。 |
|
g****y
发帖数: 240 | 12 对于longest repeated substring problem. 可能的solution只可能是internal node
，不可能是implicit node。
用o |
|
w*********0
发帖数: 48 | 13 貌似答案不是最佳的线性时间线性空间啊
找到UKK算法看，云里雾里的。。。
面试时候需要写最佳的UKK算法么。。。 |
|
n***i
发帖数: 777 | 14 讲讲思路差不多了吧，你觉得有谁能够现场写出这个code |
|
w*********0
发帖数: 48 | 15 如果有勤奋的背过code 也说不定呢。。。呵呵 我只是瞎猜。。。 |
|
|
i***h
发帖数: 12655 | 17 suffix array is much easier to implement |
|
i***h
发帖数: 12655 | 18 DP和suffix array没什么直接关系吧 |
|
j******2
发帖数: 362 | 19 我的意思是：longest common substring这个问题的DP解法就是用DP来算suffix array
的长度。 |
|
i***h
发帖数: 12655 | 20 不用DP,
suffix array排序, 然后过一遍就行了
array |
|
C***U
发帖数: 2406 | 21 你应该google一下suffix array及算法 |
|
C***U
发帖数: 2406 | 22 是有些麻烦。。。。我觉得现场写不太可能把。
我的算法课的project就是做linear time suffix array construction + wavelet
tree 来实现string match
当然大牛可能有很简单的 办法实现 |
|
j******2
发帖数: 362 | 23 多处看到这个结论。但是想不通啊，难道不是要quadratic time吗？比如所有字符都不
一样。 |
|
|
|
r*****e
发帖数: 264 | 26 来自主题: JobHunting版 - G家电面筋 第二轮第一问用hash可以做到O（n），用suffix trie可以做到O（m） |
|
h****n
发帖数: 1093 | 27 最近A家感觉很缺人，组织了很多不需要电面的group onsite event
小弟也有幸参加了一次这种onsite，接到recruiter的邀请，准备了一个月参加了
Amazon的面试。不过可能还是由于准备不充分并且是第一次面试，最后挂了，说说过程
，求大牛分析为什么挂了
第一个是一个白人年轻GG，上来寒暄了一阵子，大概介绍了一下自己的research，貌似
他不怎么感兴趣，接着开始问behavior问题，印象比较深的是问了一个如果项目中有很
多bug，但是deadline快到期了，你会怎么办，我说首先我会尽量想办法fix掉bug，如
果还是预期还是没法fix完可以找manager多allocate一些resources，比如多一些人手
来一起fix bugs。我说任何bug都有可能导致程序崩溃，那个GG貌似很不满意，继续问
，如果这些bug很不重要呢，举了个例子，我没听清，大体就是和产品功能无关之类的
，我说我会找manager商量商量要不要忽略这些bug继续deliver产品。感觉他还是很不
满意。。。
然后开始问coding题，coding题其实满简单的，就是一个字符串的str... 阅读全帖 |
|
c********t
发帖数: 5706 | 28 赞面经。
先删除invalid,并转lowercase
然后用Manacher's algorithm 或者 suffix tree?
你是这样答得吗？
code 题：Given 这样的string “ ni hao! 32hi, ?? ih 23 oa! h ?i ~n ”
判断是不是会文，只考虑数字，字母是valid，然后A=a, B = b
写完要我给一些test case
然后说我的solution 他满意。
ebay |
|
c***w
发帖数: 134 | 29 上次a家onsite，让我画一颗树，并且写出api。 |
|
d**********x
发帖数: 4083 | 30 后缀树是什么
你问面试官，面试官一半以上都不知道 |
|
|
|
|
|
c********t
发帖数: 5706 | 35 我是说你从打击中恢复的能力，马上回到学习状态，很厉害。
下周我也要onsite，准备的比你差多了 |
|
g*****e
发帖数: 282 | 36 我问google面试官朋友，他说goog根本没希望你用trie这种高级数据结构来解。用还不
错的算法，fast/bug free coding和清晰的思维和交流才是他们看重的。一家之言 =) |
|
c********t
发帖数: 5706 | 37 先猜用suffix tree,再慢慢想设计
。 |
|
|
K*********n
发帖数: 2852 | 39 刚跟Yelp的小帅哥Skype过了，半个多小时就匆匆结束了。我是master in CS，申的是S
DE New Grad。
先简要介绍他自己，然后问我做过的project，我说了俩，用了十分钟。
然后问了三个问题：
1. 当你在浏览器输入地址然后敲回车之后，一直到你看到想要的内容，这期间都发生了
什么，描述了一下。
这方面我不是专家，我就high-level说了，地址嘛，被翻译成IP，定向到网站的服务器
，然后地址后面的suffix用来query服务器，得到内容传回来，比如是个html文件，那么
浏览器就就parse它，显示出来。超级超级业余的回答啊。他说好，看起来你挺了解的。
2. 比如在Yelp网页上，有一块区域是当地你关心过的商业POI(Point of Interest)的更
新，或者朋友的推荐的更新，如果你要手动刷新这一快更新，结果反应是很迟钝，很慢
，你会在服务器端寻找什么问题？
我说，可能不同的地域和不同类型的POI分别存在不同的机器上，跨机器的query会很慢
，因为POI在机器上的组织形式可能不符合我query的要求。他说忽略这个，假如所有数
据都在一个大datab... 阅读全帖 |
|
i****y
发帖数: 58 | 40 我只要看到B-tree就浑身一抖。。。有同样效果的还有suffix tree。。。看来准备还
是不到家啊。。。 |
|
p*****e
发帖数: 1611 | 41 来自主题: JobHunting版 - G/F面经 多串模式匹配做好的方法可能是suffix array+LCP
预处理O(m)，然后每个query的复杂度是O(n+lgm) |
|
p*****e
发帖数: 1611 | 42 来自主题: JobHunting版 - G/F面经 suffix array + LCP写code的话也要跪……
因为LCP如果要O(n)的话还要写RMQ... |
|
c*********n
发帖数: 1371 | 43 准备的实在是不怎么样. 先是一个三哥，随便聊聊做过的东西，因为我现在一直在用c#
，就问一下c#和java的区别。然后是millions integer里面找5个最小的。然后是电话
里里面找所有没有用过的号码，然后限制内存的使用，找别的存储号码的方式。再之后
是非常弱智的删除linkedlist中间节点的题目，我也非常弱智的没有做出来。。。。。
。。
之后问了问java的一些基本概念。
之后听口音应该是个老中，或最少是亚裔。也是先随便聊了聊project，估计我说的不
太清楚，他没再问下去。之后是2个数组找最大common substring, 当时有点蒙，知道
用DP可以做，但很久没有用过了，没什么思路，后来这个哥们提醒可以用suffix tree.
之后也是一个限制内存的使用，存储数据关系的题目，用bitmap就解决了，但当时也蒙
了，没往2维数据上想。
估计是挂了。
总结，看来不管工作没工作过，做题是肯定面不了了。很多东西还是得花时间复习一下
，否则连这种最基本的题目都做不出来。。。。 |
|
|
c********t
发帖数: 5706 | 45 “之后是2个数组找最大common substring, 当时有点蒙，知道用DP可以做”
应该是两个string找最大common substring吧，suffix tree 说出来以后不会要实现吧？ |
|
D**********d
发帖数: 849 | 46 第一题 DP
f(str1,str2) = max{f(str1-1,str2), f(str1,str2-1), g(str1-1,str2-1)+ str1[
end] - str2[end]},
where g(str1,str2) is the max distance of suffix.
s2 |
|
f*****e
发帖数: 2992 | 47 你是搞生物的吗？第一题可以用suffix tree做吗？ |
|
f*****e
发帖数: 2992 | 48 最长重复字串，建suffix tree的时候，最长重复字串就是增长点的起始点。 |
|
l***i
发帖数: 1309 | 49
suffix array, look for longest comment prefix. |
|
c********t
发帖数: 5706 | 50 pat pat, 感觉面得不错，可能local招的人少，hiring bar更高。
第一题如何解？我觉得删除是不是就类似删除linkedlist里面一个节点，很容易。但插
入怎么办？难道不要搜索找插入的位置吗？
假如有一个iterator，可以对chain的hash table进行iterate，它有两个函数,next(),
hasNext().问我如何修改hash table的插入和删除操作以维护这个iterator的数据结
构。当然，hash table本身的操作是O(1)的，所以要求
维护这个数据结构的时间也是O(1)。
第二题前缀搜寻，为什么不用trie, 而用后缀树呢？你最后给的结构是节点是BST的
suffix tree,然后叶子节点有权重值？
他说chrome地址栏有个功能，就是输入一个词的时候，会跳出以输入的字符为前缀的
suggestion，这些suggestion是从历史记录和书签来的。问我对这个实现的数据结构有
什么看法。我说了一下需要记录每个书签的content以及最近
访问的次数，然后根据访问次数排序。他又问那假如有连个书签，一个是在一个月之前
访问了500次... 阅读全帖 |
|
