r****m
发帖数: 70 | 1 一面
You are given two words A and B of the same length from a dictionary D. You
can only access this dictionary through a function boolean isInDictionary(
string word). We are going to make a word ladder. We start at A, we end with
B, and change one letter at every step.
All words are over the alphabet [a-z]. |A| <= 10 characters. |D| <= 10 000
000 words.
We are looking for a shortest word ladder, if any exists. If many exist,
return any one of them.
A=dog, B=let
D={dog, let, log, leg, puzzle, bicycle}
dog
log
leg
let
二面
1. given a cactus graph, determine the number of different spanning trees of
this graph.
2. Given a very large string T, |T| = 10 000 000 chars
a stream of small strings Si
check if Si is a subsequence of T ? return true/false
number of Si ~ 100 000 000 (strings)
|Si| ~ 100 chars
'a' to 'z'
T = abcdefg
S1 = abc yes
S2 = ag yes
S3 = ga no
S4 = aa no |
j*****y
发帖数: 1071 | 2 cactus graph那道题是要写 code 吗？
You
with
【在 r****m 的大作中提到】
: 一面
: You are given two words A and B of the same length from a dictionary D. You
: can only access this dictionary through a function boolean isInDictionary(
: string word). We are going to make a word ladder. We start at A, we end with
: B, and change one letter at every step.
: All words are over the alphabet [a-z]. |A| <= 10 characters. |D| <= 10 000
: 000 words.
: We are looking for a shortest word ladder, if any exists. If many exist,
: return any one of them.
: A=dog, B=let
|
r****m
发帖数: 70 | |
j********g
发帖数: 80 | |
p*****2
发帖数: 21240 | 5 第一题bfs，第三题trie
第二题忘记spaning tree的算法了。
这是什么公司？ |
l**b
发帖数: 457 | 6 二爷不用DP，奇怪啊！第3题用Trie的话memory吃不消吧？用DP是不是好点？
贴个简单的代码，helper是recursive的，helper2是DP的，2爷帮忙看看，是不是又出
错了：
public boolean isSubSequence(String s, String t) {
assert(s != null && t != null);
if (t.length() == 0) return true;
//return helper(s, t, 0, 0);
return helper2(s, t);
}
private boolean helper(String s, String t, int si, int ti) {
if (ti == t.length()) return true;
if (si >= s.length()) return false;
if (s.charAt(si) == t.charAt(ti)) {
return helper(s, t, si + 1, ti + 1);
} else {
return helper(s, t, si + 1, ti);
}
}
private boolean helper2(String s, String t) {
boolean[][] dp = new boolean[t.length() + 1][s.length() + 1];
dp[0][0] = true;
for (int i = 0; i <= s.length(); i++) {
dp[0][i] = true;
}
for (int i = 1; i <= t.length(); i++) {
for (int j = 1; j <= s.length(); j++) {
if (t.charAt(i - 1) == s.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = dp[i][j - 1];
}
}
}
return dp[t.length()][s.length()];
}
【在 p*****2 的大作中提到】
: 第一题bfs，第三题trie
: 第二题忘记spaning tree的算法了。
: 这是什么公司？
|
l**b
发帖数: 457 | 7 然后想了一下，DP的空间好像可以优化到O(|Si|):
private boolean helper3(String s, String t) {
boolean[] dp = new boolean[s.length() + 1];
for (int i = 0; i <= s.length(); i++) {
dp[i] = true;
}
for (int i = 1; i <= t.length(); i++) {
boolean[] newDp = new boolean[s.length() + 1];
for (int j = 1; j <= s.length(); j++) {
if (t.charAt(i - 1) == s.charAt(j - 1)) {
newDp[j] = dp[j - 1];
} else {
newDp[j] = newDp[j - 1];
}
}
dp = newDp;
}
return dp[s.length()];
} |
p*****2
发帖数: 21240 | 8
刚看了一下题，昨天看错题目了。我再看看。
【在 l**b 的大作中提到】
: 二爷不用DP，奇怪啊！第3题用Trie的话memory吃不消吧？用DP是不是好点？
: 贴个简单的代码，helper是recursive的，helper2是DP的，2爷帮忙看看，是不是又出
: 错了：
: public boolean isSubSequence(String s, String t) {
: assert(s != null && t != null);
: if (t.length() == 0) return true;
: //return helper(s, t, 0, 0);
: return helper2(s, t);
: }
:
|
j********g
发帖数: 80 | 9 第二题 是不是把s按顺序扫一遍就行了， 我没理解错吧
bool find_substr(string si, string t){
int s_len=si.size();
int t_len=t.size();
int j=0;
for(int i=0; i
while(si[i]!=t[j] && j
j++;
if(j==t_len)
return false;
j++;
}
return true;
} |
l**b
发帖数: 457 | 10 好像是啊，我想太复杂了。
【在 j********g 的大作中提到】
: 第二题 是不是把s按顺序扫一遍就行了， 我没理解错吧
: bool find_substr(string si, string t){
: int s_len=si.size();
: int t_len=t.size();
: int j=0;
: for(int i=0; i: while(si[i]!=t[j] && j: j++;
: if(j==t_len)
: return false;
|
|
|
H****s
发帖数: 247 | 11 原题要看是否subsequence 不是 substr
【在 j********g 的大作中提到】
: 第二题 是不是把s按顺序扫一遍就行了， 我没理解错吧
: bool find_substr(string si, string t){
: int s_len=si.size();
: int t_len=t.size();
: int j=0;
: for(int i=0; i: while(si[i]!=t[j] && j: j++;
: if(j==t_len)
: return false;
|
a**********e
发帖数: 22 | 12 这样也行吧？
static boolean isSubString(char[] s, char[] t){
int s_len = s.length;
int t_len = t.length;
int j = 0;
for(int i = 0; i < s_len; i++){
if(s[i]==t[j]){
if(j == t_len -1){
return true;
}
j++;
}
}
return false;
}
【在 j********g 的大作中提到】
: 第二题 是不是把s按顺序扫一遍就行了， 我没理解错吧
: bool find_substr(string si, string t){
: int s_len=si.size();
: int t_len=t.size();
: int j=0;
: for(int i=0; i: while(si[i]!=t[j] && j: j++;
: if(j==t_len)
: return false;
|
H****s
发帖数: 247 | 13 不过除了函数名，code 是对的！
【在 H****s 的大作中提到】
: 原题要看是否subsequence 不是 substr
|
H****s
发帖数: 247 | 14 这个code有问题吧？ if(s[i]!=t[j]) j不变？ s 跟 t 搞反了？
【在 a**********e 的大作中提到】
: 这样也行吧？
: static boolean isSubString(char[] s, char[] t){
: int s_len = s.length;
: int t_len = t.length;
: int j = 0;
: for(int i = 0; i < s_len; i++){
: if(s[i]==t[j]){
: if(j == t_len -1){
: return true;
: }
|
t****a
发帖数: 1212 | 15 第三题很有趣，偶来给个clojure的解
基本思路是
1. 对T做预处理，构建graph，同时，记录每个字符a-z所出现的位置
2. 由于S长度<100，数量却很大(100M)，意味着有很多重复，使用memoize function会
大大减少计算量
下面的程序在1/1000大小的S数据集上运行需要1.7秒。观察了一下时间和数据集大小趋
势，在完整数据集上几分钟内也可以产生结果
(def alphabet (map char (range (int \a) (inc (int \z)))))
(def T (vec (take 10000000 (repeatedly #(rand-nth alphabet)))))
(def S (take 100000 (repeatedly (fn [] (take (inc (int (* (rand) 100))) (
repeatedly #(rand-nth alphabet)))))))
(def T-ix (group-by #(T %) (range (count T))))
(def T-map (let [pairs (distinct (partition 2 (interleave (pop T) (next T))))
map0 (group-by #(first %) pairs)]
(zipmap (keys map0) (map last (vals map0)))))
(def good-align?
(memoize
(fn [[x & xs] pos]
(let [xp-set (T-ix x)
xp (first (drop-while #(<= % pos) xp-set))]
(if (nil? xp)
false
(if (empty? xs)
true
(let [y (first xs)]
(if (and (contains? T-map x) (contains? (T-map x) y))
false
(good-align? xs xp)))))))))
(time (count (pmap #(good-align? % -1) S)))
; "Elapsed time: 1727.207492 msecs"
另外请问楼主，Imo是什么公司啊？ |
l**h
发帖数: 893 | 16 第三题怎么用trie呢?
【在 p*****2 的大作中提到】
: 第一题bfs，第三题trie
: 第二题忘记spaning tree的算法了。
: 这是什么公司？
|
p*****2
发帖数: 21240 | 17
不好意思，我当时以为是substring
【在 l**h 的大作中提到】
: 第三题怎么用trie呢?
|
l**h
发帖数: 893 | 18 假设是substring的话，建立一个suffix tree?
感觉题目特别强调原始String很大，估计建立suffix tree memory消耗很大吧
【在 p*****2 的大作中提到】
:
: 不好意思，我当时以为是substring
|
t****a
发帖数: 1212 | 19 不懂suffix tree的用法，不过根据
http://en.wikipedia.org/wiki/Suffix_tree
alignment中的gap是不能乱来的，影响计算速度
【在 l**h 的大作中提到】
: 假设是substring的话，建立一个suffix tree?
: 感觉题目特别强调原始String很大，估计建立suffix tree memory消耗很大吧
|
r****m
发帖数: 70 | 20 一面
You are given two words A and B of the same length from a dictionary D. You
can only access this dictionary through a function boolean isInDictionary(
string word). We are going to make a word ladder. We start at A, we end with
B, and change one letter at every step.
All words are over the alphabet [a-z]. |A| <= 10 characters. |D| <= 10 000
000 words.
We are looking for a shortest word ladder, if any exists. If many exist,
return any one of them.
A=dog, B=let
D={dog, let, log, leg, puzzle, bicycle}
dog
log
leg
let
二面
1. given a cactus graph, determine the number of different spanning trees of
this graph.
2. Given a very large string T, |T| = 10 000 000 chars
a stream of small strings Si
check if Si is a subsequence of T ? return true/false
number of Si ~ 100 000 000 (strings)
|Si| ~ 100 chars
'a' to 'z'
T = abcdefg
S1 = abc yes
S2 = ag yes
S3 = ga no
S4 = aa no |
|
|
j*****y
发帖数: 1071 | 21 cactus graph那道题是要写 code 吗？
You
with
【在 r****m 的大作中提到】
: 一面
: You are given two words A and B of the same length from a dictionary D. You
: can only access this dictionary through a function boolean isInDictionary(
: string word). We are going to make a word ladder. We start at A, we end with
: B, and change one letter at every step.
: All words are over the alphabet [a-z]. |A| <= 10 characters. |D| <= 10 000
: 000 words.
: We are looking for a shortest word ladder, if any exists. If many exist,
: return any one of them.
: A=dog, B=let
|
r****m
发帖数: 70 | |
j********g
发帖数: 80 | |
p*****2
发帖数: 21240 | 24 第一题bfs，第三题trie
第二题忘记spaning tree的算法了。
这是什么公司？ |
l**b
发帖数: 457 | 25 二爷不用DP，奇怪啊！第3题用Trie的话memory吃不消吧？用DP是不是好点？
贴个简单的代码，helper是recursive的，helper2是DP的，2爷帮忙看看，是不是又出
错了：
public boolean isSubSequence(String s, String t) {
assert(s != null && t != null);
if (t.length() == 0) return true;
//return helper(s, t, 0, 0);
return helper2(s, t);
}
private boolean helper(String s, String t, int si, int ti) {
if (ti == t.length()) return true;
if (si >= s.length()) return false;
if (s.charAt(si) == t.charAt(ti)) {
return helper(s, t, si + 1, ti + 1);
} else {
return helper(s, t, si + 1, ti);
}
}
private boolean helper2(String s, String t) {
boolean[][] dp = new boolean[t.length() + 1][s.length() + 1];
dp[0][0] = true;
for (int i = 0; i <= s.length(); i++) {
dp[0][i] = true;
}
for (int i = 1; i <= t.length(); i++) {
for (int j = 1; j <= s.length(); j++) {
if (t.charAt(i - 1) == s.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = dp[i][j - 1];
}
}
}
return dp[t.length()][s.length()];
}
【在 p*****2 的大作中提到】
: 第一题bfs，第三题trie
: 第二题忘记spaning tree的算法了。
: 这是什么公司？
|
l**b
发帖数: 457 | 26 然后想了一下，DP的空间好像可以优化到O(|Si|):
private boolean helper3(String s, String t) {
boolean[] dp = new boolean[s.length() + 1];
for (int i = 0; i <= s.length(); i++) {
dp[i] = true;
}
for (int i = 1; i <= t.length(); i++) {
boolean[] newDp = new boolean[s.length() + 1];
for (int j = 1; j <= s.length(); j++) {
if (t.charAt(i - 1) == s.charAt(j - 1)) {
newDp[j] = dp[j - 1];
} else {
newDp[j] = newDp[j - 1];
}
}
dp = newDp;
}
return dp[s.length()];
} |
p*****2
发帖数: 21240 | 27
刚看了一下题，昨天看错题目了。我再看看。
【在 l**b 的大作中提到】
: 二爷不用DP，奇怪啊！第3题用Trie的话memory吃不消吧？用DP是不是好点？
: 贴个简单的代码，helper是recursive的，helper2是DP的，2爷帮忙看看，是不是又出
: 错了：
: public boolean isSubSequence(String s, String t) {
: assert(s != null && t != null);
: if (t.length() == 0) return true;
: //return helper(s, t, 0, 0);
: return helper2(s, t);
: }
:
|
j********g
发帖数: 80 | 28 第二题 是不是把s按顺序扫一遍就行了， 我没理解错吧
bool find_substr(string si, string t){
int s_len=si.size();
int t_len=t.size();
int j=0;
for(int i=0; i
while(si[i]!=t[j] && j
j++;
if(j==t_len)
return false;
j++;
}
return true;
} |
l**b
发帖数: 457 | 29 好像是啊，我想太复杂了。
【在 j********g 的大作中提到】
: 第二题 是不是把s按顺序扫一遍就行了， 我没理解错吧
: bool find_substr(string si, string t){
: int s_len=si.size();
: int t_len=t.size();
: int j=0;
: for(int i=0; i: while(si[i]!=t[j] && j: j++;
: if(j==t_len)
: return false;
|
H****s
发帖数: 247 | 30 原题要看是否subsequence 不是 substr
【在 j********g 的大作中提到】
: 第二题 是不是把s按顺序扫一遍就行了， 我没理解错吧
: bool find_substr(string si, string t){
: int s_len=si.size();
: int t_len=t.size();
: int j=0;
: for(int i=0; i: while(si[i]!=t[j] && j: j++;
: if(j==t_len)
: return false;
|
|
|
a**********e
发帖数: 22 | 31 这样也行吧？
static boolean isSubString(char[] s, char[] t){
int s_len = s.length;
int t_len = t.length;
int j = 0;
for(int i = 0; i < s_len; i++){
if(s[i]==t[j]){
if(j == t_len -1){
return true;
}
j++;
}
}
return false;
}
【在 j********g 的大作中提到】
: 第二题 是不是把s按顺序扫一遍就行了， 我没理解错吧
: bool find_substr(string si, string t){
: int s_len=si.size();
: int t_len=t.size();
: int j=0;
: for(int i=0; i: while(si[i]!=t[j] && j: j++;
: if(j==t_len)
: return false;
|
H****s
发帖数: 247 | 32 不过除了函数名，code 是对的！
【在 H****s 的大作中提到】
: 原题要看是否subsequence 不是 substr
|
H****s
发帖数: 247 | 33 这个code有问题吧？ if(s[i]!=t[j]) j不变？ s 跟 t 搞反了？
【在 a**********e 的大作中提到】
: 这样也行吧？
: static boolean isSubString(char[] s, char[] t){
: int s_len = s.length;
: int t_len = t.length;
: int j = 0;
: for(int i = 0; i < s_len; i++){
: if(s[i]==t[j]){
: if(j == t_len -1){
: return true;
: }
|
t****a
发帖数: 1212 | 34 第三题很有趣，偶来给个clojure的解
基本思路是
1. 对T做预处理，构建graph，同时，记录每个字符a-z所出现的位置
2. 由于S长度<100，数量却很大(100M)，意味着有很多重复，使用memoize function会
大大减少计算量
下面的程序在1/1000大小的S数据集上运行需要1.7秒。观察了一下时间和数据集大小趋
势，在完整数据集上几分钟内也可以产生结果
(def alphabet (map char (range (int \a) (inc (int \z)))))
(def T (vec (take 10000000 (repeatedly #(rand-nth alphabet)))))
(def S (take 100000 (repeatedly (fn [] (take (inc (int (* (rand) 100))) (
repeatedly #(rand-nth alphabet)))))))
(def T-ix (group-by #(T %) (range (count T))))
(def T-map (let [pairs (distinct (partition 2 (interleave (pop T) (next T))))
map0 (group-by #(first %) pairs)]
(zipmap (keys map0) (map last (vals map0)))))
(def good-align?
(memoize
(fn [[x & xs] pos]
(let [xp-set (T-ix x)
xp (first (drop-while #(<= % pos) xp-set))]
(if (nil? xp)
false
(if (empty? xs)
true
(let [y (first xs)]
(if (and (contains? T-map x) (contains? (T-map x) y))
false
(good-align? xs xp)))))))))
(time (count (pmap #(good-align? % -1) S)))
; "Elapsed time: 1727.207492 msecs"
另外请问楼主，Imo是什么公司啊？ |
l**h
发帖数: 893 | 35 第三题怎么用trie呢?
【在 p*****2 的大作中提到】
: 第一题bfs，第三题trie
: 第二题忘记spaning tree的算法了。
: 这是什么公司？
|
p*****2
发帖数: 21240 | 36
不好意思，我当时以为是substring
【在 l**h 的大作中提到】
: 第三题怎么用trie呢?
|
l**h
发帖数: 893 | 37 假设是substring的话，建立一个suffix tree?
感觉题目特别强调原始String很大，估计建立suffix tree memory消耗很大吧
【在 p*****2 的大作中提到】
:
: 不好意思，我当时以为是substring
|
t****a
发帖数: 1212 | 38 不懂suffix tree的用法，不过根据
http://en.wikipedia.org/wiki/Suffix_tree
alignment中的gap是不能乱来的，影响计算速度
【在 l**h 的大作中提到】
: 假设是substring的话，建立一个suffix tree?
: 感觉题目特别强调原始String很大，估计建立suffix tree memory消耗很大吧
|
h******2
发帖数: 13 | 39 有哪位大神能详细讲一下 二面中的两道题吗？
对于第二道题， 我能想到的是:
可以用一个map > m_Indexes;
对于每个char，value中记录了index列表。 然后对于T中的每个char，先找第一个char
的leftest位置(smallest index), then find the second char, and it’s index
must be greater than the first’s char ‘s smallest index(that’s upper_
bound), and we do it iteratively until we all found it or not.
第一道 cactus的不太清楚怎么做啊？
二面
1. given a cactus graph, determine the number of different spanning trees of
this graph.
2. Given a very large string T, |T| = 10 000 000 chars
a stream of small strings Si
check if Si is a subsequence of T ? return true/false
number of Si ~ 100 000 000 (strings)
|Si| ~ 100 chars
'a' to 'z' |
a*******3
发帖数: 27 | 40 第三题给个其他解法，说了查询字符串都较小，而且又是求subsequence，有个算法可
以将LCS转化成LIS来计算，转化方法在本题里面，是将短字符串中的每个字符，在T中
出现的位置，由大到小排列，然后求这个序列的LIS。
如
T=abacbdefb
a的位置有(0,2)，b的有(1,4,8),c(3),d(5),e(6),f(7)
S1 = aab =>(2,0,2,0,8,4,1),LIS=>(0,2,8)=3，故yes |
|
|
b*****u
发帖数: 648 | 41 free text search 应该是上suffix tree
尽管建tree开销大但是考虑是stream of short strings,还是有必要的，否则每个小字
符串都要遍历一遍大串 |
m****i
发帖数: 650 | |
a*******3
发帖数: 27 | 43 T = abcdefg
S1 = abc yes
S2 = ag yes
S3 = ga no
S4 = aa no
看楼主给的example，S2，不是match substring，而是subsequence，所以suffix tree
在这里没有用的
【在 b*****u 的大作中提到】
: free text search 应该是上suffix tree
: 尽管建tree开销大但是考虑是stream of short strings,还是有必要的，否则每个小字
: 符串都要遍历一遍大串
|
d*******3
发帖数: 58 | 44 嗯，这个简单好写！
【在 j********g 的大作中提到】
: 第二题 是不是把s按顺序扫一遍就行了， 我没理解错吧
: bool find_substr(string si, string t){
: int s_len=si.size();
: int t_len=t.size();
: int j=0;
: for(int i=0; i: while(si[i]!=t[j] && j: j++;
: if(j==t_len)
: return false;
|
d*******3
发帖数: 58 | 45 大牛，你这个我看不懂啊...
【在 t****a 的大作中提到】
: 第三题很有趣，偶来给个clojure的解
: 基本思路是
: 1. 对T做预处理，构建graph，同时，记录每个字符a-z所出现的位置
: 2. 由于S长度<100，数量却很大(100M)，意味着有很多重复，使用memoize function会
: 大大减少计算量
: 下面的程序在1/1000大小的S数据集上运行需要1.7秒。观察了一下时间和数据集大小趋
: 势，在完整数据集上几分钟内也可以产生结果
: (def alphabet (map char (range (int \a) (inc (int \z)))))
: (def T (vec (take 10000000 (repeatedly #(rand-nth alphabet)))))
: (def S (take 100000 (repeatedly (fn [] (take (inc (int (* (rand) 100))) (
|
