Redian新闻
>
番茄收过一茬,不结果了, 该拔掉吗
avatar
番茄收过一茬,不结果了, 该拔掉吗# gardening - 拈花惹草
r*m
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
avatar
x*g
2
小房出租,每月也就几百,租客打算paypal付款。听有人说paypal不保险,是这样吗?
有什么风险?
avatar
H*H
3
看到有专门卖Left-Handed Easi-Grip Scissors
http://www.zulily.com/p/green-left-handed-easi-grip-scissors-73
我家小妞儿还弄不清她左手右手的倾向,目前貌似是平均的。本来我不介意左右手倾向
,觉得多用左手好,但据说左撇子因为工具和机械上的开关操纵杆不趁手特别容易受伤
,感觉还是选择性地“掰”一下比较好。
用这个剪刀的话我不介意她用左手。
avatar
c*2
4
猜测是因为高温,最近气温一直在95以上,估计这气候还要持续两三个月,是该拔掉种
其他的还是等等看还有收获吗? 第一茬收货的番茄皮光溜滑的,最近收获的都是歪瓜裂
枣而且皮糙,要多难看就有多难看。
avatar
j*y
5
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

avatar
y*n
6
avatar
r*f
7
顶锅盖说,这剪刀是故意坑钱的么?
比如最常见的fiskars, 到处都很便宜,开学后更是白菜价,本来不就是左右手都可以
用的吗?
avatar
r*m
8
所有题都要
avatar
z*3
9
收钱方有手续费的吧
avatar
a*e
10
普通店里就有left-handed的剪子,像rite-aid
avatar
j*g
11
前一阵一面直接就问了我五道题,然后就跪了~~
avatar
s*1
12
小额没什么问题,让对方用friends&family发送付款
avatar
p*2
13
第一题bfs,第三题trie
第二题忘记spaning tree的算法了。
这是什么公司?
avatar
a*e
14
一直用,没听说,没感觉。paypal 有专门FAQ 关于怎样操作交房租以避免交PayPal手
续费。不过如果想逃税的话还是想别的办法吧。

【在 x*******g 的大作中提到】
: 小房出租,每月也就几百,租客打算paypal付款。听有人说paypal不保险,是这样吗?
: 有什么风险?

avatar
l*b
15
二爷不用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的算法了。
: 这是什么公司?

avatar
l*b
16
然后想了一下,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()];
}
avatar
p*2
17

刚看了一下题,昨天看错题目了。我再看看。

【在 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);
: }
:

avatar
j*g
18
第二题 是不是把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; iwhile(si[i]!=t[j] && jj++;
if(j==t_len)
return false;
j++;
}
return true;
}
avatar
l*b
19
好像是啊,我想太复杂了。

【在 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;

avatar
H*s
20
原题要看是否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;

avatar
a*e
21
这样也行吧?
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;

avatar
H*s
22
不过除了函数名,code 是对的!

【在 H****s 的大作中提到】
: 原题要看是否subsequence 不是 substr
avatar
H*s
23
这个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;
: }

avatar
t*a
24
第三题很有趣,偶来给个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是什么公司啊?
avatar
l*h
25
第三题怎么用trie呢?

【在 p*****2 的大作中提到】
: 第一题bfs,第三题trie
: 第二题忘记spaning tree的算法了。
: 这是什么公司?

avatar
p*2
26

不好意思,我当时以为是substring

【在 l**h 的大作中提到】
: 第三题怎么用trie呢?
avatar
l*h
27
假设是substring的话,建立一个suffix tree?
感觉题目特别强调原始String很大,估计建立suffix tree memory消耗很大吧

【在 p*****2 的大作中提到】
:
: 不好意思,我当时以为是substring

avatar
t*a
28
不懂suffix tree的用法,不过根据
http://en.wikipedia.org/wiki/Suffix_tree
alignment中的gap是不能乱来的,影响计算速度

【在 l**h 的大作中提到】
: 假设是substring的话,建立一个suffix tree?
: 感觉题目特别强调原始String很大,估计建立suffix tree memory消耗很大吧

avatar
r*m
29
一面
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
avatar
j*y
30
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

avatar
r*m
31
所有题都要
avatar
j*g
32
前一阵一面直接就问了我五道题,然后就跪了~~
avatar
p*2
33
第一题bfs,第三题trie
第二题忘记spaning tree的算法了。
这是什么公司?
avatar
l*b
34
二爷不用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的算法了。
: 这是什么公司?

avatar
l*b
35
然后想了一下,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()];
}
avatar
p*2
36

刚看了一下题,昨天看错题目了。我再看看。

【在 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);
: }
:

avatar
j*g
37
第二题 是不是把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; iwhile(si[i]!=t[j] && jj++;
if(j==t_len)
return false;
j++;
}
return true;
}
avatar
l*b
38
好像是啊,我想太复杂了。

【在 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;

avatar
H*s
39
原题要看是否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;

avatar
a*e
40
这样也行吧?
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;

avatar
H*s
41
不过除了函数名,code 是对的!

【在 H****s 的大作中提到】
: 原题要看是否subsequence 不是 substr
avatar
H*s
42
这个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;
: }

avatar
t*a
43
第三题很有趣,偶来给个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是什么公司啊?
avatar
l*h
44
第三题怎么用trie呢?

【在 p*****2 的大作中提到】
: 第一题bfs,第三题trie
: 第二题忘记spaning tree的算法了。
: 这是什么公司?

avatar
p*2
45

不好意思,我当时以为是substring

【在 l**h 的大作中提到】
: 第三题怎么用trie呢?
avatar
l*h
46
假设是substring的话,建立一个suffix tree?
感觉题目特别强调原始String很大,估计建立suffix tree memory消耗很大吧

【在 p*****2 的大作中提到】
:
: 不好意思,我当时以为是substring

avatar
t*a
47
不懂suffix tree的用法,不过根据
http://en.wikipedia.org/wiki/Suffix_tree
alignment中的gap是不能乱来的,影响计算速度

【在 l**h 的大作中提到】
: 假设是substring的话,建立一个suffix tree?
: 感觉题目特别强调原始String很大,估计建立suffix tree memory消耗很大吧

avatar
h*2
48
有哪位大神能详细讲一下 二面中的两道题吗?
对于第二道题, 我能想到的是:
可以用一个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'
avatar
a*3
49
第三题给个其他解法,说了查询字符串都较小,而且又是求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
avatar
b*u
50
free text search 应该是上suffix tree
尽管建tree开销大但是考虑是stream of short strings,还是有必要的,否则每个小字
符串都要遍历一遍大串
avatar
m*i
51
lmo什么公司
avatar
a*3
52
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,还是有必要的,否则每个小字
: 符串都要遍历一遍大串

avatar
d*3
53
嗯,这个简单好写!

【在 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;

avatar
d*3
54
大牛,你这个我看不懂啊...

【在 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))) (

相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。