l*******g
发帖数: 82 | 1 哈，不好意思，晚上睡前没仔细思考。这个应该用suffix tree做。吧整个字符串序列
存入suffix tree，然后搜索1234这样子。比如 1234 1235 1237 1238
当搜索suffix tree的时候只要搜索到123，那么1234，1235，1236，1238都会返回，这
样在判断返回的序列是不是连续的就可了。
只要遇到999之类的加一搜索就可以了。
就是找Missing int,但是输入不是int arr,而是一个string.比如 123456891011
output 7 |
|
k****s
发帖数: 16 | 2 这个思路非常好。
问题应该只出现在真实pattern的prefix和suffix相同。
1. prefix和suffix相同且不为同一字母，之前方法（直接看到从前）可解。
2. prefix和suffix相同且为同一字母，这就必须得Pattern+1了。
所以只需要找到pattern第一个和首字母不同的字母。每次比较如果是match它出问题，
那么Pattern+1, 否则就 直接看到从前。
比如 aba aba 失败在第三个a 应该match的是b，所以pattern+1
aaaba aaaba最后失败在aaabaaa[a]，应该match的是b，所以pattern+1.
更新完pattern后，只需要把当前match的b前移一位match，来保证O(n) |
|
k****s
发帖数: 16 | 3 这个思路非常好。
问题应该只出现在真实pattern的prefix和suffix相同。
1. prefix和suffix相同且不为同一字母，之前方法（直接看到从前）可解。
2. prefix和suffix相同且为同一字母，这就必须得Pattern+1了。
所以只需要找到pattern第一个和首字母不同的字母。每次比较如果是match它出问题，
那么Pattern+1, 否则就 直接看到从前。
比如 aba aba 失败在第三个a 应该match的是b，所以pattern+1
aaaba aaaba最后失败在aaabaaa[a]，应该match的是b，所以pattern+1.
更新完pattern后，只需要把当前match的b前移一位match，来保证O(n) |
|
e**********y
发帖数: 128 | 4 不是很理解最后一句 “suffix match: 一个非suffix但等于suffix的substring。”
楼主能把问题用个例子解释一下吗？ |
|
a******u
发帖数: 69 | 5 比如说input: banana
suffix match:
a
na
ana
但nana就不是了。它不是一个非suffix但等于suffix的substring |
|
M****e
发帖数: 2803 | 6 前两天被指责有deal不通报，今天看到个Suffix braided line的deal，不知道有没有
人发过。
Dick's suffix braided line 300 yard原价30.99，现在有10刀mail in rebate，外加
用上$10 off $25 的coupon，相当于$12刀一圈，超值啊。
PS：个人感觉suffix的线比PP似乎好用一些。 |
|
s****s
发帖数: 628 | 7 为什么html page 做view page 就不行? 报错:
no mapping found for http request with uri in Dispatherservlet...
jsp page 就没问题.
现在用的是internalresourceviewresolver.
我的mapping没有问题.
把阅读全帖 |
|
x*z
发帖数: 1010 | 8 这个的边界条件很直观啊，就是转换到程序上比较麻烦，如果有[]，
就把[]里的所有东西当一个整体处理，[]前后分别是prefix/suffix，
如果没有[]，那就是一个整体，无所谓prefix/suffix，因为我只要
这个string就行。
比如上面的例子
input='r0[0-1,9,11-12].abc, d23.def'
这个就是两段，第一段'r0[0-1,9,11-12].abc'，第二段'd23.def'，
然后要对第一段[]内做展开，prefix='r0', suffix='.abc'。第二段
不需要处理，直接添加到最后结果就行。
[]内的展开部分我都写好了，但是前面分段还没想好怎么处理。 |
|
S*A
发帖数: 7142 | 9 这个边界条件是 prefix/suffix 由什么东西字符组成是合法的。
例如 prefix/suffix 里面可不可以有 [] etc.
我给你的例子里的 re.sub 加上 replacement 的函数就是你想要的。
在 expand() 里面返回如何展开一个 prefix[...]suffix 就成了。 |
|
n******t
发帖数: 4406 | 10 是字符操作.不是字符串操作.一般的Ram model.
这个算法主要是建立在suffix tree的处理能力上面.
在建立好suffix tree之后(linear time), 对于每个
LCE的应答在常数时间内可以完成.有兴趣可以查查
suffix tree的算法. |
|
n*******r
发帖数: 12 | 11 关于suffix tree的
suppose suffix trees are available for text files T1 and T2. Given that
you wish to efficiently determine if a given pattern p appears in the
concatenation T1T2 of the two text files, how would you proceed.
简单的说，就是有文件T1和T2（纯文本文件）的suffix tree，想查找一个长度n的字符
串p是不是出
现在T1T2中。请给出有效的算法。 |
|
f***c
发帖数: 338 | 12 写了一段代码，用g++编译顺利通过。
想到前几天曾讨论过编译器对int main(),void main()的处理不同问题，就顺手试了cc
和gcc。这一试不打紧，居然都不能通过。
OS: Debian GNU/Linux 6.0.3 (squeeze)
然后就看看个编译器的version，居然是一样的。但是对同样的代码的编译处理区别怎
么这么大呢？
彻底懵了，请达人解惑，谢谢。
g++ -v
Using built-in specs.
Target: x86_64-linux-gnu
Configured with: ../src/configure -v --with-pkgversion='Debian 4.4.5-8' --
with-bugurl=file:///usr/share/doc/gcc-4.4/README.Bugs --enable-languages=c,c
++,fortran,objc,obj-c++ --prefix=/usr --program-suffix=-4.4 --enable-shared
--enable-multiarch --enab... 阅读全帖 |
|
发帖数: 1 | 13 WHY IDO?
http://idolinguo.org.uk/whyido.htm
NOTE: Because of the difficulty of showing Esperanto's special accented
letters, where a letter which in Esperanto should carry a circumflex it is
shown here followed by a circumflex (^), and where the letter 'u' should
carry a breve it is followed by a tilde (~).
The idea of using a constructed language as a medium of international
communication - not replacing existing languages but supplementing them - is
far from new. The first such language to ach... 阅读全帖 |
|
f*********d
发帖数: 3358 | 14 Capture with a Firefox extension
There are many reasons why Mozilla Firefox is our favorite Web browser, and
one is because it makes grabbing online videos so easy. This tip for Firefox
works with both the Windows and Mac versions.
Adding new features and customizing Firefox is simple to do with extensions.
Extensions are typically created by other users and are simple to search
for and add. To see your browser's list of extensions, select Extensions
from the Tools pull-down menu or hit the ... 阅读全帖 |
|
N*******w
发帖数: 15 | 15 (1) Imagine there is a square matrix with n x n cells. Each cell is either
filled with a black pixel or a white pixel. Design an algorithm to find the
maximum subsquare such that all four borders are filled with black pixels;
optimize the algorithm as much as possible.
(2) Given an arbitrarily long string, what is the most efficient way to find
out the first repeating character?
(No Suffix Tree algorithm)
(3) Find the longest parlindrom from a string.
(No Suffix Tree algorithm) |
|
g*******y
发帖数: 1930 | 16 这两天写了几十道题目的code，挑几个有疑惑的问问大家
1.Find the largest rectangular matrix with 1's
//网上倒是有个Dr.***的网页上有解答。不过个人认为这题做为面试题过于难了。
2.Wildcard string matching(suffix tree)
//同样觉得面试做suffix tree的题过于难了。
3.怎么组织字典，使得在解cross puzzle时可以很快得到满足条件的所有单词.比如所
有第二个字母是o，第5个是H的单词。
//感觉找不到很好的预处理/加速的方法
4.coding test. 两个不同的link list, node buffer size不一样. 从一个link list
的node考贝到另一个list.
//理解不了题意
5.Write the code to print a Binary tree level by level STARTING FROM THE
LEAF LEVEL
//同时用栈和队列很简单，找一个比同时用栈和队列更好的方法？
6.Give three methods to c |
|
y*******g
发帖数: 6599 | 17 suffix tree 的确太复杂。不过suffix array 还可以吧 |
|
g*******y
发帖数: 1930 | 18 use trie with max level k. suffix tree is trie with path compression. But
for this problem, I would not bother using suffix tree.
if you are allowed to ignore any pre-processing cost, then:
1. for each word, sort letters, then use the find_all_combination() algorithm to find all combinations of k letters
2. for each combination, search a leaf in trie. (If no leaf found, add a leaf which stores the current word.)
3. check if the current word is longer than the word stored in the leaf node. If |
|
f*********r
发帖数: 68 | 19 这题要用suffix tree 或者suffix array. 然后求LCP判断一下就可以了
one. |
|
g*******y
发帖数: 1930 | 20 我们算法课作业题
用suffix当然是最好的
不会suffix的话，用DP有两种复杂度
一种是O(A.size * B.size * dist.size)
一种是O(dist.size^2) |
|
b******7
发帖数: 79 | 21 geniusxsy， 能否指教怎么用suffix tree或者suffix array做啊？ |
|
a*********7
发帖数: 30080 | 22 来自主题: JobHunting版 - 新鲜面试题 是不是可以先把split query into a few parts, for example, *o*ve*ou => o, ve,
ou, 然后用其中一个先query（这步可以再优化一下，比如说先用最长的一部分）；
得到的结果处理一下，比如说用ou做query，得到iloveyou.com, itveabou.com，处理
后就变成了ilovey，itveab；再用ve对处理过的结果做query。。。
是个比较笨的方法，呵呵
into
a few parts, for example, *o*ve*ou => o, ve, ou, 然后分别用o, ve, ou 查询，
但是似乎不适合这道题。 另外，如果对Index里的每一个URL建suffix tree ，然后对
每个query check againgt 所有的suffix tree, 这样实际上就是scan all urls, 明显
也不合适。但是排序？我想不出来。 |
|
g*******y
发帖数: 1930 | 23 很多都是老题，不过我专门整理了一下：
1. string match:
string Text, Pattern;
find a substring of Text matches with Pattern.
解法纲要：Rabin-Karp, KMP, suffix tree
变种1b: multiple match:
string Text, PatternSet[n];
find a substring of Text matches with any one pattern in the set;
解法纲要: Rabin-Karp
2.LCSubstring:
string A,B;
find the longest common consecutive substring;
解法纲要：DP(A.len*B.len复杂度)，suffix tree(A.len+B.len复杂度)
3.Longest Palindrome
string A;
find the longest substring of A which is a palindrome;
解法纲要：类似2
4.Wild |
|
h*********e
发帖数: 56 | 24 如果非得用suffix tree，能不能转化成exact set matching？
"www.i" occurs at index X = {x1, x2...}
"a" occurs at index Y = {y1, y2...}
"c.com" occurs at index Z = {z1, z2...}
Building the suffix tree and matching can be done in linear time. Then,
pattern occurs in text iff the following has solution:
y-x >= 5
z-y >= 1
x, y, z from X, Y, Z
不知道这方程组有没有线性解法。 |
|
a******2
发帖数: 393 | 25 我问了 要用第一个函数 对方说是
然后我说用suffix tree
他先让我解释什么是suffix tree，完了之后说写code吧
我就奔溃了
不用的话我只能想到O(n*n)的 |
|
c******f
发帖数: 2144 | 26 怎么能保证“the length of largest common substring between x' suffix and y's
prefix is K-m”这样的字符串一定能够造阿？有没有什么理论的证明？ 我画了一些
图倒是都对 而且我知道 如果是string来构造graph的话 用的就是这个方法
value to make reduction possible), and this is the length of each string we
will use. So, we reduce HP problem by: if for two nodes X, Y and the weight
of their edge is m, then we convert the node to 2 strings x', y', such that
the length of largest common substring between x' suffix and y's prefix is K
-m( when K is large enough, this is p |
|
j**l
发帖数: 2911 | 27 什么KMP, Rabin-Karp, BM, Suffix Tree, Suffix Array, 能用上的请尽量用
1. Write a function f(a, b) which takes two character string arguments and
returns a string containing only the characters found in both strings in the
order of a. Write a version which is O(n^2) and one which is O(n).
2. Given that one of the strings is very very long , and the other one could
be of various sizes. Windowing will result in O(N+M) solution but could it
be better? May be NlogM or even better?
3. Given that you have one str |
|
I**********s
发帖数: 441 | 28 问了1) 研究, 2) 多线程程序设计, 3) 任意无穷字符串流, 内存有限, 找出唯一一对
重复字符串, 这个我说了哈希表和外部排序, 但是面试人说有更好的办法(后来想也许
是bloom filter), 然后追问外部排序的细节到结束. 估计要挂 :(
总结: 面试既是技术活, 又是运气活.
无论如何, 把我的准备工作放下面, 攒点rp, 希望对大家有所帮助.
Interview Qs
Data Structures
1. Integer
- find number of 1s
- next largest smaller
- smallest larger number
- determine if is palindrom
- itoa, atoi
- add 2 numbers w/o using + or arithmetic operators
- implement *, -, / using only +
- find max of two numbers w/o co... 阅读全帖 |
|
l*****a
发帖数: 14598 | 29 DP for the last one???
i think we can get it directly with 2 loops
or suffix array/generalized suffix tree
case |
|
z***e
发帖数: 5393 | 30 I like your solution, simple, clean, easy to maintain.
yes, DP is common for LCS alike problems. However, this problem, is not the
type for DP. If people try to struggle with DP/Suffix, he is simply waste
time (OK, you will be super if you can do it by DP on whiteboard without ANY
bug within 15 mins).
many ppl like to talk about suffix tree --- can u really code it within 10
mins on whiteboard? |
|
h**k
发帖数: 3368 | 31 prefix 一定是要从头开始匹配，而suffix允许从字符串的任何一个位置开始匹配。
所以prefix相当于generalized suffix tree的边的一个子集。
呢? |
|
x***y
发帖数: 633 | 32 First of all, find Longest Common extension of sequence(which uses matching
statistics in suffix tree and constant time LCA to find length of longest
substring that start from any positions at 2 string in constant time after
linear preprocsing)
2nd, find all maximal palindromes (which means that if A[i:j] is palindrome,
then A[i-1:j+1] can not be palindrome) in linear time with the help of
suffix tree and Longest Common extension.
3rd, find the segments in the original sequnce that satisfes the ... 阅读全帖 |
|
P*******b
发帖数: 1001 | 33 longest repeated substring （overlap vs non-overlap)
这个题怎么做？
suffix tree吗？有没有别的办法？
suffix tree的话现场写程序好难啊。
thanks |
|
A*********3
发帖数: 70 | 34 Phone 1:
1.提出尽可能多的方法使一个method可以返回多个不同type的值
2.reverse string
比如 "I have a dream" -> "dream a have I"
3.判断一个binary tree是不是对称的
Phone 2:
1.给a list of number，返回前top K个（内存足够怎么做，内存不够怎么做）
2.OOD 电梯
3.找两个链表的交集
Onsite 6轮 1轮HR 1轮午餐 4轮技术 （亚马逊网络服务组）
签了保密协议，希望不要被抓到T_T
1.设计个电话本 可以用那些数据结构
我说suffix tree, 哈希表
问了这两种方法的比较，还考了suffix tree的插入，
2.问research, OOD 交通灯系统
3.写函数算一个整数的阶层 n!
又问了n很大，怎么办？
比如99%的n都在400000-900000之间，怎么提高函数的执行速度
4.给一个数组和一个数n，找出数组中的所有的对和等于n的
5.给手机键盘，给定某个按键序列比如‘1489’，返回这个按键序列生成的所有的正确
的单词
... 阅读全帖 |
|
t**********n
发帖数: 145 | 35 多谢分享！Bless！
保密协议我仔细阅读了一下，
只是说不能透露跟Amazon的业务有关的内容就好了。
面试题应该都不在其保护范围内的。
呵呵。
Phone 1:
1.提出尽可能多的方法使一个method可以返回多个不同type的值
2.reverse string
比如 "I have a dream" -> "dream a have I"
3.判断一个binary tree是不是对称的
Phone 2:
1.给a list of number，返回前top K个（内存足够怎么做，内存不够怎么做）
2.OOD 电梯
3.找两个链表的交集
Onsite 6轮 1轮HR 1轮午餐 4轮技术 （亚马逊网络服务组）
签了保密协议，希望不要被抓到T_T
1.设计个电话本 可以用那些数据结构
我说suffix tree, 哈希表
问了这两种方法的比较，还考了suffix tree的插入，
2.问research, OOD 交通灯系统
3.写函数算一个整数的阶层 n!
又问了n很大，怎么办？
比如99%的n都在400000-900000之间，怎么提高函数的执行速度
... 阅读全帖 |
|
g*****x
发帖数: 799 | 36 build suffix tree of S1, check if S2 contains in the suffix tree, this
should take O(n) |
|
g*********s
发帖数: 1782 | 37 那个实在太长了。我提炼了一下。似乎很难啊。
啥是soduko test？
最长回文的算法到底是啥？
sum of square是哪个经典算法？
发信人: evaeva (evaeva), 信区: JobHunting
标 题: 生物PHD 转行找CS， 报Offer和罗嗦的面经
发信站: BBS 未名空间站 (Sat Mar 19 06:10:37 2011, 美东)
背景: 生物phd, WSN, 计算机 master.毫无工作经验，无实际project经验
不在Google总部，面了５个人，
第一个负责论文讨论，ＥＥ背景，写底层code, 工作性质类似于打杂。
第二个问了简单的SODUKO ＴＥＳＴ。 我写了一白板，和他讨论了下各种方法的复杂
度，就混过
去了。他自己做的东西也很简单，不懂ＭＬ，就做做数据库，写C 的。
第三个ＡＵＴＯＭＡＴＩＯＮ背景，做ADword。做题找最长回文。反转找最长相同加
suffix tree
不对。用简单的方法，n2 和n3。最好方法就是suffix tree。
第四个是JAVA person. 问把整数分成 sum of square的经典问题。... 阅读全帖 |
|
g*****i
发帖数: 2162 | 38 这个是学校考试题,要写出o(n)的建suffix tree的方法不容易把.建suffix tree我觉得
自己很难写,. |
|
o*****e
发帖数: 99 | 39 Use "Generalized Suffix Tree."
节点存储出现次数(counter)。
After constructing the suffix tree,
Then the problem is converted to:
find max 节点 whose length =3 |
|
c*****t
发帖数: 13 | 40 本人CS硕士名校非牛人,一年前去了一家中型软件公司做SD,不喜欢,刚刚跳去一家小HF.面试
的过程好像西游记一样,路途遥遥,艰险不断,怪物层出不穷,自己的本领也日渐增长,2年来承蒙
版上各路豪杰照顾分享,今日也算有个结果;特此拿出小弟所见所闻共勉,纪念找工作的艰辛,愿
大家早日心想试成,取到真经!
/***********************
小测验
***********************/
首先来个小测验,看你能看懂多少
1.array,list,BST,Hashtable,queue,stack,suffix tree,collection...
2.BFS,DFS,DP,D&C,Greedy,Dijkstra,tree traversal,recursion,quick
sort...
3.A,F,G,L,M,O,T,Y...
4.OOP,GC,Polymorphism,interface,abstract class,singleton...
5.bar raiser,white board programming,lunch interview..... 阅读全帖 |
|
a*****a
发帖数: 46 | 41 问一下，网上都说用suffix tree可以linear time完成，据说是用 txt$reverse(txt)#
建树然后找最长枝（不就是找最大common substring），但是那样的话怎么剔除不连
续的情况呢？
比如 abcdeecba
树里最长的应该是abc而不是ee吧？
如果对每一枝都去判断是否是palindrome，那不就n^2了么？
是不是我对suffix tree方法的理解有问题？！
谢谢！ |
|
F**r
发帖数: 84 | 42 suffix tree O(n), construct new string S~S^, where ~ is a character
not in S, and S^ is the reverse of S. then consider odd and even
substring separately, very similar.
for substring center at j, where 0<=j
can tell you LCP of two string in O(1), so complexity to find
maximum palindrome is O(n).
I think straight forward approach or DP or KMP is more reasonable
solution for this problem during the interview.
in O(n) |
|
G******i
发帖数: 5226 | 43 ☆─────────────────────────────────────☆
currant (葡萄干) 于 駡 提到:
/***********************
小测验
***********************/
首先来个小测验,看你能看懂多少
1.array,list,BST,Hashtable,queue,stack,suffix tree,collection...
2.BFS,DFS,DP,D&C,Greedy,Dijkstra,tree traversal,recursion,quick
sort...
3.A,F,G,L,M,O,T,Y...
4.OOP,GC,Polymorphism,interface,abstract class,singleton...
5.bar raiser,white board programming,lunch interview...
如果以上任何概念不能熟练给出详细解答,请在往下面看之后抓紧复习1.数据结构(这个如果一
个没看懂可以按后退关窗口了)2.算法3.公司背景4.面向对象编程5.on... 阅读全帖 |
|
|
|
z*******y
发帖数: 578 | 46
suffix tree肯定行，不过电话interview这点时间 建树的code还是挺challenging的
呵呵
suffix tree的code不太好写
我觉得他可能就是想让我写那个KMP算法 |
|
g*****i
发帖数: 2162 | 47 bless?楼主什么背景? fresh graduate吗?
第一题我觉得不需要完整的suffix tree,因为题目只要找longest prefix,所以就把每
个string的插入一次就可以了,还可以记录当前的longest prefix的长度来加速. 另外
linear suffix tree construction好像很复杂吧.
第二题如果文件在memory放不下怎么办呢?
第四题每个server的os image都一样吗?如果一样的话应该是类似找一个快速扩散的方法
第七题这种多线程题没经验的总觉得很麻烦啊,楼主说的unblock型是什么意思? |
|
r*******g
发帖数: 1335 | 48 suffix tree，据说有O(n)的算法，因为求LCA可以O(1)，但是我能想到的也只是O(
nlogn)，因为怎么也不知道LCA如何O(1)算。具体就是，构建两个suffix tree，然后算
n次，每次都是去找LCA。 |
|
y*******g
发帖数: 6599 | 49 有O(n) suffix tree的构造算法，不过现场写code还是用sorting (NlogN)来构造
suffix array比较现实，programming pearls 讲过 |
|
