l**********1
发帖数: 415 | 1 求问把一个长度为n的string建成suffixTree的时间复杂度是多少？
貌似是是O(n^2)？
第一节点连 n个字母
第二节点连 n-1个字母
...
或有更好的实现？
求牛人解答。 |
|
l*******g
发帖数: 82 | 2 第一题，suffixtree的话要看如何分词了。而且，suffixtree主要是搜索和搜索的精确
度有帮助，如果已经有neg词典的话就map就好了，然后先确定nag词，然后左右察看临
近词，比如is, not, yet, but之类的。这个感觉更像是machine learning sentiment
analysis。
第二题，那个数学的做法，那位再受累解释一下。没太明白。
第三题我觉得可以用conqure merge的做法，一般题目说有一个大数组，大文件，潜台
词就是最好提供一个可以parallel的处理方式，而且不要试图用用memory来存储太多东
西。
前些天面的EBay， onsite。 |
|
l*******g
发帖数: 82 | 3 第一题，suffixtree的话要看如何分词了。而且，suffixtree主要是搜索和搜索的精确
度有帮助，如果已经有neg词典的话就map就好了，然后先确定nag词，然后左右察看临
近词，比如is, not, yet, but之类的。这个感觉更像是machine learning sentiment
analysis。
第二题，那个数学的做法，那位再受累解释一下。没太明白。
第三题我觉得可以用conqure merge的做法，一般题目说有一个大数组，大文件，潜台
词就是最好提供一个可以parallel的处理方式，而且不要试图用用memory来存储太多东
西。
前些天面的EBay， onsite。 |
|
z*******y
发帖数: 578 | 4 字典那道我没有用suffixtree 就是先处理了一下字典 然后找出7个字母的组合
第二个不是Linux命令，就是一道算法题目，用hashtable 就可以了，比较快 |
|
r*******g
发帖数: 1335 | 5 我看你前面回的，如果单个pattern，生成状态转换表，然后对输入
比方说 a*b
initial state s[0],
f(s[0],a)=s[1]
f(s[1],a...)=s[1]
f(s[1],b)=s[2]
现在这里所有已有链接生成一个状态转换表？
如果用suffixtree似乎也不大好。
你说的match一头一尾，难道要单独存储所有pattern的头和尾？ |
|
r*******g
发帖数: 1335 | 6 我看你前面回的，如果单个pattern，生成状态转换表，然后对输入
比方说 a*b
initial state s[0],
f(s[0],a)=s[1]
f(s[1],a...)=s[1]
f(s[1],b)=s[2]
现在这里所有已有链接生成一个状态转换表？
如果用suffixtree似乎也不大好。
你说的match一头一尾，难道要单独存储所有pattern的头和尾？ |
|
g*****i
发帖数: 2162 | 7 当然有,还有专门的paper,面试应该不会考这个的吧.板上一般推荐会suffixarray就不
错了 |
|
|
x*******6
发帖数: 262 | 9 对B建一个suffixtree，然后从里面找出路径为字符串A的internal node，数数这个
node
的subtree有几个leaf。线性复杂度 |
|
n******n
发帖数: 567 | 10 这会让suffixtree写这种题？这是面senior的吧。。。。。。 |
|
j********x
发帖数: 2330 | 11 Suffix tree
弄一个大suffixtree 放所有单词后缀，后缀树上的从root出发的所有路径就是全部
unique 的子串 遍历并且计数
比如考虑当前路径从root到leaf长度为n，则其子串数目为n，每个分支另行统计 |
|
k*j
发帖数: 153 | 12 http://www.cs.cmu.edu/~ckingsf/bioinfo-lectures/suffixtrees.pdf
PAGE 44
Determine the strings in a database {S1, S2, S3, ..., Sm} that contain
query string q:
Build generalized suffix tree for {S1, S2, S3, ..., Sm}
Follow the path for q in the suffix tree.
Suppose you end at node u: traverse the tree below u, and
output i if you find a string containing #i |
|
l*******g
发帖数: 82 | 13 我不是大牛！
我觉得可以用suffixtree来做，或者A* search
好久没碰算法了，哈哈。 |
|
l*******g
发帖数: 82 | 14 通过搜索123得到1234 1235 1237 1238
然后substring之后得到4,5,7,8，从0到9暴力的话我想这是一个constant time
complex。应该可以忽略不记得。
我是这么理解的，这道题看上去是求number，其实，这是一个string pattern搜索的题。
这也是为什么他给了string而不是int类型。因为，要确定这个开始的数其实是要对比
整个字符串之后才能知道，而suffixtree恰恰是用来进行string set搜索的数据结构。
看你题目的例子， string转换成的int array是有序的吧？ |
|
x****1
发帖数: 118 | 15 Linkedin
phone1：烙印
lowest common ancestor w/ and w/o parent pointer
phone2：国人
search in rotated sorted array
onsite:
1.两个国人
implement addInterval(start, end) and getcoverage(),
2.两个国人
talk projects and some behavior question
3.烙印
lunch, talk about technologies interest
4.亚裔，不确定是否国人
Manager, talked a lot of behavior questions, interest and projects
5.烙印
Design: tinyurl
6.烙印+小白
1.exclusive array, give an arr1, return a new arr2, arr2[i] is the
multiplication of all elements in arr1 except arr1[i]
... 阅读全帖 |
|
f******h
发帖数: 45 | 16 也找工作了一段时间了，从版上学了很多，上周G家面完了，求个bless。
之前的一些都挂了，还在继续找其他的。等定下来之后一定发面经回报本版。
谢谢大家啦！！
1. http://www.mitbbs.com/article_t/JobHunting/32005597.html
1) Implement a simple calculator (+,-,*,/);
2) Implement "+1" for a large integer;
3) How to match Ads to users;
4) How to extract useful information from a forum webpage (list all
kinds of useful signal you can think of)
5) How to detect the duplicate HTML pages (large scale);
6) Find all the paths between two places on Google map;
7)... 阅读全帖 |
|
|
