v***a
发帖数: 365 | 1 之前都不知道还有如此方便的网站，
随便在上面做了几道题目，竟然有很不错的公司主动联系我给电面，比 refer 效率高
多了。做5道题目就可以申Facebook, Dropbox 等公司了
下月6号还有个比赛 http://codesprint.interviewstreet.com/recruit/challenges/ |
q****x
发帖数: 7404 | 2 啥公司？
【在 v***a 的大作中提到】
: 之前都不知道还有如此方便的网站，
: 随便在上面做了几道题目，竟然有很不错的公司主动联系我给电面，比 refer 效率高
: 多了。做5道题目就可以申Facebook, Dropbox 等公司了
: 下月6号还有个比赛 http://codesprint.interviewstreet.com/recruit/challenges/
|
v***a
发帖数: 365 | |
p*****2
发帖数: 21240 | |
v***a
发帖数: 365 | 5
对我来说有点难度，等找到工作了，把我的解答都放上来
【在 p*****2 的大作中提到】
:
: 题什么难度呀？
|
A**u
发帖数: 2458 | 6 这个能不能看到solution
topcoder竟然只能键盘敲，不能复制过去，也复制不出来代码 |
q****x
发帖数: 7404 | 7 比topcoder如何？
【在 v***a 的大作中提到】
:
: 对我来说有点难度，等找到工作了，把我的解答都放上来
|
v***a
发帖数: 365 | 8
当然可以复制了，否则没法 debug 了
【在 A**u 的大作中提到】
: 这个能不能看到solution
: topcoder竟然只能键盘敲，不能复制过去，也复制不出来代码
|
v***a
发帖数: 365 | 9
比TC难不少，但是challenge没有做题时间限制，可以多些时间思考
【在 q****x 的大作中提到】
: 比topcoder如何？
|
p*****2
发帖数: 21240 | 10
有点太难了。我试着做了两道分低的，但是算法肯定是太naive了，过不了所有的test
cases. time exceeded. 想了半天也想不出好算法来。会不会要用到数学呀？不错的是
支持.net 4.0, TC只是支持2.0。但是，对我来说太难了。不然是个很好的练习平台。
【在 v***a 的大作中提到】
:
: 比TC难不少，但是challenge没有做题时间限制，可以多些时间思考
|
|
|
f*******t
发帖数: 7549 | |
p*****2
发帖数: 21240 | 12
你是大牛，我看到你pass了那两道题。我想了一晚上一道也搞不定呀。需要用到什么知
识呀？我在想是不是我本来就不具备那方面的知识搞得。
【在 f*******t 的大作中提到】
: 非常难，我两天才做出两道25分的题
|
f*******t
发帖数: 7549 | 13 啊，你怎么看到我做什么题的？
String Reduction没什么算法在里面，研究一下规律就能做了。
String Similarity是KMP算法的应用。
还有版上问的50分题，我只能过sample testcases，其它WA
http://www.mitbbs.com/article_t/JobHunting/32011987.html
不知道有没有大牛能讲解一下具体算法。。
【在 p*****2 的大作中提到】
:
: 你是大牛，我看到你pass了那两道题。我想了一晚上一道也搞不定呀。需要用到什么知
: 识呀？我在想是不是我本来就不具备那方面的知识搞得。
|
p*****2
发帖数: 21240 | 14
Activity里边能看到最近的submission, 我做题的时候，正好看到你的submission
succeeded了。我主要是做similarity那题，我看一下KMP算法去。
【在 f*******t 的大作中提到】
: 啊，你怎么看到我做什么题的？
: String Reduction没什么算法在里面，研究一下规律就能做了。
: String Similarity是KMP算法的应用。
: 还有版上问的50分题，我只能过sample testcases，其它WA
: http://www.mitbbs.com/article_t/JobHunting/32011987.html
: 不知道有没有大牛能讲解一下具体算法。。
|
p*****2
发帖数: 21240 | 15
多谢大牛。reduction pass了。
【在 f*******t 的大作中提到】
: 啊，你怎么看到我做什么题的？
: String Reduction没什么算法在里面，研究一下规律就能做了。
: String Similarity是KMP算法的应用。
: 还有版上问的50分题，我只能过sample testcases，其它WA
: http://www.mitbbs.com/article_t/JobHunting/32011987.html
: 不知道有没有大牛能讲解一下具体算法。。
|
n****p
发帖数: 193 | 16 推荐一些面试书籍：
http://haiwaibbs.com/forum.php?mod=viewthread&tid=14182
【在 v***a 的大作中提到】
: 之前都不知道还有如此方便的网站，
: 随便在上面做了几道题目，竟然有很不错的公司主动联系我给电面，比 refer 效率高
: 多了。做5道题目就可以申Facebook, Dropbox 等公司了
: 下月6号还有个比赛 http://codesprint.interviewstreet.com/recruit/challenges/
|
n****n
发帖数: 5804 | |
w***c
发帖数: 8 | |
p*****2
发帖数: 21240 | |
a****a
发帖数: 186 | |
|
|
p*****2
发帖数: 21240 | 21
我用了用KMP好像找不到感觉。后来把我的代码稍微优化了一下，竟然就过了。
【在 f*******t 的大作中提到】
: 啊，你怎么看到我做什么题的？
: String Reduction没什么算法在里面，研究一下规律就能做了。
: String Similarity是KMP算法的应用。
: 还有版上问的50分题，我只能过sample testcases，其它WA
: http://www.mitbbs.com/article_t/JobHunting/32011987.html
: 不知道有没有大牛能讲解一下具体算法。。
|
v********a
发帖数: 14 | |
g****v
发帖数: 971 | |
e*****a
发帖数: 79 | 24 m
【在 p*****2 的大作中提到】
:
: 我用了用KMP好像找不到感觉。后来把我的代码稍微优化了一下，竟然就过了。
|
p*****2
发帖数: 21240 | 25 找到点感觉，pass 5道了，不知道能不能找到工作。LZ拿到offer过来报一下喜呀。 |
R******9
发帖数: 267 | 26 mark
【在 v***a 的大作中提到】
: 之前都不知道还有如此方便的网站，
: 随便在上面做了几道题目，竟然有很不错的公司主动联系我给电面，比 refer 效率高
: 多了。做5道题目就可以申Facebook, Dropbox 等公司了
: 下月6号还有个比赛 http://codesprint.interviewstreet.com/recruit/challenges/
|
p*****2
发帖数: 21240 | |
b*****c
发帖数: 1103 | 28 String Similarity
为啥米KMP会超时呢，不是死循环，我测过100000的，只过了4/10 test case
int test_num;
char str[100024];
int F[100024];
long long ans;
void FailureFunction(char P[], int F[],int m){
int i,j;
F[0]=0; // assignment is important!
j=0;
i=1;
while(i
if(P[i]==P[j]){
F[i]=j+1;
i++;
j++;
}else if(j>0){
j=F[j-1];
}else {
F[i]=0;
i++;
}
}
}
void solve(int m)
{
int i=m;
int life=-1;
while (i--)
{
if (F[i]<0)
{
life=-F[i];
ans-=(long long)F[i];
}
else
{
int j=i;
while (F[j]>0)
{
j=F[j];
if (life-1 == j || F[j]<0)
{
///////
life=abs(F[j]);
///////
ans+=(long long)abs(F[j]);
break;
}
}
}
}
}
void KMP(char P[]){
int m=strlen(P);
FailureFunction(P,F,m);
int i=m;
while (i--)
{
if (m-1 == i)
{
F[i]*=-1;
}
else
{
if (abs(F[i+1]) != F[i]+1)
{
F[i]*=-1;
}
}
}
ans=m;
solve(m);
std::cout<
}
int main()
{
std::cin>>test_num;
std::cin.getline(str,200);
while (test_num--)
{
std::cin.getline(str,100024);
KMP(str);
}
} |
b******t
发帖数: 965 | 29 100000个a的时候？
【在 b*****c 的大作中提到】
: String Similarity
: 为啥米KMP会超时呢，不是死循环，我测过100000的，只过了4/10 test case
: int test_num;
: char str[100024];
: int F[100024];
: long long ans;
: void FailureFunction(char P[], int F[],int m){
: int i,j;
: F[0]=0; // assignment is important!
: j=0;
|
b******t
发帖数: 965 | 30 有谁能讲讲这个题的解答么 我也是用KMP怎么也找不到感觉
关键 KMP会skip outer iteration 但是似乎这里不太能skip
【在 b******t 的大作中提到】
: 100000个a的时候？
|
|
|
d*******l
发帖数: 338 | 31 开始看着像KMP但后来也没想出来怎么弄。直接二分加hash过了。 |
p*****2
发帖数: 21240 | 32
我不懂KMP，也没用KMP。看了下wiki上的KMP，试了试，没什么感觉。最后就是用brute
force。
【在 b******t 的大作中提到】
: 有谁能讲讲这个题的解答么 我也是用KMP怎么也找不到感觉
: 关键 KMP会skip outer iteration 但是似乎这里不太能skip
|
c****p
发帖数: 6474 | 33 kmp的实际性能ms一般
brute
【在 p*****2 的大作中提到】
:
: 我不懂KMP，也没用KMP。看了下wiki上的KMP，试了试，没什么感觉。最后就是用brute
: force。
|
p*****2
发帖数: 21240 | 34
什么公司跟你联系了？怎么还没有一个公司给我电面呀？
【在 v***a 的大作中提到】
: 之前都不知道还有如此方便的网站，
: 随便在上面做了几道题目，竟然有很不错的公司主动联系我给电面，比 refer 效率高
: 多了。做5道题目就可以申Facebook, Dropbox 等公司了
: 下月6号还有个比赛 http://codesprint.interviewstreet.com/recruit/challenges/
|
i******r
发帖数: 793 | 35 感觉这个网站对找工帮助不大
company list里面很多都是startup，不怎么招国际学生
网站不少bug，没发现投简历的地方
练习一下算法还行
【在 v***a 的大作中提到】
: 之前都不知道还有如此方便的网站，
: 随便在上面做了几道题目，竟然有很不错的公司主动联系我给电面，比 refer 效率高
: 多了。做5道题目就可以申Facebook, Dropbox 等公司了
: 下月6号还有个比赛 http://codesprint.interviewstreet.com/recruit/challenges/
|
w*******6
发帖数: 1897 | |
