J******8
发帖数: 132 | 1 The question is not hard. But I missed two key points.
The details below.
==========================================================
/*
example
char *words[] = {"foo", "bar", "baz", NULL};
setup(words);
1) First step:
isMember("foo") -> true
isMember("garply") -> false
2) Second step:
isMember("f.o") -> true
isMember("..") -> false
*/
#include
#include
#include
char *words[] = {"foo", "bar", "baz", "caz","cat",NULL};
int num=0;
void print_words(void)
{
int i=0;
while(words[i]){
printf("%s\n",words[i]);
i++;
}
}
/* arbitrary preprocessing. May be slow */
void setup(char *words[])
{
int i=0,j;
char temp[16];
while(words[i]){
i++;
}
num=i;
printf("num=%d\n",num);
//Brute force sorting
for(i=0;i
for(j=i+1;j
if(strcmp(words[i],words[j])>0){
strcpy(temp,words[i]);
strcpy(words[i],words[j]);
strcpy(words[j],temp);
}
}
}
//Missed: Can't do qsort() lib call here. !!!!
printf("sorted.\n");
}
//Missed: in this case, it does NOT make sense to compare as strcmp
//only matched or not.
int matchdot(const char *s1, const char *s2)
{
if(!s1||!s2)
return 0;
while(*s1&&*s2&&((*s1==*s2)||(*s2=='.'))){
s1++;
s2++;
}
if(*s1||*s2)
return 0;
return 1;
}
/* returns whether word is a member of words given in setup() as fast as
possible */
int isMember(char *word) {
int low=0,high=num-1;
int mid;
while(high>=low){
mid=low+(high-low)/2;
if(!strcmp(words[mid],word))
return 1;
else if(strcmp(words[mid],word)>0)
high=mid-1;
else
low=mid+1;
}
return 0;
}
int isMemberdot(char *word) {
int i=0;
while(words[i]){
if(matchdot(words[i],word))
return 1;
i++;
}
return 0;
}
int main (int argc, char *argv[])
{
char buf[16];
print_words();
setup(words);
print_words();
//1) test cases
strcpy(buf,"cat");
if(isMember(buf))
printf("isMember(%s)=Yes\n",buf);
else
printf("isMember(%s)=No\n",buf);
strcpy(buf,"cot");
if(isMember(buf))
printf("isMember(%s)=Yes\n",buf);
else
printf("isMember(%s)=No\n",buf);
//2) test cases
strcpy(buf,"cat");
if(isMemberdot(buf))
printf("isMemberdot(%s)=Yes\n",buf);
else
printf("isMemberdot(%s)=No\n",buf);
strcpy(buf,"cot");
if(isMemberdot(buf))
printf("isMemberdot(%s)=Yes\n",buf);
else
printf("isMemberdot(%s)=No\n",buf);
strcpy(buf,"c.t");
if(isMemberdot(buf))
printf("isMemberdot(%s)=Yes\n",buf);
else
printf("isMemberdot(%s)=No\n",buf);
strcpy(buf,"..");
if(isMemberdot(buf))
printf("isMemberdot(%s)=Yes\n",buf);
else
printf("isMemberdot(%s)=No\n",buf);
return 0;
}
===================
running results | l*****v
发帖数: 498 | 2 what is the question?
【在 J******8 的大作中提到】
: The question is not hard. But I missed two key points.
: The details below.
: ==========================================================
: /*
: example
: char *words[] = {"foo", "bar", "baz", NULL};
: setup(words);
: 1) First step:
: isMember("foo") -> true
: isMember("garply") -> false
| l*********r
发帖数: 674 | 3 我觉得是写程序实现开头那个example的功能把。
【在 l*****v 的大作中提到】
: what is the question?
| l*****v
发帖数: 498 | 4 这就是带wildcard的string match。没有*应该不难吧。 | l*****v
发帖数: 498 | 5 面你的是不是个中国人
【在 J******8 的大作中提到】
: The question is not hard. But I missed two key points.
: The details below.
: ==========================================================
: /*
: example
: char *words[] = {"foo", "bar", "baz", NULL};
: setup(words);
: 1) First step:
: isMember("foo") -> true
: isMember("garply") -> false
| n******n
发帖数: 215 | 6 问一下，他们用电话问问题阿？
那么多，难道用笔记下来吗？
【在 J******8 的大作中提到】
: The question is not hard. But I missed two key points.
: The details below.
: ==========================================================
: /*
: example
: char *words[] = {"foo", "bar", "baz", NULL};
: setup(words);
: 1) First step:
: isMember("foo") -> true
: isMember("garply") -> false
| L******h
发帖数: 1191 | 7 同问
【在 n******n 的大作中提到】
: 问一下，他们用电话问问题阿？
: 那么多，难道用笔记下来吗？
| J******8
发帖数: 132 | 8 No. A mostly white guy, fresh graduate.
Not friendly: *interrogated* me about
1) why want to leave current company
2) why choose facebook.
A bit bullshit. :-)
http://www.linkedin.com/pub/daniel-peek/7/571/b02
【在 l*****v 的大作中提到】
: 面你的是不是个中国人
| J******8
发帖数: 132 | 9 http://collabedit.com/
【在 n******n 的大作中提到】
: 问一下，他们用电话问问题阿？
: 那么多，难道用笔记下来吗？
| J******8
发帖数: 132 | 10 Not hard at all. But I focused on how to do wildcard matching, missed the
point to do linear lookup in dictionary in that case (binary search not
applicable any more).
【在 l*****v 的大作中提到】
: 这就是带wildcard的string match。没有*应该不难吧。
| j*****u
发帖数: 1133 | 11 did he ask to use additional space to speed up lookup? ( is the source must
be an array)
otherwise the O(n) match is not interesting at all. | J******8
发帖数: 132 | 12 No, But I mentioned the best way is to build a trie, but that's too complex.
So let's do the binary search and/or linear search... He agrees. :-)
Do you have any better solution than trie?
must
【在 j*****u 的大作中提到】
: did he ask to use additional space to speed up lookup? ( is the source must
: be an array)
: otherwise the O(n) match is not interesting at all.
|
|
