[合集] G一面，感觉不咋的# JobHunting - 待字闺中
S*I
1 楼
☆─────────────────────────────────────☆
libei (Bei) 于 (Wed Jan 11 15:43:39 2012, 美东) 提到:
面试官是Google+组的，
一上来她说看到我简历上的一篇测试自动化的文章，读了一遍，感觉"very
informative"，让后让我介绍一下相关经验。让我小高兴了一下。
第一题是coding，做的还算顺利，后来她评价说所有的cases都覆盖到了。可能算是过
关吧。
第二题我想复杂了，然后在她提示下才解决。自我感觉很不好。其实sort一下就差不多
了，不过我往复杂的树结构想去了。虽然树结构确实能解决这个问题，不过当时我解释
得很不清楚。反正很不爽。
最后瞎聊时间，她说我提到的测试自动化实践和Google内部的基本完全一样blahblah。
。。，不过我觉得这点也算不上加分吧，是个人进google一段时间后都能学会。就怕她
觉得我想问题太复杂，直接negative。
大家有啥建议想法？？
☆─────────────────────────────────────☆
peking2 (myfacebook) 于 (Wed Jan 11 16:02:51 2012, 美东) 提到:
SET吗？
☆─────────────────────────────────────☆
quicklogic (兔八哥) 于 (Wed Jan 11 16:04:37 2012, 美东) 提到:
What questions did she ask? Mind sharing?
☆─────────────────────────────────────☆
libei (Bei) 于 (Wed Jan 11 16:05:24 2012, 美东) 提到:
我投的是New Grads，HR告诉我这个职位进去后才分组，
另外她说G里面developer自己也要写很多自动化的测试，特别是Unit level的，SET主要是负责
functional level的。其实现在新一些的公司都这么做。
☆─────────────────────────────────────☆
libei (Bei) 于 (Wed Jan 11 16:07:14 2012, 美东) 提到:
还在面中，
☆─────────────────────────────────────☆
peking2 (myfacebook) 于 (Wed Jan 11 16:08:17 2012, 美东) 提到:
G的电面比较容易过。onsite就比较麻烦。很多人觉得答的很好还是悲剧。摸不清楚他
们onsite主要是看什么。
☆─────────────────────────────────────☆
runPython (凸-.- 我挺郭德刚) 于 (Wed Jan 11 17:41:21 2012, 美东) 提到:
看解题思路吧
☆─────────────────────────────────────☆
peking2 (myfacebook) 于 (Wed Jan 11 18:04:44 2012, 美东) 提到:
我从最naive的算法谈起，一层层到最优解，还是不行。
☆─────────────────────────────────────☆
lolhaha (二零一二，做一个有米的人) 于 (Wed Jan 11 18:15:31 2012, 美东) 提到:
人家一看你就是准备过
所以这不能证明你的实力
你应该直接上次优解
然后在他的提示下逐步得到最优解
☆─────────────────────────────────────☆
fingerdancer (碍眼猫) 于 (Wed Jan 11 18:39:32 2012, 美东) 提到:
这年头不准备不行，准备还是不行，真是不让人活了
☆─────────────────────────────────────☆
quantx (X矿工) 于 (Wed Jan 11 19:14:27 2012, 美东) 提到:
too much personal thinking. just wait.
☆─────────────────────────────────────☆
peking2 (myfacebook) 于 (Wed Jan 11 20:15:26 2012, 美东) 提到:
碰到的题还真都没见过。但是解法跟其他题雷同。有一个直接给了最优解用trie，结果
让我code，麻烦大了，时间不够。后来他说他就是想让我用dictionary。这样代码就没
那么长了。sigh。也不早说。
☆─────────────────────────────────────☆
quantx (X矿工) 于 (Wed Jan 11 20:20:37 2012, 美东) 提到:
dictionary can be implemented by trie, hash table, and binary search tree.
☆─────────────────────────────────────☆
peking2 (myfacebook) 于 (Wed Jan 11 20:27:21 2012, 美东) 提到:
那我概念有问题了。C#里dictionary就是hashtable呀。Java，C++里dictionary是什么
data structure?
☆─────────────────────────────────────☆
libei (Bei) 于 (Wed Jan 11 21:02:36 2012, 美东) 提到:
这里Dictionary一般是说数据结构里面的定义，和具体语言关系不大阿。
另外你看一下IDictionary接口有很多实现，包含Hashtable和Dictionary，各种实现都
算是“Dictionary”
☆─────────────────────────────────────☆
quantx (X矿工) 于 (Wed Jan 11 21:06:01 2012, 美东) 提到:
yes, it's a problem.
☆─────────────────────────────────────☆
peking2 (myfacebook) 于 (Wed Jan 11 21:50:03 2012, 美东) 提到:
但是他也指出来trie比dictionary要更优化呀。
☆─────────────────────────────────────☆
guangyi ( 光一) 于 (Wed Jan 11 21:58:44 2012, 美东) 提到:
我面ms的时候也有题我用了trie,对方后来告诉我期望的是简单的hash,但是我把trie写
出来了,尽管费时比较多但是对方也很满意.
☆─────────────────────────────────────☆
peking2 (myfacebook) 于 (Wed Jan 11 22:16:25 2012, 美东) 提到:
我跟你情况应该是差不多的。但是我trie没写完。我本来也没有写过trie。唉。我刚才
想了想trie确实要优化，这样很多情况就直接return了，如果用hashtable的话就要
brute force了。还是自己太弱，准备的时候以为随便聊聊trie就可以了。结果真写
code就露怯了。
☆─────────────────────────────────────☆
lolhaha (二零一二，做一个有米的人) 于 (Wed Jan 11 22:28:24 2012, 美东) 提到:
Trie就是一个多叉树
比方说26字母/0-9之类
没那么麻烦
你这次自己写写，下次就不会出问题了
☆─────────────────────────────────────☆
peking2 (myfacebook) 于 (Wed Jan 11 22:32:33 2012, 美东) 提到:
嗯。只是读过一个tutorial，应该好好练练。不过Trie加上面试题，写起来也比较麻烦
。像我这基础，练了trie下次不定又栽在什么上边了。
☆─────────────────────────────────────☆
lolhaha (二零一二，做一个有米的人) 于 (Wed Jan 11 22:36:10 2012, 美东) 提到:
常见数据结构
旧那么几种
统统写10遍
☆─────────────────────────────────────☆
peking2 (myfacebook) 于 (Wed Jan 11 22:39:21 2012, 美东) 提到:
red-black要写吗？
☆─────────────────────────────────────☆
lolhaha (二零一二，做一个有米的人) 于 (Wed Jan 11 22:55:23 2012, 美东) 提到:
我从来没写过，基本上认为不会让写这个，
不过，你要有时间，最好全会
☆─────────────────────────────────────☆
quantx (X矿工) 于 (Wed Jan 11 22:57:15 2012, 美东) 提到:
还是有点麻烦。压力下现想现写不易。
☆─────────────────────────────────────☆
Hbase (Hbase) 于 (Thu Jan 12 01:17:37 2012, 美东) 提到:
这个能面试时间写好也是神人了
面试官自己完全没有理由记得那些细节吧
让写这个，我觉得也就只有某国的人想刁难人才会吧，你要让他写肯定不会
☆─────────────────────────────────────☆
appscan (appscan) 于 (Sun Jan 15 23:24:08 2012, 美东) 提到:
我电面AMAZON的时候写了TRIE的实现。。。
☆─────────────────────────────────────☆
quantx (X矿工) 于 (Sun Jan 15 23:25:22 2012, 美东) 提到:
牛。超过20行不好写。
☆─────────────────────────────────────☆
peking2 (myfacebook) 于 (Sun Jan 15 23:29:10 2012, 美东) 提到:
如果准备过应该没问题吧。如果单纯写个trie的话。
☆─────────────────────────────────────☆
quantx (X矿工) 于 (Sun Jan 15 23:29:48 2012, 美东) 提到:
照抄当然简单。
☆─────────────────────────────────────☆
fantasist (fan) 于 (Sun Jan 15 23:55:18 2012, 美东) 提到:
trie很好写的，而且面试时也常考（至少概念要清楚），强烈推荐准备
☆─────────────────────────────────────☆
quantx (X矿工) 于 (Mon Jan 16 00:00:24 2012, 美东) 提到:
给个20行实现看看？
☆─────────────────────────────────────☆
fantasist (fan) 于 (Mon Jan 16 01:55:26 2012, 美东) 提到:
20行的没有，只有80行的。。。
☆─────────────────────────────────────☆
quantx (X矿工) 于 (Mon Jan 16 01:56:33 2012, 美东) 提到:
一个面试写80行？牛逼。
☆─────────────────────────────────────☆
peking2 (myfacebook) 于 (Mon Jan 16 02:00:01 2012, 美东) 提到:
那也share一下吧。
☆─────────────────────────────────────☆
fantasist (fan) 于 (Mon Jan 16 02:32:37 2012, 美东) 提到:
单独的貌似没有，就发完整的boggle game代码吧
#include
#include
#include
#define ENTRYNOTFOUND 0
#define ENTRYFOUND 1
#define NOTCOMPLETE 2
struct Trie;
void FindWords(Trie *root);
struct Trie
{
Trie();
~Trie();
Trie *children[26];
bool isEnd;
};
Trie::Trie()
{
for(int i = 0; i < 26; i++)
children[i] = NULL;
isEnd = false;
}
Trie::~Trie()
{
for(int i = 0; i < 26; i++) {
if(children[i]) {
delete children[i];
children[i] = NULL;
}
}
}
void TrieInsert(Trie *root, const char *str)
{
if(!str || *str < 'a' || *str > 'z') {
printf("Invalid line\n");
return;
}
Trie *cur = root;
while(*str >= 'a' && *str <= 'z') {
int index = (int)(*str - 'a');
if(cur->children[index] == NULL) {
cur->children[index] = new Trie();
}
cur = cur->children[index];
str++;
}
if(cur != root)
cur->isEnd = true;
}
int TrieSearch(Trie *root, const char *str)
{
if(!str || *str < 'a' || *str > 'z') {
printf("Invalid string!\n");
return ENTRYNOTFOUND;
}
printf("Looking for word %s\n", str);
Trie *cur = root;
while(*str >= 'a' && *str <= 'z') {
int index = (int)(*str - 'a');
if(cur->children[index]) {
cur = cur->children[index];
str++;
}
else
return ENTRYNOTFOUND;
}
if(cur != root && cur->isEnd)
return ENTRYFOUND;
else
return NOTCOMPLETE;
}
int main()
{
Trie *root = new Trie();
FILE *fp = fopen("dictionary.txt", "r");
if(!fp) {
printf("Cannot find dictionary file\n");
exit(-1);
}
char buff[32];
int count = 0;
while(fgets(buff, 31, fp) != NULL) {
TrieInsert(root, buff);
memset(buff, 0, 32);
count++;
}
fclose(fp);
printf("Loaded %d words\n", count);
FindWords(root);
delete root;
return 0;
}
#define WIDTH 4
#define HEIGHT 4
bool isValidIndex(int x, int y, bool used[HEIGHT][WIDTH])
{
if(x >= 0 && x < WIDTH && y >= 0 && y < HEIGHT && !used[y][x])
return true;
else
return false;
}
void dfsWord(Trie *root, char *buff, int buffidx, char matrix[HEIGHT][WIDTH]
, bool used[HEIGHT][WIDTH], int x, int y)
{
/*
if(buffidx > 0)
printf("Current buffer: %s\n", buff);
*/
buff[buffidx] = matrix[y][x];
used[y][x] = true;
int status = TrieSearch(root, buff);
if(status != ENTRYNOTFOUND) {
if(status == ENTRYFOUND)
printf("Found word: %s\n", buff);
if(isValidIndex(x-1, y, used))
dfsWord(root, buff, buffidx+1, matrix, used, x-1, y);
if(isValidIndex(x-1, y-1, used))
dfsWord(root, buff, buffidx+1, matrix, used, x-1, y-1);
if(isValidIndex(x, y-1, used))
dfsWord(root, buff, buffidx+1, matrix, used, x, y-1);
if(isValidIndex(x+1, y-1, used))
dfsWord(root, buff, buffidx+1, matrix, used, x+1, y-1);
if(isValidIndex(x+1, y, used))
dfsWord(root, buff, buffidx+1, matrix, used, x+1, y);
if(isValidIndex(x+1, y+1, used))
dfsWord(root, buff, buffidx+1, matrix, used, x+1, y+1);
if(isValidIndex(x, y+1, used))
dfsWord(root, buff, buffidx+1, matrix, used, x, y+1);
if(isValidIndex(x-1, y+1, used))
dfsWord(root, buff, buffidx+1, matrix, used, x-1, y+1);
}
buff[buffidx] = 0;
used[y][x] = false;
}
void FindWords(Trie *root)
{
char matrix[HEIGHT][WIDTH] = {
{'t', 'e', 'g', 's'},
{'r', 'e', 'i', 't'},
{'n', 'i', 'f', 'o'},
{'g', 'l', 'k', 'c'},
};
bool used[HEIGHT][WIDTH];
for(int i = 0; i < HEIGHT; i++) {
for(int j = 0; j < WIDTH; j++) {
used[i][j] = false;
}
}
int tempx, tempy;
char buff[32];
int buffidx;
bool noValidChoice;
for(int y = 0; y < HEIGHT; y++) {
for(int x = 0; x < WIDTH; x++) {
memset(buff, 0, 32);
buffidx = 0;
dfsWord(root, buff, buffidx, matrix, used, x, y);
}
}
}
☆─────────────────────────────────────☆
peking2 (myfacebook) 于 (Mon Jan 16 09:34:02 2012, 美东) 提到:
Kao。这个就是我被出的题。最后没写完代码。
☆─────────────────────────────────────☆
peking2 (myfacebook) 于 (Mon Jan 16 09:36:44 2012, 美东) 提到:
这题以前讨论过吗？我面试的时候第一次见。
☆─────────────────────────────────────☆
peking2 (myfacebook) 于 (Mon Jan 16 09:55:14 2012, 美东) 提到:
我onsite的时候还要求返回最多可能的那些单词 (不止是打印），又增加了一些复杂度
。不过我犯了一个错误就是这段代码。我的想法是每次查完就不再从头查了，所以把下
一个node传下去，不是每次都从root查起。写代码的时候就把两部分给混起来了。虽说
是优化了，但是实现起来就更麻烦了。不过欣慰的是，我的思路还是对的，写出来的代
码也基本跟这个答案一致。就是trie的接口没定义好（没写过trie)。
nt status = TrieSearch(root, buff);
if(status != ENTRYNOTFOUND) {
if(status == ENTRYFOUND)
printf("Found word: %s\n", buff);
if(isValidIndex(x-1, y, used))
dfsWord(root, buff, buffidx+1, matrix, used, x-1, y);
☆─────────────────────────────────────☆
peking2 (myfacebook) 于 (Mon Jan 16 10:00:47 2012, 美东) 提到:
大牛帮我分析一下。我面QA出这题是不是有些偏难呀？
☆─────────────────────────────────────☆
fantasist (fan) 于 (Mon Jan 16 12:31:02 2012, 美东) 提到:
这个算是经典题了吧，我也被面到，因为写过于是轻松搞定
☆─────────────────────────────────────☆
peking2 (myfacebook) 于 (Mon Jan 16 13:39:56 2012, 美东) 提到:
sigh. 见识太少了。
☆─────────────────────────────────────☆
lolhaha (二零一二，做一个有米的人) 于 (Mon Jan 16 17:19:30 2012, 美东) 提到:
下面这段可以优化
if(isValidIndex(x-1, y, used))
dfsWord(root, buff, buffidx+1, matrix, used, x-1, y);
if(isValidIndex(x-1, y-1, used))
dfsWord(root, buff, buffidx+1, matrix, used, x-1, y-1);
if(isValidIndex(x, y-1, used))
dfsWord(root, buff, buffidx+1, matrix, used, x, y-1);
if(isValidIndex(x+1, y-1, used))
dfsWord(root, buff, buffidx+1, matrix, used, x+1, y-1);
if(isValidIndex(x+1, y, used))
dfsWord(root, buff, buffidx+1, matrix, used, x+1, y);
if(isValidIndex(x+1, y+1, used))
dfsWord(root, buff, buffidx+1, matrix, used, x+1, y+1);
if(isValidIndex(x, y+1, used))
dfsWord(root, buff, buffidx+1, matrix, used, x, y+1);
if(isValidIndex(x-1, y+1, used))
dfsWord(root, buff, buffidx+1, matrix, used, x-1, y+1);
☆─────────────────────────────────────☆
peking2 (myfacebook) 于 (Mon Jan 16 17:24:07 2012, 美东) 提到:
优化大师来了。怎么优化比较好呢？
☆─────────────────────────────────────☆
lolhaha (二零一二，做一个有米的人) 于 (Mon Jan 16 17:27:39 2012, 美东) 提到:
认真想半个小时
一会公布结果
☆─────────────────────────────────────☆
peking2 (myfacebook) 于 (Mon Jan 16 17:32:43 2012, 美东) 提到:
for loop吗？
☆─────────────────────────────────────☆
lolhaha (二零一二，做一个有米的人) 于 (Mon Jan 16 17:36:09 2012, 美东) 提到:
en
☆─────────────────────────────────────☆
lolhaha (二零一二，做一个有米的人) 于 (Mon Jan 16 17:47:47 2012, 美东) 提到:
其实对你这个整体design也有点疑问
既然想用class,就应该把insert/search也做为成员函数。
否则的话，写ctor/dtor也意义不大，还不如用malloc/free
☆─────────────────────────────────────☆
peking2 (myfacebook) 于 (Mon Jan 16 17:52:35 2012, 美东) 提到:
是。
☆─────────────────────────────────────☆
peking2 (myfacebook) 于 (Mon Jan 16 17:53:19 2012, 美东) 提到:
每次到这个时候脑子里都想应该generalize一下。但是脑子懒就会这样写下去。
☆─────────────────────────────────────☆
lolhaha (二零一二，做一个有米的人) 于 (Mon Jan 16 17:56:26 2012, 美东) 提到:
我发现看别人的东西，挑毛病的时候还真能想到很多
自己写的话可能还真发现不了这些问题
☆─────────────────────────────────────☆
peking2 (myfacebook) 于 (Mon Jan 16 18:05:53 2012, 美东) 提到:
是。所以让别人code review还是挺重要的。提高的捷径呀。
☆─────────────────────────────────────☆
zodiac (Respect Differences) 于 (Mon Jan 16 18:52:31 2012, 美东) 提到:
试着写了个递归的trie，五十行左右
class CTrie
{
public:
CTrie() {
for (int i = 0; i < 26 ; i++){
branch[i] = NULL;
}
IsEnd_ = false;
Val_ = 0;
}
virtual ~CTrie(){
for (int i = 0; i < 26 ; i++){
delete branch[i];
}
}
bool IsEnd() {return IsEnd_;}
void SetEnd() {IsEnd_ = true;}
void InsertString(string s){
if(s.empty()){
SetEnd();
return;
}
else{
if(!branch[*s.begin() - 'a'])
branch[*s.begin() - 'a'] = new CTrie;
branch[*s.begin() - 'a']->InsertString(s.substr(1,s.size()-1));
}
}
bool RetriveString(string s){
if(s.empty()){
if(IsEnd())
return true;
else
return false;
}
else if(branch[*s.begin() - 'a'])
return branch[*s.begin()-'a']->RetriveString(s.substr(1,s.size()
-1));
else
return false;
}
protected:
CTrie *branch[26];
bool IsEnd_;
int Val_;
};
☆─────────────────────────────────────☆
moneybull (moneybull) 于 (Mon Jan 16 19:57:15 2012, 美东) 提到:
靠,主贴怎么找不到了?
☆─────────────────────────────────────☆
moneybull (moneybull) 于 (Mon Jan 16 19:57:30 2012, 美东) 提到:
靠,只有一个帖子了?
☆─────────────────────────────────────☆
fantasist (fan) 于 (Mon Jan 16 22:55:28 2012, 美东) 提到:
随手写的，确实没在意太多。其实还应该分文件呢。。
☆─────────────────────────────────────☆
peking2 (myfacebook) 于 (Mon Jan 16 23:40:08 2012, 美东) 提到:
我碰到那题是要求返回从一个字符开始找，能找到的最多的单词。返回所有的单词。所
以最后的答案可能是从几个邻居辐射出去，而不是一个邻居一条路径那样。你能试试写
写吗？
☆─────────────────────────────────────☆
fantasist (fan) 于 (Mon Jan 16 23:53:31 2012, 美东) 提到:
退役了，不做题了
☆─────────────────────────────────────☆
peking2 (myfacebook) 于 (Mon Jan 16 23:58:07 2012, 美东) 提到:
sigh
libei (Bei) 于 (Wed Jan 11 15:43:39 2012, 美东) 提到:
面试官是Google+组的，
一上来她说看到我简历上的一篇测试自动化的文章，读了一遍，感觉"very
informative"，让后让我介绍一下相关经验。让我小高兴了一下。
第一题是coding，做的还算顺利，后来她评价说所有的cases都覆盖到了。可能算是过
关吧。
第二题我想复杂了，然后在她提示下才解决。自我感觉很不好。其实sort一下就差不多
了，不过我往复杂的树结构想去了。虽然树结构确实能解决这个问题，不过当时我解释
得很不清楚。反正很不爽。
最后瞎聊时间，她说我提到的测试自动化实践和Google内部的基本完全一样blahblah。
。。，不过我觉得这点也算不上加分吧，是个人进google一段时间后都能学会。就怕她
觉得我想问题太复杂，直接negative。
大家有啥建议想法？？
☆─────────────────────────────────────☆
peking2 (myfacebook) 于 (Wed Jan 11 16:02:51 2012, 美东) 提到:
SET吗？
☆─────────────────────────────────────☆
quicklogic (兔八哥) 于 (Wed Jan 11 16:04:37 2012, 美东) 提到:
What questions did she ask? Mind sharing?
☆─────────────────────────────────────☆
libei (Bei) 于 (Wed Jan 11 16:05:24 2012, 美东) 提到:
我投的是New Grads，HR告诉我这个职位进去后才分组，
另外她说G里面developer自己也要写很多自动化的测试，特别是Unit level的，SET主要是负责
functional level的。其实现在新一些的公司都这么做。
☆─────────────────────────────────────☆
libei (Bei) 于 (Wed Jan 11 16:07:14 2012, 美东) 提到:
还在面中，
☆─────────────────────────────────────☆
peking2 (myfacebook) 于 (Wed Jan 11 16:08:17 2012, 美东) 提到:
G的电面比较容易过。onsite就比较麻烦。很多人觉得答的很好还是悲剧。摸不清楚他
们onsite主要是看什么。
☆─────────────────────────────────────☆
runPython (凸-.- 我挺郭德刚) 于 (Wed Jan 11 17:41:21 2012, 美东) 提到:
看解题思路吧
☆─────────────────────────────────────☆
peking2 (myfacebook) 于 (Wed Jan 11 18:04:44 2012, 美东) 提到:
我从最naive的算法谈起，一层层到最优解，还是不行。
☆─────────────────────────────────────☆
lolhaha (二零一二，做一个有米的人) 于 (Wed Jan 11 18:15:31 2012, 美东) 提到:
人家一看你就是准备过
所以这不能证明你的实力
你应该直接上次优解
然后在他的提示下逐步得到最优解
☆─────────────────────────────────────☆
fingerdancer (碍眼猫) 于 (Wed Jan 11 18:39:32 2012, 美东) 提到:
这年头不准备不行，准备还是不行，真是不让人活了
☆─────────────────────────────────────☆
quantx (X矿工) 于 (Wed Jan 11 19:14:27 2012, 美东) 提到:
too much personal thinking. just wait.
☆─────────────────────────────────────☆
peking2 (myfacebook) 于 (Wed Jan 11 20:15:26 2012, 美东) 提到:
碰到的题还真都没见过。但是解法跟其他题雷同。有一个直接给了最优解用trie，结果
让我code，麻烦大了，时间不够。后来他说他就是想让我用dictionary。这样代码就没
那么长了。sigh。也不早说。
☆─────────────────────────────────────☆
quantx (X矿工) 于 (Wed Jan 11 20:20:37 2012, 美东) 提到:
dictionary can be implemented by trie, hash table, and binary search tree.
☆─────────────────────────────────────☆
peking2 (myfacebook) 于 (Wed Jan 11 20:27:21 2012, 美东) 提到:
那我概念有问题了。C#里dictionary就是hashtable呀。Java，C++里dictionary是什么
data structure?
☆─────────────────────────────────────☆
libei (Bei) 于 (Wed Jan 11 21:02:36 2012, 美东) 提到:
这里Dictionary一般是说数据结构里面的定义，和具体语言关系不大阿。
另外你看一下IDictionary接口有很多实现，包含Hashtable和Dictionary，各种实现都
算是“Dictionary”
☆─────────────────────────────────────☆
quantx (X矿工) 于 (Wed Jan 11 21:06:01 2012, 美东) 提到:
yes, it's a problem.
☆─────────────────────────────────────☆
peking2 (myfacebook) 于 (Wed Jan 11 21:50:03 2012, 美东) 提到:
但是他也指出来trie比dictionary要更优化呀。
☆─────────────────────────────────────☆
guangyi ( 光一) 于 (Wed Jan 11 21:58:44 2012, 美东) 提到:
我面ms的时候也有题我用了trie,对方后来告诉我期望的是简单的hash,但是我把trie写
出来了,尽管费时比较多但是对方也很满意.
☆─────────────────────────────────────☆
peking2 (myfacebook) 于 (Wed Jan 11 22:16:25 2012, 美东) 提到:
我跟你情况应该是差不多的。但是我trie没写完。我本来也没有写过trie。唉。我刚才
想了想trie确实要优化，这样很多情况就直接return了，如果用hashtable的话就要
brute force了。还是自己太弱，准备的时候以为随便聊聊trie就可以了。结果真写
code就露怯了。
☆─────────────────────────────────────☆
lolhaha (二零一二，做一个有米的人) 于 (Wed Jan 11 22:28:24 2012, 美东) 提到:
Trie就是一个多叉树
比方说26字母/0-9之类
没那么麻烦
你这次自己写写，下次就不会出问题了
☆─────────────────────────────────────☆
peking2 (myfacebook) 于 (Wed Jan 11 22:32:33 2012, 美东) 提到:
嗯。只是读过一个tutorial，应该好好练练。不过Trie加上面试题，写起来也比较麻烦
。像我这基础，练了trie下次不定又栽在什么上边了。
☆─────────────────────────────────────☆
lolhaha (二零一二，做一个有米的人) 于 (Wed Jan 11 22:36:10 2012, 美东) 提到:
常见数据结构
旧那么几种
统统写10遍
☆─────────────────────────────────────☆
peking2 (myfacebook) 于 (Wed Jan 11 22:39:21 2012, 美东) 提到:
red-black要写吗？
☆─────────────────────────────────────☆
lolhaha (二零一二，做一个有米的人) 于 (Wed Jan 11 22:55:23 2012, 美东) 提到:
我从来没写过，基本上认为不会让写这个，
不过，你要有时间，最好全会
☆─────────────────────────────────────☆
quantx (X矿工) 于 (Wed Jan 11 22:57:15 2012, 美东) 提到:
还是有点麻烦。压力下现想现写不易。
☆─────────────────────────────────────☆
Hbase (Hbase) 于 (Thu Jan 12 01:17:37 2012, 美东) 提到:
这个能面试时间写好也是神人了
面试官自己完全没有理由记得那些细节吧
让写这个，我觉得也就只有某国的人想刁难人才会吧，你要让他写肯定不会
☆─────────────────────────────────────☆
appscan (appscan) 于 (Sun Jan 15 23:24:08 2012, 美东) 提到:
我电面AMAZON的时候写了TRIE的实现。。。
☆─────────────────────────────────────☆
quantx (X矿工) 于 (Sun Jan 15 23:25:22 2012, 美东) 提到:
牛。超过20行不好写。
☆─────────────────────────────────────☆
peking2 (myfacebook) 于 (Sun Jan 15 23:29:10 2012, 美东) 提到:
如果准备过应该没问题吧。如果单纯写个trie的话。
☆─────────────────────────────────────☆
quantx (X矿工) 于 (Sun Jan 15 23:29:48 2012, 美东) 提到:
照抄当然简单。
☆─────────────────────────────────────☆
fantasist (fan) 于 (Sun Jan 15 23:55:18 2012, 美东) 提到:
trie很好写的，而且面试时也常考（至少概念要清楚），强烈推荐准备
☆─────────────────────────────────────☆
quantx (X矿工) 于 (Mon Jan 16 00:00:24 2012, 美东) 提到:
给个20行实现看看？
☆─────────────────────────────────────☆
fantasist (fan) 于 (Mon Jan 16 01:55:26 2012, 美东) 提到:
20行的没有，只有80行的。。。
☆─────────────────────────────────────☆
quantx (X矿工) 于 (Mon Jan 16 01:56:33 2012, 美东) 提到:
一个面试写80行？牛逼。
☆─────────────────────────────────────☆
peking2 (myfacebook) 于 (Mon Jan 16 02:00:01 2012, 美东) 提到:
那也share一下吧。
☆─────────────────────────────────────☆
fantasist (fan) 于 (Mon Jan 16 02:32:37 2012, 美东) 提到:
单独的貌似没有，就发完整的boggle game代码吧
#include
#include
#include
#define ENTRYNOTFOUND 0
#define ENTRYFOUND 1
#define NOTCOMPLETE 2
struct Trie;
void FindWords(Trie *root);
struct Trie
{
Trie();
~Trie();
Trie *children[26];
bool isEnd;
};
Trie::Trie()
{
for(int i = 0; i < 26; i++)
children[i] = NULL;
isEnd = false;
}
Trie::~Trie()
{
for(int i = 0; i < 26; i++) {
if(children[i]) {
delete children[i];
children[i] = NULL;
}
}
}
void TrieInsert(Trie *root, const char *str)
{
if(!str || *str < 'a' || *str > 'z') {
printf("Invalid line\n");
return;
}
Trie *cur = root;
while(*str >= 'a' && *str <= 'z') {
int index = (int)(*str - 'a');
if(cur->children[index] == NULL) {
cur->children[index] = new Trie();
}
cur = cur->children[index];
str++;
}
if(cur != root)
cur->isEnd = true;
}
int TrieSearch(Trie *root, const char *str)
{
if(!str || *str < 'a' || *str > 'z') {
printf("Invalid string!\n");
return ENTRYNOTFOUND;
}
printf("Looking for word %s\n", str);
Trie *cur = root;
while(*str >= 'a' && *str <= 'z') {
int index = (int)(*str - 'a');
if(cur->children[index]) {
cur = cur->children[index];
str++;
}
else
return ENTRYNOTFOUND;
}
if(cur != root && cur->isEnd)
return ENTRYFOUND;
else
return NOTCOMPLETE;
}
int main()
{
Trie *root = new Trie();
FILE *fp = fopen("dictionary.txt", "r");
if(!fp) {
printf("Cannot find dictionary file\n");
exit(-1);
}
char buff[32];
int count = 0;
while(fgets(buff, 31, fp) != NULL) {
TrieInsert(root, buff);
memset(buff, 0, 32);
count++;
}
fclose(fp);
printf("Loaded %d words\n", count);
FindWords(root);
delete root;
return 0;
}
#define WIDTH 4
#define HEIGHT 4
bool isValidIndex(int x, int y, bool used[HEIGHT][WIDTH])
{
if(x >= 0 && x < WIDTH && y >= 0 && y < HEIGHT && !used[y][x])
return true;
else
return false;
}
void dfsWord(Trie *root, char *buff, int buffidx, char matrix[HEIGHT][WIDTH]
, bool used[HEIGHT][WIDTH], int x, int y)
{
/*
if(buffidx > 0)
printf("Current buffer: %s\n", buff);
*/
buff[buffidx] = matrix[y][x];
used[y][x] = true;
int status = TrieSearch(root, buff);
if(status != ENTRYNOTFOUND) {
if(status == ENTRYFOUND)
printf("Found word: %s\n", buff);
if(isValidIndex(x-1, y, used))
dfsWord(root, buff, buffidx+1, matrix, used, x-1, y);
if(isValidIndex(x-1, y-1, used))
dfsWord(root, buff, buffidx+1, matrix, used, x-1, y-1);
if(isValidIndex(x, y-1, used))
dfsWord(root, buff, buffidx+1, matrix, used, x, y-1);
if(isValidIndex(x+1, y-1, used))
dfsWord(root, buff, buffidx+1, matrix, used, x+1, y-1);
if(isValidIndex(x+1, y, used))
dfsWord(root, buff, buffidx+1, matrix, used, x+1, y);
if(isValidIndex(x+1, y+1, used))
dfsWord(root, buff, buffidx+1, matrix, used, x+1, y+1);
if(isValidIndex(x, y+1, used))
dfsWord(root, buff, buffidx+1, matrix, used, x, y+1);
if(isValidIndex(x-1, y+1, used))
dfsWord(root, buff, buffidx+1, matrix, used, x-1, y+1);
}
buff[buffidx] = 0;
used[y][x] = false;
}
void FindWords(Trie *root)
{
char matrix[HEIGHT][WIDTH] = {
{'t', 'e', 'g', 's'},
{'r', 'e', 'i', 't'},
{'n', 'i', 'f', 'o'},
{'g', 'l', 'k', 'c'},
};
bool used[HEIGHT][WIDTH];
for(int i = 0; i < HEIGHT; i++) {
for(int j = 0; j < WIDTH; j++) {
used[i][j] = false;
}
}
int tempx, tempy;
char buff[32];
int buffidx;
bool noValidChoice;
for(int y = 0; y < HEIGHT; y++) {
for(int x = 0; x < WIDTH; x++) {
memset(buff, 0, 32);
buffidx = 0;
dfsWord(root, buff, buffidx, matrix, used, x, y);
}
}
}
☆─────────────────────────────────────☆
peking2 (myfacebook) 于 (Mon Jan 16 09:34:02 2012, 美东) 提到:
Kao。这个就是我被出的题。最后没写完代码。
☆─────────────────────────────────────☆
peking2 (myfacebook) 于 (Mon Jan 16 09:36:44 2012, 美东) 提到:
这题以前讨论过吗？我面试的时候第一次见。
☆─────────────────────────────────────☆
peking2 (myfacebook) 于 (Mon Jan 16 09:55:14 2012, 美东) 提到:
我onsite的时候还要求返回最多可能的那些单词 (不止是打印），又增加了一些复杂度
。不过我犯了一个错误就是这段代码。我的想法是每次查完就不再从头查了，所以把下
一个node传下去，不是每次都从root查起。写代码的时候就把两部分给混起来了。虽说
是优化了，但是实现起来就更麻烦了。不过欣慰的是，我的思路还是对的，写出来的代
码也基本跟这个答案一致。就是trie的接口没定义好（没写过trie)。
nt status = TrieSearch(root, buff);
if(status != ENTRYNOTFOUND) {
if(status == ENTRYFOUND)
printf("Found word: %s\n", buff);
if(isValidIndex(x-1, y, used))
dfsWord(root, buff, buffidx+1, matrix, used, x-1, y);
☆─────────────────────────────────────☆
peking2 (myfacebook) 于 (Mon Jan 16 10:00:47 2012, 美东) 提到:
大牛帮我分析一下。我面QA出这题是不是有些偏难呀？
☆─────────────────────────────────────☆
fantasist (fan) 于 (Mon Jan 16 12:31:02 2012, 美东) 提到:
这个算是经典题了吧，我也被面到，因为写过于是轻松搞定
☆─────────────────────────────────────☆
peking2 (myfacebook) 于 (Mon Jan 16 13:39:56 2012, 美东) 提到:
sigh. 见识太少了。
☆─────────────────────────────────────☆
lolhaha (二零一二，做一个有米的人) 于 (Mon Jan 16 17:19:30 2012, 美东) 提到:
下面这段可以优化
if(isValidIndex(x-1, y, used))
dfsWord(root, buff, buffidx+1, matrix, used, x-1, y);
if(isValidIndex(x-1, y-1, used))
dfsWord(root, buff, buffidx+1, matrix, used, x-1, y-1);
if(isValidIndex(x, y-1, used))
dfsWord(root, buff, buffidx+1, matrix, used, x, y-1);
if(isValidIndex(x+1, y-1, used))
dfsWord(root, buff, buffidx+1, matrix, used, x+1, y-1);
if(isValidIndex(x+1, y, used))
dfsWord(root, buff, buffidx+1, matrix, used, x+1, y);
if(isValidIndex(x+1, y+1, used))
dfsWord(root, buff, buffidx+1, matrix, used, x+1, y+1);
if(isValidIndex(x, y+1, used))
dfsWord(root, buff, buffidx+1, matrix, used, x, y+1);
if(isValidIndex(x-1, y+1, used))
dfsWord(root, buff, buffidx+1, matrix, used, x-1, y+1);
☆─────────────────────────────────────☆
peking2 (myfacebook) 于 (Mon Jan 16 17:24:07 2012, 美东) 提到:
优化大师来了。怎么优化比较好呢？
☆─────────────────────────────────────☆
lolhaha (二零一二，做一个有米的人) 于 (Mon Jan 16 17:27:39 2012, 美东) 提到:
认真想半个小时
一会公布结果
☆─────────────────────────────────────☆
peking2 (myfacebook) 于 (Mon Jan 16 17:32:43 2012, 美东) 提到:
for loop吗？
☆─────────────────────────────────────☆
lolhaha (二零一二，做一个有米的人) 于 (Mon Jan 16 17:36:09 2012, 美东) 提到:
en
☆─────────────────────────────────────☆
lolhaha (二零一二，做一个有米的人) 于 (Mon Jan 16 17:47:47 2012, 美东) 提到:
其实对你这个整体design也有点疑问
既然想用class,就应该把insert/search也做为成员函数。
否则的话，写ctor/dtor也意义不大，还不如用malloc/free
☆─────────────────────────────────────☆
peking2 (myfacebook) 于 (Mon Jan 16 17:52:35 2012, 美东) 提到:
是。
☆─────────────────────────────────────☆
peking2 (myfacebook) 于 (Mon Jan 16 17:53:19 2012, 美东) 提到:
每次到这个时候脑子里都想应该generalize一下。但是脑子懒就会这样写下去。
☆─────────────────────────────────────☆
lolhaha (二零一二，做一个有米的人) 于 (Mon Jan 16 17:56:26 2012, 美东) 提到:
我发现看别人的东西，挑毛病的时候还真能想到很多
自己写的话可能还真发现不了这些问题
☆─────────────────────────────────────☆
peking2 (myfacebook) 于 (Mon Jan 16 18:05:53 2012, 美东) 提到:
是。所以让别人code review还是挺重要的。提高的捷径呀。
☆─────────────────────────────────────☆
zodiac (Respect Differences) 于 (Mon Jan 16 18:52:31 2012, 美东) 提到:
试着写了个递归的trie，五十行左右
class CTrie
{
public:
CTrie() {
for (int i = 0; i < 26 ; i++){
branch[i] = NULL;
}
IsEnd_ = false;
Val_ = 0;
}
virtual ~CTrie(){
for (int i = 0; i < 26 ; i++){
delete branch[i];
}
}
bool IsEnd() {return IsEnd_;}
void SetEnd() {IsEnd_ = true;}
void InsertString(string s){
if(s.empty()){
SetEnd();
return;
}
else{
if(!branch[*s.begin() - 'a'])
branch[*s.begin() - 'a'] = new CTrie;
branch[*s.begin() - 'a']->InsertString(s.substr(1,s.size()-1));
}
}
bool RetriveString(string s){
if(s.empty()){
if(IsEnd())
return true;
else
return false;
}
else if(branch[*s.begin() - 'a'])
return branch[*s.begin()-'a']->RetriveString(s.substr(1,s.size()
-1));
else
return false;
}
protected:
CTrie *branch[26];
bool IsEnd_;
int Val_;
};
☆─────────────────────────────────────☆
moneybull (moneybull) 于 (Mon Jan 16 19:57:15 2012, 美东) 提到:
靠,主贴怎么找不到了?
☆─────────────────────────────────────☆
moneybull (moneybull) 于 (Mon Jan 16 19:57:30 2012, 美东) 提到:
靠,只有一个帖子了?
☆─────────────────────────────────────☆
fantasist (fan) 于 (Mon Jan 16 22:55:28 2012, 美东) 提到:
随手写的，确实没在意太多。其实还应该分文件呢。。
☆─────────────────────────────────────☆
peking2 (myfacebook) 于 (Mon Jan 16 23:40:08 2012, 美东) 提到:
我碰到那题是要求返回从一个字符开始找，能找到的最多的单词。返回所有的单词。所
以最后的答案可能是从几个邻居辐射出去，而不是一个邻居一条路径那样。你能试试写
写吗？
☆─────────────────────────────────────☆
fantasist (fan) 于 (Mon Jan 16 23:53:31 2012, 美东) 提到:
退役了，不做题了
☆─────────────────────────────────────☆
peking2 (myfacebook) 于 (Mon Jan 16 23:58:07 2012, 美东) 提到:
sigh