f****e
发帖数: 30 | 1 第一次：given two integer numbers n and k, print all combinations of k
numbers out of 1 ... n
e.g. if k = 2, n = 4, print
1 2
1 3
1 4
2 3
2 4
3 4
第二次:
if you have a grid
a b c e
d f a h
i j k l
and a dictionary with more than 10K words
print out all words in dictionary that can be obtained by visiting grid.
restriction: if a word is c1, c2, ..., cn, then c_(i+1) should be one of the
eight neighbors of c_i in the grid
第二题出了递归还有什么办法？ 我写了一个递归程序，对方问我可以有什么
improvement,想了半天没想出来。 |
S******A
发帖数: 1002 | 2 2 is boggle problem
load dic as trie to stop searching immediately upon a dead-end, i guess you
also need to avoid re-using any cell (char) more than once when constructing
a valid word |
f****e
发帖数: 30 | 3 I mentioned trie and that guy asked me to implement it. I said I can not
implement it in just 10 min.
Yes, the problem requires that no char can be used more than once when
constructing a valid word.
you
constructing
【在 S******A 的大作中提到】
: 2 is boggle problem
: load dic as trie to stop searching immediately upon a dead-end, i guess you
: also need to avoid re-using any cell (char) more than once when constructing
: a valid word
|
W***i
发帖数: 9134 | 4 "k numbers out of 1 ... n" 啥意思? |
H*M
发帖数: 1268 | 5 select k numbers out of 1,2,...n
【在 W***i 的大作中提到】
: "k numbers out of 1 ... n" 啥意思?
|
B*****t
发帖数: 335 | 6 my code for first problem, not tested.
const int N = 1000;
int b[N], a[N];
int n;
void dfs(int a[], int cur, int level) {
if(level==k) {
copy(b, b+k, ostream(cout," "));
cout<
return;
}
int i, j;
for(i=cur+1; i<=n; i++) {
b[level+1] = a[i];
dfs(a, i, level+1);
}
} |
B*****t
发帖数: 335 | 7 for the 2nd problem, recursion is not efficient.
Trie or AC-Automation is the only choice! Do 8 direction search on them and
need lots of optimizations and some tricks I think.
【在 f****e 的大作中提到】
: 第一次：given two integer numbers n and k, print all combinations of k
: numbers out of 1 ... n
: e.g. if k = 2, n = 4, print
: 1 2
: 1 3
: 1 4
: 2 3
: 2 4
: 3 4
: 第二次:
|
B*****t
发帖数: 335 | 8 May I ask how could you get the phone interview?
thanks.
【在 f****e 的大作中提到】
: 第一次：given two integer numbers n and k, print all combinations of k
: numbers out of 1 ... n
: e.g. if k = 2, n = 4, print
: 1 2
: 1 3
: 1 4
: 2 3
: 2 4
: 3 4
: 第二次:
|
f****e
发帖数: 30 | 9 internal referral. 申的是research scientist,按照SDE的标准面试
【在 B*****t 的大作中提到】
: May I ask how could you get the phone interview?
: thanks.
|
B*****t
发帖数: 335 | 10 Thanks! and bless you for the future interviews.
【在 f****e 的大作中提到】
: internal referral. 申的是research scientist,按照SDE的标准面试
|
f**r
发帖数: 865 | 11 For the second question, the problem space does not seem to be polynomial.
Maximum of n^2 nodes in the search path, at each step >>1 choices on average
, even after taking "visited" flag into consideration. Are the interviewer
looking for a solution that's not exponential? |
k***g
发帖数: 75 | 12 第二个我觉得recursive没啥问题，recursive和trie也没啥矛盾，recursive的过程就
是建trie的过程，如果发现字典里没有，也就结束了。recursive相当于是DFS，也可以
用BFS。
【在 f****e 的大作中提到】
: 第一次：given two integer numbers n and k, print all combinations of k
: numbers out of 1 ... n
: e.g. if k = 2, n = 4, print
: 1 2
: 1 3
: 1 4
: 2 3
: 2 4
: 3 4
: 第二次:
|
k***g
发帖数: 75 | 13 你的面试题比我难多了啊，我面的他们的基础设施组，问的问题都好简单。总共四个编
程题，atoi，不用sqrt库函数求sqrt，strstr，反转单链表。
【在 f****e 的大作中提到】
: internal referral. 申的是research scientist,按照SDE的标准面试
|
h****h
发帖数: 75 | 14 我也被面到了第二个问题。我给的就是recursive function with backtracking and
also walking in trie tree.
我到没有被要求实现trie tree, 但是说明了在recursive function的那些地方检查
trie tree。
【在 f****e 的大作中提到】
: 第一次：given two integer numbers n and k, print all combinations of k
: numbers out of 1 ... n
: e.g. if k = 2, n = 4, print
: 1 2
: 1 3
: 1 4
: 2 3
: 2 4
: 3 4
: 第二次:
|
