n*****s
发帖数: 6495 | 1
说laoselang当年翻墙发贴算日杂吗？
说laoselang列举的福特车上配置都不对算日杂吗？
说laoselang自己给的数据要么前后矛盾，要么来源不明，举证的贴一个字都没提到丰
田，算日杂吗？ |
|
|
w******1
发帖数: 520 | 3 字符串A : 1011
字符串B: 111101010110101010001011
要求在B找到A 的 最佳算法， 求出 A 在B 中出现的第一次的位置
和总共出现的次数。 |
|
B*****t
发帖数: 335 | 4 Robin-Carp
KMP
Sunday
BM
... |
|
w******1
发帖数: 520 | 5 The Rabin-Karp Algorithm
The Knuth-Morris-Pratt Algorithm
The Boyer-Moore Algorithm |
|
u**s
发帖数: 50 | 6 Simple application of suffix tree. |
|
B*****t
发帖数: 335 | 7 1. 删除重复字串.
2. 建立一个DAG，比如, 如果两个单词有prefix的关系的话，建立一条有向边。
3. 统计入度为0的节点。
建图的时候可以先sort一下，worst case复杂度O(n^2) |
|
A*********r
发帖数: 564 | 8 我觉得我们对题目的理解不一样。。
给一个简单的例子：s0="AB", s1="XY"
按照原题的意思，一共有6种可能性
AXBY
AXYB
ABXY
XABY
XAYB
XYAB
用DP的话， 取F(i,j)表示以第一个字符串中前i个字符和第二个字符串中前j个字符的字串的可能性， F(1,j)=j+1, F(i,1)=i+1;
F(i,j)=F(i-1,j)+(F(i,j-1).
算法复杂度，应该是Ｏ（ｍ＊ｎ）因为对每个ｉ，ｊ都要算一次。
这个正好跟Ｃ（ｍ＋ｎ，ｉ）＝Ｃ（ｍ＋ｎ－１，ｉ－１）＋Ｃ（ｍ＋ｎ－１，ｉ）的
递归公式一致。 |
|
h********e
发帖数: 1972 | 9 啊。。我没认真看题目。。应该是二分。。不是那种一个字串砍k段，让求最大和 |
|
r******d
发帖数: 308 | 10 hush function弄成个字串存起来？ 呵呵 |
|
|
|
|
|
|
g*********s
发帖数: 1782 | 16 发信人: uglyduke (一苇居士), 信区: JobHunting
标 题: 绝对精华，offer＋面经
发信站: BBS 未名空间站 (Wed Mar 30 21:34:37 2011, 美东)
Amazon的offer，95k+15k
基本情况：
国内大学cs本科，杭州小公司SDE工作1年半，L1来了公司美国总部作PM。工作不到2年
离职开始找工作。L1签证到今年2月就过期了，算是黑着身份找的，挺不容易。
google电面。大我10多届的学长打来，问题范围比较广，但内容基础，考察面：
1 基本数据结构，如array和list
2 十六进制的基本题
3 多线程，线程与进程的区别，windows下的多线程编程基础，livelock技术，读写者
4 给了几个数比大小
5 c++的基本知识，多态，vptable，引用，常，构造析构，static的用法等等小东西
6 浏览器里输入URL后发生什么
on site在santa monica
1 behavior+60秒点击最多的问题，coding。
2 coding，实现一个DFS，不过缺一些条件。
3 大规模问题，有点特殊性的字串排序... 阅读全帖 |
|
a**********2
发帖数: 340 | 17 来自主题: JobHunting版 - 请教两个题 两道最近面试题
1. 最长palindrome有linear的算法？
2. 设计个数据结构存储通讯录，让用户能够按姓名的关键字检索，比方说
ababab 6463562178
cdseabaer 3782903907
搜aba 就返回字串是aba的记录 |
|
i*****d
发帖数: 4 | 18 G家电面zurich的职位。没有NDA。
面试我是一话不多的小哥。首先问了问research，让讲讲最后一篇paper的idea。
然后开始编程，只有一题，就是打印出boggle游戏所有的可能的单词。假定有一个字典
可以检测单词是否存在。
解法很简单，递归久就行。问了问复杂度，和如何优化，假定字典可以检测字串是不是
某个单词的前缀。
用google docs写程序挺痛苦的。写完后被发现几个bug逐一修正。
然后换我问问题结束。
然后给Recruiter写了封感谢信，过一会就回我有Feedback了。打电话告诉我要onsite
。真的很有效率，recruiter也
非常nice。
继续加油准备了，攒攒rp。 |
|
s*****n
发帖数: 5488 | 19 这题1337网站上有答案。差不多是这样。我选择的算法先找到第一个窗口，去掉第一个
字符后，到扫描到同样字符补上前，遇到任何其他字串中的字符都把记录的位置右移，
知道被去掉字符被补上，算windows size,去min,记录start end.数据结构我感觉hash+
linkedlist就够了。
character
table |
|
q******8
发帖数: 848 | 20 longest parlindrome这题用反转之后求公共字串的方法是不是复杂度是O（n3）啊？用
访问每个字符，然后两边扩展的方法是不是好点,O(N2)？然后查了查，说是有linear的
算法，但是没看懂。。。大家讨论一下？ |
|
x******2
发帖数: 546 | 21 DP？
S(a,b)表示恰用了A[a]到A[b]中最长所含有的B的长度，且必须满足A[a]=B[1],A[b]为
该最长字串的最后一个字符。
则S(a,b)=min(k=a...b-1){ S(a,k)+1 | A[b]=B[S[a,b-1]+1] }
最后答案应该在所有的S(a,b)对中找出满足S(a,b)=m且b-a+1最小的那个。
这个复杂度是O(N^3)，不知道有没有更好的 |
|
l****p
发帖数: 397 | 22 我当时的回答是：比如选择空格当各个字串之间的分界符，这样必须把字符本来含有的
空格给去掉，比如用“\b”之类。然后面试官又追问，那么“\”怎么办，我说用两个“\”
代替 |
|
a*****n
发帖数: 158 | 23 我试着回答一下，这里大牛一堆，希望不对的地方大家指点。
１。一般来说用HASHMAP，除非你的HASH FUNCTION PERFECT， 否则有大量的空间实际
上浪费，记得有本书算过JAVA HASHMAP存字串，大概有一半的地方没有数据。。
２。排序的数组有多少不就放多少，当然不浪费。如果溢出可能要整体复制。
３。你说的对，但是他要STORAGE EFFICIENT啊。。还有重要的一点是他需要特别功能
就是显示所有前缀名字的电话号码，这个HASHMAP根本不可能实现。。。
４。这个我同意。 |
|
s******n
发帖数: 3946 | 24 构造prefix tree，然后再匹配每个字串，匹配的过程用到DP（保存中间结果） |
|
k***t
发帖数: 276 | 25 题目其实很简单，自己摆乌龙了。细节如下。
虽然连on-site都没拿到，个人感觉，作为第一次电面，基本达到操练面试的目的。自
我介绍，项目表达要言简意赅。Coding要冷静，不紧张，确保看清题目，自我检查code
要细。
与大家分享面经/经历。也希望大家给comment。Code是我从collabedit上直接贴过来的
。欢迎comment，帮我提高。谢谢。
一电面：老美。
前半部分是简历上Performance Tuning的各种Projects的细节；
后半部分是Website Performance的各种问题。
基本对答如流，获面试人认同。并说我们网站增长快，急需你这样有Performance方面
经验的人。Highly recommend for the next step.
二电面：老印。题目其实很简单，自己摆乌龙了。
开始讲Projects，老印问了一个简历上Resource Leakage Finding的东西。
回答不够简洁清晰，偏冗长。老印试图澄清，最后彻底澄清。花了一些时间。
后半个小时，两道Coding题：
1。判断string是否数字？如1.2。并写TestCa... 阅读全帖 |
|
c***p
发帖数: 221 | 26 我觉得就是字符串的匹配问题吧。 用u匹配s的每个等长字串，看看有多少个字符不同
。考虑到u的开始和结束的特殊情况，可以在u的前后加上足够的pad.
#include
#include
using namespace std;
const char PAD = '$';
int match(string p, string q, size_t len)
{
int count = 0;
for(size_t i = 0; i < len; i++){
if (p.at(i) != q.at(i)){
count++;
}
}
return count;
}
size_t edit (string from, string to, string& sub)
{
string pad;
pad.append( to.length()-1, PAD)... 阅读全帖 |
|
c***p
发帖数: 221 | 27 我觉得就是字符串的匹配问题吧。 用u匹配s的每个等长字串，看看有多少个字符不同
。考虑到u的开始和结束的特殊情况，可以在u的前后加上足够的pad.
#include
#include
using namespace std;
const char PAD = '$';
int match(string p, string q, size_t len)
{
int count = 0;
for(size_t i = 0; i < len; i++){
if (p.at(i) != q.at(i)){
count++;
}
}
return count;
}
size_t edit (string from, string to, string& sub)
{
string pad;
pad.append( to.length()-1, PAD)... 阅读全帖 |
|
o******y
发帖数: 446 | 28 来自主题: JobHunting版 - 今天上一题 (1) 先弄出 x=|A| （A个数）, y=|B|， 扫描一圈即可
（2）取 L=min(x,y),不妨假设为L=x
(3) 找连续L长有A最多的字串，假设含有m个A, 扫描一圈即可
（4）L-m就是结果 |
|
t*********7
发帖数: 255 | 29 就是找最大公共字串吧...反正不论加减修改都算一次... |
|
l*******s
发帖数: 1258 | 30 请google： edit distance
这个是DP的经典问题，思路挺NB的，非常具有扩展性。相关算法在NLP领域用的很多。
基本思路就是用两个字符串构建一个matrix，每个cell代表对应的两个字串的edit
distance。
自己定义insert、delete、alternate的cost，然后比较每个cell周围三个cell的值，
确定当前值，然后就ok了 |
|
m***g
发帖数: 90 | 31 请问可以用hashmap把字典的字母和出现次数存起来，然后在字串里面一个个mapping吗 |
|
P***t
发帖数: 1006 | 32 可以把两个字符串拆成四段来看。假如原字符串是：A B C D
中间交换 B C，应该得到：A C B D
(每次个大写字母代表一段字符，A D 可以是空).
用一个二维数组 X[i][j] 记录 S1从ｉ开始，S2从ｊ开始的相同字符的最大长度。譬如：
S1＝abcd
S2=cdab
then
X[0][0]=0
X[0][1]=0
X[0][2]=2 (ab -> ab)
X[0][2]=0
...
同时记录两头最大相同字串的长度。譬如：
S1=abxyz
S2=abyxz
那么 A 最大长度是2, D 最大长度是１.
Now,
for i = 1 to Length-1 // i is start of segment C in S1
for j = 0 to CommonPrefixLength // j is start of segment of C in S2 (
length of A)
for LenC = X[i][j] to 1 // LenC as the length of segment C
&& (i+LenC >= Leng... 阅读全帖 |
|
P***t
发帖数: 1006 | 33 可以把两个字符串拆成四段来看。假如原字符串是：A B C D
中间交换 B C，应该得到：A C B D
(每次个大写字母代表一段字符，A D 可以是空).
用一个二维数组 X[i][j] 记录 S1从ｉ开始，S2从ｊ开始的相同字符的最大长度。譬如：
S1＝abcd
S2=cdab
then
X[0][0]=0
X[0][1]=0
X[0][2]=2 (ab -> ab)
X[0][2]=0
...
同时记录两头最大相同字串的长度。譬如：
S1=abxyz
S2=abyxz
那么 A 最大长度是2, D 最大长度是１.
Now,
for i = 1 to Length-1 // i is start of segment C in S1
for j = 0 to CommonPrefixLength // j is start of segment of C in S2 (
length of A)
for LenC = X[i][j] to 1 // LenC as the length of segment C
&& (i+LenC >= Leng... 阅读全帖 |
|
p*****2
发帖数: 21240 | 34 做了recursion的，道理不难。想研究一下bottom up的解法。
http://www.mitbbs.com/article_t/JobHunting/32132145.html
可以把两个字符串拆成四段来看。假如原字符串是：A B C D
中间交换 B C，应该得到：A C B D
(每次个大写字母代表一段字符，A D 可以是空).
用一个二维数组 X[i][j] 记录 S1从ｉ开始，S2从ｊ开始的相同字符的最大长度。譬如：
S1＝abcd
S2=cdab
then
X[0][0]=0
X[0][1]=0
X[0][2]=2 (ab -> ab)
X[0][2]=0
...
同时记录两头最大相同字串的长度。譬如：
S1=abxyz
S2=abyxz
那么 A 最大长度是2, D 最大长度是１.
Now,
for i = 1 to Length-1 // i is start of segment C in S1
for j = 0 to CommonPrefixLength // j is start of segment of C in S2 (
length o... 阅读全帖 |
|
M**********7
发帖数: 378 | 35 之前两轮电面
一题是给两个字符串,其中一个作为排序依据,排另外一个字串.
比如
mitbbs, bt
结果
bbtmis
可以假设第二个里面无重复字符,不出现的字符任意放在最后面可以.
另外的电面题再回想中,应该不难.... |
|
q***y
发帖数: 236 | 36 空间可以优化到O(1)。只需记录前两位的个数就可以了。我觉得对全1,2字串，就是斐
波那契数。 |
|
R********y
发帖数: 88 | 37 pair up, // 和 \n 一组
/* 和 */ 一组
用string.indexOf method，如果先出现//，从此处开始找\n，中间跳过。
如果先出现/*，从此处开始找*/，中间跳过。
跳过后继续找，直到字串结束 |
|
K*********n
发帖数: 2852 | 38 周二onsite，office组SDET。面试当天早上才知道是哪个组。今天给消息有offer，明
天打电话谈待遇。
我已经签了Concur Technologies，这个就不能要了。不过因为在Concur是做machine l
earning的，在office组SDET，这些知识就都用不着了，所以之前就想好了会从了Concu
r的。
一共五个人面试。
第一个是东欧人，问behavior quesions，长达半小时。然后给一个平时喝水的纸杯，说
你打算怎么测试这个产品，又是半小时。
第二个老印男，principle SDET，人很友好，问怎么测试vending maching。test的问题
我之前完全没准备过，所以纸杯测试答得不好，但是东欧人一直给指方向，所以到了ve
nding machine我就知道他们要听什么了，这个答得我觉得很好。然后在电脑上给了一个
新建Access Web App的对话框，问怎么测试。大约就是，输入是否合法，文件名可能出
现怎么样的问题之类的。
然后和老印男吃饭。谈我过去的project，谈西雅图的天气。人很友好，就是老发问，吃
不好饭……
饭后第三个人，... 阅读全帖 |
|
K*********n
发帖数: 2852 | 39 周二onsite，office组SDET。面试当天早上才知道是哪个组。今天给消息有offer，明
天打电话谈待遇。
我已经签了Concur Technologies，这个就不能要了。不过因为在Concur是做machine l
earning的，在office组SDET，这些知识就都用不着了，所以之前就想好了会从了Concu
r的。
一共五个人面试。
第一个是东欧人，问behavior quesions，长达半小时。然后给一个平时喝水的纸杯，说
你打算怎么测试这个产品，又是半小时。
第二个老印男，principle SDET，人很友好，问怎么测试vending maching。test的问题
我之前完全没准备过，所以纸杯测试答得不好，但是东欧人一直给指方向，所以到了ve
nding machine我就知道他们要听什么了，这个答得我觉得很好。然后在电脑上给了一个
新建Access Web App的对话框，问怎么测试。大约就是，输入是否合法，文件名可能出
现怎么样的问题之类的。
然后和老印男吃饭。谈我过去的project，谈西雅图的天气。人很友好，就是老发问，吃
不好饭……
饭后第三个人，... 阅读全帖 |
|
s********i
发帖数: 74 | 40 我觉得regular expression肯定不行。首先需要额外空间，否则就要改原字串；其次时
间没优势，Regular expression本身就要一个O(n)。 |
|
f*****e
发帖数: 2992 | 41 用一个或多个hash函数把长为m的string去掉一个字符然后(s,i)hash到buckets里。有
点bloom filter的思想。然后对落到同一个bucket里的string进行比较。
s是去掉第i个字符得到的字串。 |
|
G********r
发帖数: 9 | 42 比较久之前T家的面试,结果就不共享了,只贡献题目，可能给面Machine Learning方向
的有些帮助。
电面1.
（1）一些统计的问题，二项分布，大数定理，抛硬币做概率转换
(2) （写程序）用stack实现queue
电面2.
（1） Trending tweats的算法设计；tweat topic的提取；
（2）（写程序）输入一个程序源文件，写一个程序去掉所以有的comment
Onsite:
(1). （a）(写程序)两个字符串的最大公共字串
（b （puzzle）game: the interviewee is an oracle of a function "bool f(
int, int, int)", that is, the interviewer can provide three numbers as input
, then the interviewee can give the TRUE/FALSE answer. Play the game and
find the precise definition for the function.
... 阅读全帖 |
|
c********t
发帖数: 5706 | 43 赞！多谢分享！
Onsite:
(1). （a）(写程序)两个字符串的最大公共字串
需要优化的算法吗？还是brute force就可以？
（b （puzzle）game: the interviewee is an oracle of a function "bool f(
int, int, int)", that is, the interviewer can provide three numbers as input
, then the interviewee can give the TRUE/FALSE answer. Play the game and
find the precise definition for the function.
不会做啊，试很多很多triple,然后找规律？
(b)(写程序)爬楼梯的题，valid single-step move is 2^k (always starting
from the first floor). Given a target floor n, output the best strategy to
r... 阅读全帖 |
|
c********t
发帖数: 5706 | 44 DP可以做(写程序)两个字符串的最大公共字串。我觉得比写suffix tree容易些。 |
|
e****9
发帖数: 316 | 45 有n个很长的字符串，比如
abcd....
bacd....
cabd....
........
有没有一个hash算法，使第一个字串的生成的hash值小于第二个，第二个hash值小于第
三个？
就是hash之后，不改变原来的排序。 |
|
|
f*****e
发帖数: 2992 | 47 考古“海量贴”，存成以头两个字母为名字的文件"ab.txt","bc.txt"然后用trie
对每个文件进行排序。
问题 |
|
p*****2
发帖数: 21240 | 48
貌似LZ对速度有要求，而且字符串可能会变动的 |
|
s***u
发帖数: 101 | 49 找工作以来在这个版上获益良多，现在找工作告一段落，打算写个经历总结，算是回馈
本版，希望能对后来人有一点帮助。
背景：
本人 CS fresh PhD , 本科及硕士在国内学的是自动化，算法与编程的基础比较薄弱。
记得我来美国第一年，才见到算法导论这本书，当时惊为天书。。惊叹原来学计算机的
人是这么思考问题的，一个sorting 问题被玩出那么多花样！可见当时的孤陋寡闻。。
。 PhD的研究很偏，属于拓扑图论相关的，十分理论，所以我在整个PhD过程中，主要
写的代码来自课程项目。。
去年8月份的时候，被老板告知可以滚蛋了，因为研究的项目暂时没有看到太多的研究
前景，遂决定投身码工。。
准备与面试：
9月份正式开始准备找码工工作，经朋友介绍先看的是PIE 和 CC 150. 当时CC150的题
目，觉得挺难，而且每次看到答案解法十分优美，简短，勾起了我很大的兴趣。。.
150 前几大章看完一遍以后，当时自我感觉非常的良好，觉得算法考试也就那样嘛。正
巧，MS来校园招聘，就投了简历。M说要过一个月才能回来校园面试，这段时间我开始
做leetcode。 话说leetcode还是我们实验室的... 阅读全帖 |
|
a***o
发帖数: 1182 | 50 con!
那个很多interval找最多那个怎么做的？
找工作以来在这个版上获益良多，现在找工作告一段落，打算写个经历总结，算是回馈
本版，希望能对后来人有一点帮助。
背景：
本人 CS fresh PhD , 本科及硕士在国内学的是自动化，算法与编程的基础比较薄弱。
记得我来美国第一年，才见到算法导论这本书，当时惊为天书。。惊叹原来学计算机的
人是这么思考问题的，一个sorting 问题被玩出那么多花样！可见当时的孤陋寡闻。。
。 PhD的研究很偏，属于拓扑图论相关的，十分理论，所以我在整个PhD过程中，主要
写的代码来自课程项目。。
去年8月份的时候，被老板告知可以滚蛋了，因为研究的项目暂时没有看到太多的研究
前景，遂决定投身码工。。
准备与面试：
9月份正式开始准备找码工工作，经朋友介绍先看的是PIE 和 CC 150. 当时CC150的题
目，觉得挺难，而且每次看到答案解法十分优美，简短，勾起了我很大的兴趣。。.
150 前几大章看完一遍以后，当时自我感觉非常的良好，觉得算法考试也就那样嘛。正
巧，MS来校园招聘，就投了简历。M说要过一个月才能回来校园面试，这段时间我开始
... 阅读全帖 |
|
