B*******1
发帖数: 2454 | 1 用suffix tree可以做到o(n),但是现场面试肯定不可能当场写这个suffix tree的。
有另一个解法是lcs(str, reverse(str)），
但是这个方法对于这种string不适合，"abcfghicba"
出来的结果会是abc，是不是这种情况下可以做post-processing,再check得到的这个
substring是不是palindrome啊。
thanks。 |
|
d*******d
发帖数: 2050 | 2 suffix array/ suffix tree都只能找到lcs,
但是没有解决他的问题.
tree |
|
a********1
发帖数: 750 | 3 suffix array可以保存suffix的index
这样check palindrome可以在search的时候check
而不用找完再check |
|
a***r
发帖数: 93 | 4
That's not my post, I just curious about how to do it using DP.
There are a few solutions:
1.programming pearl - suffix array O(n^3)
2.suffix tree
3.DP
To slove with DP, first thing is to figure out the sub-problem, I am not
sure what's the sub-problem, that's why I am asking. |
|
S**I
发帖数: 15689 | 5 ☆─────────────────────────────────────☆
gzou (gzou) 于 (Thu May 12 02:26:35 2011, 美东) 提到:
马上就要G on site了，
求祝福。
下面是从本版收集到的Google的试题，便于大家查询。
申明：有的附带有解释说明的，也来自于本版或者网络，大家自己看， 不保证真确
http://www.mitbbs.com/article_t1/JobHunting/31847453_0_1.html
本人ECE fresh PhD，背景是电路/EDA，跟G业务基本没什么关系
同学内部推荐的，很简单的一次电面就给了onsite
题都不难，但是自己没把握好机会，出了一些小bug。
总的感觉，出错就是硬伤，宁可从最简单的算法写起，也不能出错。
电面：
1，Skip list， http://en.wikipedia.org/wiki/Skip_list
写code实现struct skip_list * find(struct skip_list *head, int value)
2，sorted array... 阅读全帖 |
|
S**I
发帖数: 15689 | 6 ☆─────────────────────────────────────☆
gzou (gzou) 于 (Thu May 12 02:26:35 2011, 美东) 提到:
马上就要G on site了，
求祝福。
下面是从本版收集到的Google的试题，便于大家查询。
申明：有的附带有解释说明的，也来自于本版或者网络，大家自己看， 不保证真确
http://www.mitbbs.com/article_t1/JobHunting/31847453_0_1.html
本人ECE fresh PhD，背景是电路/EDA，跟G业务基本没什么关系
同学内部推荐的，很简单的一次电面就给了onsite
题都不难，但是自己没把握好机会，出了一些小bug。
总的感觉，出错就是硬伤，宁可从最简单的算法写起，也不能出错。
电面：
1，Skip list， http://en.wikipedia.org/wiki/Skip_list
写code实现struct skip_list * find(struct skip_list *head, int value)
2，sorted array... 阅读全帖 |
|
a********d
发帖数: 195 | 7 看一个帖子说是suffix和string的逆序的suffix找common ancestor什么的...完全找不
到那个帖子了。两个for好像有点暴力。
题做了过一阵就忘记了...
希望到西雅图有个好状态。 |
|
p*****2
发帖数: 21240 | 8 好奇的问问大家。
我刚才翻了一下CLRS，上边没有介绍suffix tree。你们是什么时候学的呢？做
research还是准备面试呢？我看suffix tree的面试题其实也很少。 |
|
c****x
发帖数: 15 | 9 suffix array和suffix tree构造都很麻烦，面试碰到肯定是不用写了。 |
|
d****o
发帖数: 1055 | 10 对每一个famous sequence, 建立一个suffix tree.
然后用该string 去遍历suffix tree
such
sequences
NoSQL
with |
|
j******2
发帖数: 362 | 11 longest common prefix:
这题就只有O(n*m)的解法了吧？n=最短的一个string的长度，m=string个数。
没更简便的了吧？
longest common substring:
这题的两种解法都要掌握吗？DP比较容易，但是时间复杂度要O(n1xn2)。suffix tree
时间复杂度是O(n1+n2)，但是貌似很复杂，很想放弃了。有经验的大牛们，这题需要掌
握suffix算法吗？ |
|
g**e
发帖数: 6127 | 12 哈，让二爷见笑了，上个礼拜interview event搞的太多，有些东西不吐不快，能帮助
到一些同胞最好，不然看看也就算了。
也不全是说辞。有哥们上来就写代码，几次让面试官打断让他先解释思路。有哥们设计
个题目，把各种option吹了半天，面试官问他那你到底选哪种，支支吾吾就是不选一个
。还有个哥们写最长回文，上来就说DP O(n^2)，结果写了个O(n^3)，还吹可以用
suffix tree，结果连banana的suffix tree都写不出来。
得，
上做 |
|
h*******e
发帖数: 1377 | 13 longest palindrome substring suffix tree有O(n)的200多行不會考 coding的。。不
過如果說考個suffix tree原理怎麼回事倒是有可能。。 |
|
C***U
发帖数: 2406 | 14 我不是很明白你的3)
这个例子怎么跑的？
cacacb |
|
f*****e
发帖数: 2992 | 15 3)就是caca < cacb，也就是strcmp('caca','cacb')<0，这种比较排除了第2种情况，
就是c之后没有比‘c'大的。所以p1一开始指第一个c，变成指第2个c。然后就结束了。 |
|
|
C***U
发帖数: 2406 | 17 恩。我想了一个O(n)的，但是比你的复杂很多，空间也是O(n)的。关键是我觉得如果面
试的时候，现场不好写。你帮我看下对不对。
1） 找到字符串里面所有最大字母的位置，并且全部记录下来。
2） 然后看这些最大字符的后一位，还是找到最大的，并且把这些第二位也最大的记录
下来，然后给他们标记0，假设有k个标记0。把所有剩下的都标记为k，并且还记录这些
剩下的已经比较到哪个位置。这里第二位只过了2边。
3） 继续第二步，一直到找到一个唯一的最大字符串，或者有两个或以上的字符串遇到
下一个最大字符，那么就调用第二步记录的信息，看后一个最大字符串排名第几，如果
有一个唯一的排名最低，那么那个就是第一。如果不是唯一的，那么从第二步那里记录
的地方开始比较。
这样最后会结束比较，而且每个字符串只被比较了常数次。应该是4次吧。 |
|
C***U
发帖数: 2406 | 18 我觉得你可能还是考虑的简单了
漏掉了一些情况
大s |
|
f*****e
发帖数: 2992 | 19 其实可以证明的，不过太过烦琐。而且我也考虑了p1与p2之间出现多次最大字符的情况。 |
|
C***U
发帖数: 2406 | 20 我的方法肯定不好。。。
因为我觉得面试根本不可能写出来
所以不知道版上有没有大牛有简单方法
况。 |
|
l**h
发帖数: 893 | 21 假设是substring的话，建立一个suffix tree?
感觉题目特别强调原始String很大，估计建立suffix tree memory消耗很大吧 |
|
l**h
发帖数: 893 | 22 假设是substring的话，建立一个suffix tree?
感觉题目特别强调原始String很大，估计建立suffix tree memory消耗很大吧 |
|
r**********g
发帖数: 22734 | 23 trie 的话只能从头搜。想fancy一点，prefix, suffix, infix都搜的话用suffix tree
想再fancy点，模糊匹配的话用inverted document |
|
h*******e
发帖数: 1377 | 24 suffix tree大概多少行啊，从来没写过。 suffix array有大约25行如果背还好背点
。 |
|
e***s
发帖数: 799 | 25 这题他是要随意一个分法，还是有要求（分出最少的词 或 分出最多的词）
下面是一个递归写法，DFS找到第一个分法
public static String segmentStringRecursive(String s, Set dict){
if(dict.contains(s)) return s;
int len = s.length();
for(int i = 1; i < len; i++)
{
String prefix = s.substring(0, i);
if(dict.contains(prefix))
{
String suffix = s.substring(i);
String segSuffix = segmentStringRecursive(suffix, dict);
if(segSuffix != nul... 阅读全帖 |
|
d**e
发帖数: 6098 | 26 ☆─────────────────────────────────────☆
gate (态度+做题) 于 (Sun Sep 30 23:00:35 2012, 美东) 提到:
希望对找工作的同胞有用。不过我以后的面试题可是会换了，哈。
【 以下文字转载自 Topcoders 俱乐部 】
发信人: gate (态度+做题), 信区: Topcoders
标 题: Re: G Interview Workshop
发信站: BBS 未名空间站 (Sat Sep 29 21:13:43 2012, 美东)
先说amzn的录取比例。我看了一下过去一年的，SDE 1，2，3从简历到最后接受offer的
比例是3-4%。 onsite -> offer比例30%， 最后有大概60%的人接受。SDE1接受offer的
比例明显高。SDE3接受比例最低，估计牛人都去google了。
再说面试，就我们大组(>200人)来看，面试的题目实在是简单。电面一般是2 sum，
find 2 min number in array这种口水题。我偷的zhangbz的数组去重的题电面了十几
个人只有两... 阅读全帖 |
|
C*********r
发帖数: 21 | 27 1. for each string sort suffix, klnk * n, k is string size, n is number of
strings
2. merge sort suffix from step 1
correct? |
|
r*********n
发帖数: 4553 | 28 3. 构造suffix tree, 然后找出最长回文子串 O(n) 这种解法暂时不熟悉
是不是用suffix tree找字符串和反字符串的longest common substring？ |
|
j*********6
发帖数: 407 | 29 我是用DFS，和memorized 再加上 二爷指导的 pruning, 代码如下 不够感觉写得有些
麻烦 有什么问题请大家慷慨指出
顺便求教这种问题怎么分析时间复杂度
public class Solution {
public ArrayList wordBreak(String s, Set dict) {
// Note: The Solution object is instantiated only once and is reused
by each test case.
// 1. get the min and max length of words in dictionary, used for
pruning.
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
for(String str : dict){
min = Math.min(min, str... 阅读全帖 |
|
A*********c
发帖数: 430 | 30 不能直接回到0.
cnd ← T[cnd]的含义是，找到当前“匹配失败的模式串”的最长的一个proper suffix
, 然后再次尝试匹配。
T这个T vector相当于建了一个Nondeterministic finite automata，直接回到zero的
话，相当于直接回到状态0，
中间的有用的suffix信息都没有用到。
整个过程不停地回溯，到0的时候意味尝试部分匹配彻底失败了，只能从头开始。 |
|
s********x
发帖数: 914 | 31 public ArrayList wordBreak(String s, Set dict) {
Map> memorized = new HashMap
ArrayList>();
return breakIntoWordList(s, dict, memorized);
}
private ArrayList breakIntoWordList(String s, Set dict,
Map> memorized) {
ArrayList result = new ArrayList();
if (s == null || s.length() == 0) {
return result;
}
... 阅读全帖 |
|
h*******e
发帖数: 1377 | 32 里面的 suffix tree suffix array很常见吧，很多大牛可以手写。 |
|
x*******9
发帖数: 138 | 33 suffix array的初始化就是O(logn * n * n)的吧（类似于字符串的快排）
suffix tree木用过，大概差不多，应该到不了O(N) |
|
a**********0
发帖数: 422 | 34 For two strings A and B, we define the similarity of the strings to be the
length of the longest prefix common to both strings. For example, the
similarity of strings "abc" and "abd" is 2, while the
similarity of strings "aaa" and "aaab" is 3.
Calculate the sum of similarities of a string S with each of it's
suffixes.
Input:
The first line contains the number of test cases T. Each of the next T lines
contains a string each.
Output:
Output T lines containing the an... 阅读全帖 |
|
c*****e
发帖数: 3226 | 35 你只要了解 suffix tree 的基本原理以及怎么运用，谁还自己写一个Ukkonen suffix
tree ?你估计都不明白，装NB, stack over flow 上对这个的描述是好几大段 |
|
N**********d
发帖数: 9292 | 36 试过，错误是：
Street Address - The address must be format [Street Number][Suffix][Blank][
Direction][Blank][Street Name] where Suffix and Direction are optional.
Examples: 825 Edwards St., 825B Edwards St., 825B NW Edwards St. |
|
d*****3
发帖数: 65 | 37 请问这个要填啥，不勾这项的话不给certify, 万分感谢
Please note: If you do not fully complete this form or fail to submit the
required documents listed in the instructions, a final decision on your
petition may be delayed or the petition may be denied.
I declare that I prepared this petition at the request of the above
person and it is based on all information of which I have knowledge.
Attorney or Representative: In the event of a Request for Evidence (RFE)
may the USCIS contact you by Fax or E-mail?
... 阅读全帖 |
|
p***y
发帖数: 18037 | 38 一点关系都没有。不过实在太好笑了。。。。忍不住要来转载一下。。。。
To the citizens of the United States of America from Her Sovereign Majesty Queen Elizabeth II
In light of your failure in recent years to nominate competent candidates for President of the USA and thus to govern yourselves, we
hereby give notice of the revocation of your independence, effective
immediately.
(You should look up 'revocation' in the Oxford English Dictionary.)
Her Sovereign Majesty Queen Elizabeth II will resume monarchical duties
over all states, ... 阅读全帖 |
|
l****n
发帖数: 6896 | 39 【 以下文字转载自 Taiwan 讨论区 】
发信人: patsy (patsy), 信区: Taiwan
标 题: 这个和台湾版
发信站: BBS 未名空间站 (Tue Nov 15 23:27:04 2011, 美东)
一点关系都没有。不过实在太好笑了。。。。忍不住要来转载一下。。。。
To the citizens of the United States of America from Her Sovereign Majesty Queen Elizabeth II
In light of your failure in recent years to nominate competent candidates for President of the USA and thus to govern yourselves, we
hereby give notice of the revocation of your independence, effective
immediately.
(You should look up 'revocation' in the Oxfo... 阅读全帖 |
|
M****e
发帖数: 2803 | 40 是suffix的促销，在哪里买的suffix都应该可以用，你可以去你那里的dick's看看。 |
|
s*******i
发帖数: 12823 | 41 编织线版上有人推荐过suffix 832，一直没申请到funding买来试试看~
对suffix唯一的印象就是它家mono看着很爽，线盘的整整齐齐，比berkeley的入眼多了 |
|
r**u
发帖数: 1567 | 42 Suffix 832 or PowerPro Super8 Slick
Suffix 832 is stronger.
Super8 Slick casts more smooth and further. And it is very strong too.
Highly
recommend it. |
|
wh
发帖数: 141625 | 43 【 以下文字转载自 Taiwan 讨论区 】
发信人: patsy (patsy), 信区: Taiwan
标 题: 这个和台湾版
发信站: BBS 未名空间站 (Tue Nov 15 23:27:04 2011, 美东)
一点关系都没有。不过实在太好笑了。。。。忍不住要来转载一下。。。。
To the citizens of the United States of America from Her Sovereign Majesty Queen Elizabeth II
In light of your failure in recent years to nominate competent candidates for President of the USA and thus to govern yourselves, we
hereby give notice of the revocation of your independence, effective
immediately.
(You should look up 'revocation' in the Oxfo... 阅读全帖 |
|
b*s
发帖数: 82482 | 44 参见一个homage单词的OED词条：
homage, n.
View as:
Outline |
Full entry
Quotations:
Show all |
Hide all
Pronunciation: Brit. /hmd/ , U.S. /(h)ɑmd/ (also, chiefly in sense 3b)
Brit. /mɑ/ , U.S. /omɑ/
Forms: ME homoge, ME omage, ME umage, ME ummage, ME–15 hommage, ME–
homage; Sc. pre-17 homadge, pre-17 homag, pre-17 homege, pre-17 omage, pre-
17 ymage (perhaps transmission error), pre-17 17– homage. (Show Less)
Etymology: < Anglo-Norman homaige, humage, Anglo-Norman and Old French
omage, A... 阅读全帖 |
|
b*s
发帖数: 82482 | 45 看了一下，有点剧透。
不过，这个贴应该还行：
Nihon, Nippon, and Japan are all ultimately the same word. In the early part
of the Chinese Tang dynastyin A.D. 670, to be preciseJapanese scholars who
had studied Chinese created a new name for their country using the Chinese
phrase for 'origin of the sun, sunrise,' because Japan is located east of
China. In the Chinese of the time (called Middle Chinese), the phrase was
nzyet-pwun. To this the scholars added the Chinese suffix -kwuk, 'country,'
yielding a compound nz... 阅读全帖 |
|
x****o
发帖数: 21566 | 46 【 以下文字转载自 Linux 讨论区 】
发信人: wjk302 (akui), 信区: Linux
标 题: 大家能帮我看一下下面的问题吗，不胜感激。
发信站: BBS 未名空间站 (Wed Feb 1 22:05:13 2012, 美东)
很冒昧的打扰大家。大家能帮我看一下下面的问题吗，不胜感激。
问题是这样的，在生产环境下
1、Suse的Linux有 /nfsmnt/work_pub/web 文件夹和 /nfsmnt/work_inwork/web
文件夹 ，它们都是NFS文件挂载
2、机器上有多个进程会读写/nfsmnt/work_pub/web 文件夹的内容
3、cron会周期性的 删除/nfsmnt/work_pub/web 文件夹下所有文件，并把/nfsmnt/
work_inwork/web 文件夹下的所有内容拷贝到前面那个文件夹中
这样，完全删除/nfsmnt/work_pub/web 文件夹下所有文件的时候就会有.nfs文件删除
不掉（上面的流程因为某些问题不方便改动）。
想咨询的问题是：我现在能不能修改一下fs/nfs/dir.c ... 阅读全帖 |
|
H********g
发帖数: 43926 | 47 看这里：
http://docs.citationstyles.org/en/stable/primer.html
解释怎么写zotero的CSL。需要看的是Anatomy of an Independent Style部分。
其中这段似乎就是说在正文里的格式：
这是（author1,2014; author2,2015）
要改成 author1(2014),author2(2015)
把prefix改成空格“ ”，delimiter改成"),"
再把group delimiter 改成左括号
应该就差不多了。 |
|
G******U
发帖数: 4211 | 48 美国比较常用的英文名字由最多四部分组成。它们分别是姓（Last Name），名（First
Name），中间的名字（Middle Name），后缀（Suffix）。比如说 John Larry Smith
Jr。
中。John是First Name, Larry 是 middle name, Smith 是 last name, Jr 是 suffix
.
中间的名字往往只写，只用首字母。比如说上边的例子往往写成 John L Smith Jr。他
的父亲必然也叫John Smith。否则他的名字就没有必要加后缀了。
值得注意的是名字当中逗号的用法。姓写在前边的时候，姓后边一定用逗号。有时甚至
后缀写在姓的后边，逗号的前边。Smith, John L Jr 和Smith Jr, John L 和 Smith,
John Larry Jr. 都是正式的写法。如果写成 John, Smith 那么这个人一定是姓约翰名
字叫 Smith.
比如说同胞张老三。护照上和签证上的是拼音 ZHANG LAO SAN。 注意LAO 和SAN之间在
护照和签证页上是有空格的。张老三在美国使用名字要注意什 |
|
w********2
发帖数: 16371 | 49 Back in late February, we noted that Apple had begun selling Brazilian-
assembled 8 GB iPhone 4 models in that country, yielding the first fruits
from Foxconn's production lines starting up in the country. Foxconn has also
been said to be gearing up for iPad production in Brazil, with domestic
production of the iPhone and iPad providing a means by which Apple could
avoid hefty import taxes in one of the world's most populous countries.
While Apple has yet to begin selling Brazilian-assembled ver... 阅读全帖 |
|
c******g
发帖数: 4889 | 50 这才是正确的发音。
The -ium suffix conformed to the precedent set in other newly discovered
elements of the time: potassium, sodium, magnesium, calcium, and strontium (
all of which Davy isolated himself). Nevertheless, -um spellings for
elements were not unknown at the time, as for example platinum, known to
Europeans since the 16th century, molybdenum, discovered in 1778, and
tantalum, discovered in 1802. The -um suffix is consistent with the
universal spelling alumina for the oxide (as opposed to alum... 阅读全帖 |
|
