Groupon 2面 面经# JobHunting - 待字闺中
e*0
1 楼
给出16 characters（可能有重复的）， 求在4*4的Grid上输出 valid words. (即每行
每列都是valid 4字母单词)。 给了字典。
a / / /
/ / / /
/ / / /
/ / / /
每列都是valid 4字母单词)。 给了字典。
a / / /
/ / / /
/ / / /
/ / / /
D*d
2 楼
My 2 cents:
1. 根据字典里四字词建立 Trie: 四层 每层 26, 共 26^4, O(1)。这样使得像以下查
询为 O(1): 是否存在第三个字母为 X? 是否存在 ABC 为前缀的单词
2. Grid 位置上字母可能出现在单词里的位置
1 & 1,2 & 1,3 & 1,4 \
1,2 & 2 & 2,3 & 2,4 \
1,3 & 3,2 & 3 & 3,4 \
1,4 & 4,2 & 4,3 & 4 \
然后用回溯 DFS, 就像解 Sukodu 一样
1. 根据字典里四字词建立 Trie: 四层 每层 26, 共 26^4, O(1)。这样使得像以下查
询为 O(1): 是否存在第三个字母为 X? 是否存在 ABC 为前缀的单词
2. Grid 位置上字母可能出现在单词里的位置
1 & 1,2 & 1,3 & 1,4 \
1,2 & 2 & 2,3 & 2,4 \
1,3 & 3,2 & 3 & 3,4 \
1,4 & 4,2 & 4,3 & 4 \
然后用回溯 DFS, 就像解 Sukodu 一样
l*n
3 楼
电面问的啊？一个问题就覆盖好多内容。
【在 e******0 的大作中提到】
: 给出16 characters（可能有重复的）， 求在4*4的Grid上输出 valid words. (即每行
: 每列都是valid 4字母单词)。 给了字典。
: a / / /
: / / / /
: / / / /
: / / / /
【在 e******0 的大作中提到】
: 给出16 characters（可能有重复的）， 求在4*4的Grid上输出 valid words. (即每行
: 每列都是valid 4字母单词)。 给了字典。
: a / / /
: / / / /
: / / / /
: / / / /
e*0
4 楼
他有提示用PREFIX来做。
但完全没有思路。
觉得应该和SUKUDU的思路一样。
【在 D**********d 的大作中提到】
: My 2 cents:
: 1. 根据字典里四字词建立 Trie: 四层 每层 26, 共 26^4, O(1)。这样使得像以下查
: 询为 O(1): 是否存在第三个字母为 X? 是否存在 ABC 为前缀的单词
:
: 2. Grid 位置上字母可能出现在单词里的位置
: 1 & 1,2 & 1,3 & 1,4 \
: 1,2 & 2 & 2,3 & 2,4 \
: 1,3 & 3,2 & 3 & 3,4 \
: 1,4 & 4,2 & 4,3 & 4 \
: 然后用回溯 DFS, 就像解 Sukodu 一样
但完全没有思路。
觉得应该和SUKUDU的思路一样。
【在 D**********d 的大作中提到】
: My 2 cents:
: 1. 根据字典里四字词建立 Trie: 四层 每层 26, 共 26^4, O(1)。这样使得像以下查
: 询为 O(1): 是否存在第三个字母为 X? 是否存在 ABC 为前缀的单词
:
: 2. Grid 位置上字母可能出现在单词里的位置
: 1 & 1,2 & 1,3 & 1,4 \
: 1,2 & 2 & 2,3 & 2,4 \
: 1,3 & 3,2 & 3 & 3,4 \
: 1,4 & 4,2 & 4,3 & 4 \
: 然后用回溯 DFS, 就像解 Sukodu 一样
l*n
5 楼
prefix就是用来check viability的吧，楼上说的没错，还是sodoku的思路。
就是找个空位扔一个未用的字符进去，然后check每个方向是否有希望成为单词，也就
是看的当前字符构成的prefix。但凡判定有人不能延伸为单词，就backtrack。
【在 e******0 的大作中提到】
: 他有提示用PREFIX来做。
: 但完全没有思路。
: 觉得应该和SUKUDU的思路一样。
就是找个空位扔一个未用的字符进去，然后check每个方向是否有希望成为单词，也就
是看的当前字符构成的prefix。但凡判定有人不能延伸为单词，就backtrack。
【在 e******0 的大作中提到】
: 他有提示用PREFIX来做。
: 但完全没有思路。
: 觉得应该和SUKUDU的思路一样。
e*0
6 楼
我觉得 根据字典里四字词建立 Trie树， 四层 每层 16（如果有重复的字符就会小于
16）, 共 16^4。 然后通过Trie 树， 来做validation 和 backtracking。
是这样的吗？
这样空间复杂度 和 时间复杂度 岂不是特别特别大？
谢谢。
【在 l*n 的大作中提到】
: prefix就是用来check viability的吧，楼上说的没错，还是sodoku的思路。
: 就是找个空位扔一个未用的字符进去，然后check每个方向是否有希望成为单词，也就
: 是看的当前字符构成的prefix。但凡判定有人不能延伸为单词，就backtrack。
16）, 共 16^4。 然后通过Trie 树， 来做validation 和 backtracking。
是这样的吗？
这样空间复杂度 和 时间复杂度 岂不是特别特别大？
谢谢。
【在 l*n 的大作中提到】
: prefix就是用来check viability的吧，楼上说的没错，还是sodoku的思路。
: 就是找个空位扔一个未用的字符进去，然后check每个方向是否有希望成为单词，也就
: 是看的当前字符构成的prefix。但凡判定有人不能延伸为单词，就backtrack。
l*n
7 楼
真实现的话，我觉得不用上trie，因为单词都不长，不如直接搞一个字母、2字母、3字
母、四字母的hashtable。最差情况也就是把词典size*4而已。
【在 e******0 的大作中提到】
: 我觉得 根据字典里四字词建立 Trie树， 四层 每层 16（如果有重复的字符就会小于
: 16）, 共 16^4。 然后通过Trie 树， 来做validation 和 backtracking。
: 是这样的吗？
: 这样空间复杂度 和 时间复杂度 岂不是特别特别大？
: 谢谢。
母、四字母的hashtable。最差情况也就是把词典size*4而已。
【在 e******0 的大作中提到】
: 我觉得 根据字典里四字词建立 Trie树， 四层 每层 16（如果有重复的字符就会小于
: 16）, 共 16^4。 然后通过Trie 树， 来做validation 和 backtracking。
: 是这样的吗？
: 这样空间复杂度 和 时间复杂度 岂不是特别特别大？
: 谢谢。
n*e
8 楼
能问一下，为什么Trie树每层16？
【在 e******0 的大作中提到】
: 我觉得 根据字典里四字词建立 Trie树， 四层 每层 16（如果有重复的字符就会小于
: 16）, 共 16^4。 然后通过Trie 树， 来做validation 和 backtracking。
: 是这样的吗？
: 这样空间复杂度 和 时间复杂度 岂不是特别特别大？
: 谢谢。
【在 e******0 的大作中提到】
: 我觉得 根据字典里四字词建立 Trie树， 四层 每层 16（如果有重复的字符就会小于
: 16）, 共 16^4。 然后通过Trie 树， 来做validation 和 backtracking。
: 是这样的吗？
: 这样空间复杂度 和 时间复杂度 岂不是特别特别大？
: 谢谢。
e*0
9 楼
我是根据DreamingBird大牛的大作想的。
就我的理解，DreamingBird 提出的思路是每层26，是因为26个字母。
题目中已经给出16个字母（有重复）， 那么其实每层16就应该OK了。
这只是我的想法。
欢迎指教~~~~
【在 n****e 的大作中提到】
: 能问一下，为什么Trie树每层16？
就我的理解，DreamingBird 提出的思路是每层26，是因为26个字母。
题目中已经给出16个字母（有重复）， 那么其实每层16就应该OK了。
这只是我的想法。
欢迎指教~~~~
【在 n****e 的大作中提到】
: 能问一下，为什么Trie树每层16？
n*e
10 楼
感觉预处理字典挺麻烦的，如果字典很大呢？
试贴一简单解法：
bool check(unordered_set& dict, char *a, int i) {
// a[] is a permutation of the char set
// based on the elements a[0]-a[i], check if a[] a could be a solution.
int N = 4, k= (i+1)/N; // k: complete line number
string s(a,a+N*N);
for (int l = 0; l
if (k==N-1) { // check columns
for(int n= 0; n < (i+1)%N; n++) {
string t("");
for (int l=0; l
if( dict.find(t) == dict.end() ) return false;
}
}
return true;
}
// i starts with -1 when calling
//
char *wordgrid(unordered_set& dict, char *a, int i) {
int N = 4; // 4x4 grid
if (!check(dict,a,i)) return NULL;
if (i == N*N-1)
if (check(dict,a,i)) {
char *p = new char [N*N];
for( int k=0; k
}
i++;
for( int k = i; k
for (int l=0; l
char *q = wordgrid(dict,p, i);
delete [] p;
if (q!=NULL) return q;
}
return NULL;
}
试贴一简单解法：
bool check(unordered_set
// a[] is a permutation of the char set
// based on the elements a[0]-a[i], check if a[] a could be a solution.
int N = 4, k= (i+1)/N; // k: complete line number
string s(a,a+N*N);
for (int l = 0; l
if (k==N-1) { // check columns
for(int n= 0; n < (i+1)%N; n++) {
string t("");
for (int l=0; l
if( dict.find(t) == dict.end() ) return false;
}
}
return true;
}
// i starts with -1 when calling
//
char *wordgrid(unordered_set
int N = 4; // 4x4 grid
if (!check(dict,a,i)) return NULL;
if (i == N*N-1)
if (check(dict,a,i)) {
char *p = new char [N*N];
for( int k=0; k
}
i++;
for( int k = i; k
for (int l=0; l
char *q = wordgrid(dict,p, i);
delete [] p;
if (q!=NULL) return q;
}
return NULL;
}
e*0
11 楼
给出16 characters（可能有重复的）， 求在4*4的Grid上输出 valid words. (即每行
每列都是valid 4字母单词)。 给了字典。
a / / /
/ / / /
/ / / /
/ / / /
每列都是valid 4字母单词)。 给了字典。
a / / /
/ / / /
/ / / /
/ / / /
D*d
12 楼
My 2 cents:
1. 根据字典里四字词建立 Trie: 四层 每层 26, 共 26^4, O(1)。这样使得像以下查
询为 O(1): 是否存在第三个字母为 X? 是否存在 ABC 为前缀的单词
2. Grid 位置上字母可能出现在单词里的位置
1 & 1,2 & 1,3 & 1,4 \
1,2 & 2 & 2,3 & 2,4 \
1,3 & 3,2 & 3 & 3,4 \
1,4 & 4,2 & 4,3 & 4 \
然后用回溯 DFS, 就像解 Sukodu 一样
1. 根据字典里四字词建立 Trie: 四层 每层 26, 共 26^4, O(1)。这样使得像以下查
询为 O(1): 是否存在第三个字母为 X? 是否存在 ABC 为前缀的单词
2. Grid 位置上字母可能出现在单词里的位置
1 & 1,2 & 1,3 & 1,4 \
1,2 & 2 & 2,3 & 2,4 \
1,3 & 3,2 & 3 & 3,4 \
1,4 & 4,2 & 4,3 & 4 \
然后用回溯 DFS, 就像解 Sukodu 一样
l*n
13 楼
电面问的啊？一个问题就覆盖好多内容。
【在 e******0 的大作中提到】
: 给出16 characters（可能有重复的）， 求在4*4的Grid上输出 valid words. (即每行
: 每列都是valid 4字母单词)。 给了字典。
: a / / /
: / / / /
: / / / /
: / / / /
【在 e******0 的大作中提到】
: 给出16 characters（可能有重复的）， 求在4*4的Grid上输出 valid words. (即每行
: 每列都是valid 4字母单词)。 给了字典。
: a / / /
: / / / /
: / / / /
: / / / /
e*0
14 楼
他有提示用PREFIX来做。
但完全没有思路。
觉得应该和SUKUDU的思路一样。
【在 D**********d 的大作中提到】
: My 2 cents:
: 1. 根据字典里四字词建立 Trie: 四层 每层 26, 共 26^4, O(1)。这样使得像以下查
: 询为 O(1): 是否存在第三个字母为 X? 是否存在 ABC 为前缀的单词
:
: 2. Grid 位置上字母可能出现在单词里的位置
: 1 & 1,2 & 1,3 & 1,4 \
: 1,2 & 2 & 2,3 & 2,4 \
: 1,3 & 3,2 & 3 & 3,4 \
: 1,4 & 4,2 & 4,3 & 4 \
: 然后用回溯 DFS, 就像解 Sukodu 一样
但完全没有思路。
觉得应该和SUKUDU的思路一样。
【在 D**********d 的大作中提到】
: My 2 cents:
: 1. 根据字典里四字词建立 Trie: 四层 每层 26, 共 26^4, O(1)。这样使得像以下查
: 询为 O(1): 是否存在第三个字母为 X? 是否存在 ABC 为前缀的单词
:
: 2. Grid 位置上字母可能出现在单词里的位置
: 1 & 1,2 & 1,3 & 1,4 \
: 1,2 & 2 & 2,3 & 2,4 \
: 1,3 & 3,2 & 3 & 3,4 \
: 1,4 & 4,2 & 4,3 & 4 \
: 然后用回溯 DFS, 就像解 Sukodu 一样
l*n
15 楼
prefix就是用来check viability的吧，楼上说的没错，还是sodoku的思路。
就是找个空位扔一个未用的字符进去，然后check每个方向是否有希望成为单词，也就
是看的当前字符构成的prefix。但凡判定有人不能延伸为单词，就backtrack。
【在 e******0 的大作中提到】
: 他有提示用PREFIX来做。
: 但完全没有思路。
: 觉得应该和SUKUDU的思路一样。
就是找个空位扔一个未用的字符进去，然后check每个方向是否有希望成为单词，也就
是看的当前字符构成的prefix。但凡判定有人不能延伸为单词，就backtrack。
【在 e******0 的大作中提到】
: 他有提示用PREFIX来做。
: 但完全没有思路。
: 觉得应该和SUKUDU的思路一样。
e*0
16 楼
我觉得 根据字典里四字词建立 Trie树， 四层 每层 16（如果有重复的字符就会小于
16）, 共 16^4。 然后通过Trie 树， 来做validation 和 backtracking。
是这样的吗？
这样空间复杂度 和 时间复杂度 岂不是特别特别大？
谢谢。
【在 l*n 的大作中提到】
: prefix就是用来check viability的吧，楼上说的没错，还是sodoku的思路。
: 就是找个空位扔一个未用的字符进去，然后check每个方向是否有希望成为单词，也就
: 是看的当前字符构成的prefix。但凡判定有人不能延伸为单词，就backtrack。
16）, 共 16^4。 然后通过Trie 树， 来做validation 和 backtracking。
是这样的吗？
这样空间复杂度 和 时间复杂度 岂不是特别特别大？
谢谢。
【在 l*n 的大作中提到】
: prefix就是用来check viability的吧，楼上说的没错，还是sodoku的思路。
: 就是找个空位扔一个未用的字符进去，然后check每个方向是否有希望成为单词，也就
: 是看的当前字符构成的prefix。但凡判定有人不能延伸为单词，就backtrack。
l*n
17 楼
真实现的话，我觉得不用上trie，因为单词都不长，不如直接搞一个字母、2字母、3字
母、四字母的hashtable。最差情况也就是把词典size*4而已。
【在 e******0 的大作中提到】
: 我觉得 根据字典里四字词建立 Trie树， 四层 每层 16（如果有重复的字符就会小于
: 16）, 共 16^4。 然后通过Trie 树， 来做validation 和 backtracking。
: 是这样的吗？
: 这样空间复杂度 和 时间复杂度 岂不是特别特别大？
: 谢谢。
母、四字母的hashtable。最差情况也就是把词典size*4而已。
【在 e******0 的大作中提到】
: 我觉得 根据字典里四字词建立 Trie树， 四层 每层 16（如果有重复的字符就会小于
: 16）, 共 16^4。 然后通过Trie 树， 来做validation 和 backtracking。
: 是这样的吗？
: 这样空间复杂度 和 时间复杂度 岂不是特别特别大？
: 谢谢。
n*e
18 楼
能问一下，为什么Trie树每层16？
【在 e******0 的大作中提到】
: 我觉得 根据字典里四字词建立 Trie树， 四层 每层 16（如果有重复的字符就会小于
: 16）, 共 16^4。 然后通过Trie 树， 来做validation 和 backtracking。
: 是这样的吗？
: 这样空间复杂度 和 时间复杂度 岂不是特别特别大？
: 谢谢。
【在 e******0 的大作中提到】
: 我觉得 根据字典里四字词建立 Trie树， 四层 每层 16（如果有重复的字符就会小于
: 16）, 共 16^4。 然后通过Trie 树， 来做validation 和 backtracking。
: 是这样的吗？
: 这样空间复杂度 和 时间复杂度 岂不是特别特别大？
: 谢谢。
e*0
19 楼
我是根据DreamingBird大牛的大作想的。
就我的理解，DreamingBird 提出的思路是每层26，是因为26个字母。
题目中已经给出16个字母（有重复）， 那么其实每层16就应该OK了。
这只是我的想法。
欢迎指教~~~~
【在 n****e 的大作中提到】
: 能问一下，为什么Trie树每层16？
就我的理解，DreamingBird 提出的思路是每层26，是因为26个字母。
题目中已经给出16个字母（有重复）， 那么其实每层16就应该OK了。
这只是我的想法。
欢迎指教~~~~
【在 n****e 的大作中提到】
: 能问一下，为什么Trie树每层16？
n*e
20 楼
感觉预处理字典挺麻烦的，如果字典很大呢？
试贴一简单解法：
bool check(unordered_set& dict, char *a, int i) {
// a[] is a permutation of the char set
// based on the elements a[0]-a[i], check if a[] a could be a solution.
int N = 4, k= (i+1)/N; // k: complete line number
string s(a,a+N*N);
for (int l = 0; l
if (k==N-1) { // check columns
for(int n= 0; n < (i+1)%N; n++) {
string t("");
for (int l=0; l
if( dict.find(t) == dict.end() ) return false;
}
}
return true;
}
// i starts with -1 when calling
//
char *wordgrid(unordered_set& dict, char *a, int i) {
int N = 4; // 4x4 grid
if (!check(dict,a,i)) return NULL;
if (i == N*N-1)
if (check(dict,a,i)) {
char *p = new char [N*N];
for( int k=0; k
}
i++;
for( int k = i; k
for (int l=0; l
char *q = wordgrid(dict,p, i);
delete [] p;
if (q!=NULL) return q;
}
return NULL;
}
试贴一简单解法：
bool check(unordered_set
// a[] is a permutation of the char set
// based on the elements a[0]-a[i], check if a[] a could be a solution.
int N = 4, k= (i+1)/N; // k: complete line number
string s(a,a+N*N);
for (int l = 0; l
if (k==N-1) { // check columns
for(int n= 0; n < (i+1)%N; n++) {
string t("");
for (int l=0; l
if( dict.find(t) == dict.end() ) return false;
}
}
return true;
}
// i starts with -1 when calling
//
char *wordgrid(unordered_set
int N = 4; // 4x4 grid
if (!check(dict,a,i)) return NULL;
if (i == N*N-1)
if (check(dict,a,i)) {
char *p = new char [N*N];
for( int k=0; k
}
i++;
for( int k = i; k
for (int l=0; l
char *q = wordgrid(dict,p, i);
delete [] p;
if (q!=NULL) return q;
}
return NULL;
}
D*d
21 楼
是每层最多 16, 因为不在给的 16 个字母里的 单词不用考虑
【在 e******0 的大作中提到】
: 我是根据DreamingBird大牛的大作想的。
: 就我的理解，DreamingBird 提出的思路是每层26，是因为26个字母。
: 题目中已经给出16个字母（有重复）， 那么其实每层16就应该OK了。
: 这只是我的想法。
: 欢迎指教~~~~
【在 e******0 的大作中提到】
: 我是根据DreamingBird大牛的大作想的。
: 就我的理解，DreamingBird 提出的思路是每层26，是因为26个字母。
: 题目中已经给出16个字母（有重复）， 那么其实每层16就应该OK了。
: 这只是我的想法。
: 欢迎指教~~~~
l*g
22 楼
把字典用suffix tree存放。
给出16 characters（可能有重复的）， 求在4*4的Grid上输出 valid words. (即每行
每列都是valid 4字母单词)。 给了字典。a / / / ........
【在 e******0 的大作中提到】
: 给出16 characters（可能有重复的）， 求在4*4的Grid上输出 valid words. (即每行
: 每列都是valid 4字母单词)。 给了字典。
: a / / /
: / / / /
: / / / /
: / / / /
给出16 characters（可能有重复的）， 求在4*4的Grid上输出 valid words. (即每行
每列都是valid 4字母单词)。 给了字典。a / / / ........
【在 e******0 的大作中提到】
: 给出16 characters（可能有重复的）， 求在4*4的Grid上输出 valid words. (即每行
: 每列都是valid 4字母单词)。 给了字典。
: a / / /
: / / / /
: / / / /
: / / / /
t*e
23 楼
电面考这个就是不让人过的意思？onsite这也算是大招了吧。
t*e
24 楼
大概是trie+backtrace+hashtable...
建立trie是为了按prefix快速查找。
backtrace from 0 to 3, at each step i, fill in row i and col i at the same
time. chars before i are already determined, and char at i must be the same.
create hash table to group candidates from row i and col i that char i are
equal. test and keep going down or backtrace.
for example, suppose we are at level 2. we have
x x A x
x x B x
C D = ?
x x ? ?
'x's and A/B/C/D are the chars we already fill out.
at level 2, all information we know is:
1. row 2 must be a word AB..
2. col 2 must be a word CD..
3. the third char of the two word must be equal
so we find all {AB..} and {CD..} from tree, and group them by hashing third
char. so we have
u-> {ABu.} {CDu.}
v-> {ABv.} {CDv.}
......
each combination from 2 sets for a hash key need to be tested.
建立trie是为了按prefix快速查找。
backtrace from 0 to 3, at each step i, fill in row i and col i at the same
time. chars before i are already determined, and char at i must be the same.
create hash table to group candidates from row i and col i that char i are
equal. test and keep going down or backtrace.
for example, suppose we are at level 2. we have
x x A x
x x B x
C D = ?
x x ? ?
'x's and A/B/C/D are the chars we already fill out.
at level 2, all information we know is:
1. row 2 must be a word AB..
2. col 2 must be a word CD..
3. the third char of the two word must be equal
so we find all {AB..} and {CD..} from tree, and group them by hashing third
char. so we have
u-> {ABu.} {CDu.}
v-> {ABv.} {CDv.}
......
each combination from 2 sets for a hash key need to be tested.
y*3
25 楼
请问这道题怎么解？过几天就要groupon goods电面了，求解法。。谢谢！
【在 e******0 的大作中提到】
: 给出16 characters（可能有重复的）， 求在4*4的Grid上输出 valid words. (即每行
: 每列都是valid 4字母单词)。 给了字典。
: a / / /
: / / / /
: / / / /
: / / / /
【在 e******0 的大作中提到】
: 给出16 characters（可能有重复的）， 求在4*4的Grid上输出 valid words. (即每行
: 每列都是valid 4字母单词)。 给了字典。
: a / / /
: / / / /
: / / / /
: / / / /
相关阅读
RFE还没消息，有啥办法没？EQ靠锻炼：软软的鸠头萨提亚的经验 (转载)求比较2个offerh1b transfer期间离开美国有影响吗？做个调查，老中真正爱写code的有多少？码农和妓女比， 谁的青春饭长久一点？问下已经毕业但是OPT还没开始怎么拿钱今天听说弯曲好几个公司要裁员刚才随便翻翻我在亚马逊的购买历史 (转载)为什么码工都喜欢互相喷请大家帮忙支招：文科转CS职业前景（不是坑，谢谢）从码工到售前Group Interview 请教请指教怎么选择uber和airbnb？马工真是青春饭啊FB蹭饭门在国内媒体发酵：老中应对须知 (转载)刚刚收到口头offer赵大牛为啥要奔N家啊帮朋友问，uber现在pkg多少呀T a b l e a u 昂塞特面经