f*4
2 楼
输入是个stream
class input_stream
{
// Character or -1
int read();
}
每次call read（），返回一个char，如果到头了就是返回-1
Find and print repeated sequences of 10 characters
void find_repeated_sequences(input_stream in)
{
string buf;
unordered_set record;
while(true){
char temp = in.read();
if(temp=-1)
break;
buf.push_back(temp);
if(buf.length()>10)
buf = buf.substr(1);
if(buf.lengh()==10){
if(record.count(buf)==1){
cout<
else record.emplace(buf);
}
}
}
挂了。。
当时想先写个work的。。不过后来想了一下，也没想出更好的
大家看看咋写更好
class input_stream
{
// Character or -1
int read();
}
每次call read（），返回一个char，如果到头了就是返回-1
Find and print repeated sequences of 10 characters
void find_repeated_sequences(input_stream in)
{
string buf;
unordered_set
while(true){
char temp = in.read();
if(temp=-1)
break;
buf.push_back(temp);
if(buf.length()>10)
buf = buf.substr(1);
if(buf.lengh()==10){
if(record.count(buf)==1){
cout<
else record.emplace(buf);
}
}
}
挂了。。
当时想先写个work的。。不过后来想了一下，也没想出更好的
大家看看咋写更好
M1
3 楼
food processor包饺子有用处么？
blender呢？
blender呢？
a*9
4 楼
我也是这么做的，国人大哥，所以过了。。。 还有更好的方法么？这个已经是O(n)了
啊
啊
L*3
5 楼
关键看你想吃什么馅了，肉馅加点白菜或韭菜的比较好做。
10个包子教你 哈哈
【在 M1 的大作中提到】
: 都需要那些设备？
: 主要是怎么做陷
10个包子教你 哈哈
【在 M1 的大作中提到】
: 都需要那些设备？
: 主要是怎么做陷
f*4
6 楼
。。。。
fb二面碰见国人挂了
L一面碰见红毛又挂了。。
我真的很想去CA旅游啊。。。让我过一次吧。。
【在 a********9 的大作中提到】
: 我也是这么做的，国人大哥，所以过了。。。 还有更好的方法么？这个已经是O(n)了
: 啊
fb二面碰见国人挂了
L一面碰见红毛又挂了。。
我真的很想去CA旅游啊。。。让我过一次吧。。
【在 a********9 的大作中提到】
: 我也是这么做的，国人大哥，所以过了。。。 还有更好的方法么？这个已经是O(n)了
: 啊
p*e
7 楼
我怎么看了好几遍标题都没有看见那个饺字呢? 是不是最近闲的........ 老有一种要
re的冲动.
re的冲动.
n*e
8 楼
试着写一写：
Find and print repeated sequences of 10 characters
void find_repeated_sequences(input_stream in)
{
string buf;
int count = 0;
map > record;
while(true){
char temp = in.read();
if(temp=-1)
break;
buf.push_back(temp);
if(buf.length()==10)
buf = buf.substr(0, 10);
record[buf].push_back(count);
count++;
buf = buf.substr(1, 9);
}
}
map >::iterator iter;
for (iter = record.begin(); iter != record.end(); iter++) {
if (iter->second.size() > 1) {
int N = iter->second.size();
if (iter->second[N-1] - iter->second[0] >= 10) {
count << iter->first << endl;
}
}
}
}
【在 f********4 的大作中提到】
: 输入是个stream
: class input_stream
: {
: // Character or -1
: int read();
: }
: 每次call read（），返回一个char，如果到头了就是返回-1
: Find and print repeated sequences of 10 characters
: void find_repeated_sequences(input_stream in)
: {
Find and print repeated sequences of 10 characters
void find_repeated_sequences(input_stream in)
{
string buf;
int count = 0;
map
while(true){
char temp = in.read();
if(temp=-1)
break;
buf.push_back(temp);
if(buf.length()==10)
buf = buf.substr(0, 10);
record[buf].push_back(count);
count++;
buf = buf.substr(1, 9);
}
}
map
for (iter = record.begin(); iter != record.end(); iter++) {
if (iter->second.size() > 1) {
int N = iter->second.size();
if (iter->second[N-1] - iter->second[0] >= 10) {
count << iter->first << endl;
}
}
}
}
【在 f********4 的大作中提到】
: 输入是个stream
: class input_stream
: {
: // Character or -1
: int read();
: }
: 每次call read（），返回一个char，如果到头了就是返回-1
: Find and print repeated sequences of 10 characters
: void find_repeated_sequences(input_stream in)
: {
j*u
9 楼
菜还是自己切得比blender打出来的好吃。
w*s
10 楼
这个题目用java能写么？
【在 n****e 的大作中提到】
: 试着写一写：
: Find and print repeated sequences of 10 characters
: void find_repeated_sequences(input_stream in)
: {
: string buf;
: int count = 0;
: map > record;
: while(true){
: char temp = in.read();
: if(temp=-1)
【在 n****e 的大作中提到】
: 试着写一写：
: Find and print repeated sequences of 10 characters
: void find_repeated_sequences(input_stream in)
: {
: string buf;
: int count = 0;
: map
: while(true){
: char temp = in.read();
: if(temp=-1)
d*n
11 楼
yong dao qie~~~yong chaozi jiaoban
【在 M1 的大作中提到】
: 都需要那些设备？
: 主要是怎么做陷
【在 M1 的大作中提到】
: 都需要那些设备？
: 主要是怎么做陷
m*c
12 楼
这个repeated sequences of 10 characters怎么理解？是说找出input_stream里，长
度为10的，重复出现的的吗？
度为10的，重复出现的的吗？
a*n
13 楼
re这个，肉也要自己切，绞的肉馅没味道
【在 j***u 的大作中提到】
: 菜还是自己切得比blender打出来的好吃。
【在 j***u 的大作中提到】
: 菜还是自己切得比blender打出来的好吃。
z*5
14 楼
哥，这个if(temp=-1)太囧了。。。
d*r
15 楼
中国人的那些破东西，有什么好吃的，再说了，吃了不怕变成丑陋的中国人吗？
【在 M1 的大作中提到】
: 都需要那些设备？
: 主要是怎么做陷
【在 M1 的大作中提到】
: 都需要那些设备？
: 主要是怎么做陷
m*4
16 楼
java中，strings immutable，最好不要append在string后面。所以要用StringBuilder
，但StringBuilder 的substring方法又不efficient。不知道他是不是想让你自己
maintain一个能两头插入的data structure，circular array 啥的,
但问题是还得算hashcode，override
equals，麻烦不说，也不可能提高效率很多啊。想不通为什么被废
【在 f********4 的大作中提到】
: 输入是个stream
: class input_stream
: {
: // Character or -1
: int read();
: }
: 每次call read（），返回一个char，如果到头了就是返回-1
: Find and print repeated sequences of 10 characters
: void find_repeated_sequences(input_stream in)
: {
，但StringBuilder 的substring方法又不efficient。不知道他是不是想让你自己
maintain一个能两头插入的data structure，circular array 啥的,
但问题是还得算hashcode，override
equals，麻烦不说，也不可能提高效率很多啊。想不通为什么被废
【在 f********4 的大作中提到】
: 输入是个stream
: class input_stream
: {
: // Character or -1
: int read();
: }
: 每次call read（），返回一个char，如果到头了就是返回-1
: Find and print repeated sequences of 10 characters
: void find_repeated_sequences(input_stream in)
: {
g*1
17 楼
直接去买点没seasoned的肉馅，自己找把菜刀剁点菜，冲姜蒜，然后买包饺子皮就行了。
当然了sams有现成的卖的，将就着也能吃。
【在 M1 的大作中提到】
: 都需要那些设备？
: 主要是怎么做陷
当然了sams有现成的卖的，将就着也能吃。
【在 M1 的大作中提到】
: 都需要那些设备？
: 主要是怎么做陷
l*n
18 楼
repeated sequence of 10 characters，是找另一个abcdefghij？
也算abcabcabcabcabcabc...这种连续重复的？string是要unique的还是所有的？问题
多多啊。
【在 f********4 的大作中提到】
: 输入是个stream
: class input_stream
: {
: // Character or -1
: int read();
: }
: 每次call read（），返回一个char，如果到头了就是返回-1
: Find and print repeated sequences of 10 characters
: void find_repeated_sequences(input_stream in)
: {
也算abcabcabcabcabcabc...这种连续重复的？string是要unique的还是所有的？问题
多多啊。
【在 f********4 的大作中提到】
: 输入是个stream
: class input_stream
: {
: // Character or -1
: int read();
: }
: 每次call read（），返回一个char，如果到头了就是返回-1
: Find and print repeated sequences of 10 characters
: void find_repeated_sequences(input_stream in)
: {
M1
19 楼
主要是不放心速冻饺子的陷，担心都是垃圾肉，垃圾菜。
所以也不放心买肉陷，想自己做肉馅，什么机器可以打肉馅呢？
了。
【在 g*******1 的大作中提到】
: 直接去买点没seasoned的肉馅，自己找把菜刀剁点菜，冲姜蒜，然后买包饺子皮就行了。
: 当然了sams有现成的卖的，将就着也能吃。
所以也不放心买肉陷，想自己做肉馅，什么机器可以打肉馅呢？
了。
【在 g*******1 的大作中提到】
: 直接去买点没seasoned的肉馅，自己找把菜刀剁点菜，冲姜蒜，然后买包饺子皮就行了。
: 当然了sams有现成的卖的，将就着也能吃。
f*4
20 楼
是找另一个前面出现过的序列，也可以连续重复啊，只要重复就可以
算短一点，比如abcabcabcabc，比如说找长度为4
abca,bcab,cabc都是啊
【在 l*n 的大作中提到】
: repeated sequence of 10 characters，是找另一个abcdefghij？
: 也算abcabcabcabcabcabc...这种连续重复的？string是要unique的还是所有的？问题
: 多多啊。
算短一点，比如abcabcabcabc，比如说找长度为4
abca,bcab,cabc都是啊
【在 l*n 的大作中提到】
: repeated sequence of 10 characters，是找另一个abcdefghij？
: 也算abcabcabcabcabcabc...这种连续重复的？string是要unique的还是所有的？问题
: 多多啊。
f*4
21 楼
嗯，一开始我也提了，面试官也没答腔。我就说那我先写个work的吧
StringBuilder
【在 m**********4 的大作中提到】
: java中，strings immutable，最好不要append在string后面。所以要用StringBuilder
: ，但StringBuilder 的substring方法又不efficient。不知道他是不是想让你自己
: maintain一个能两头插入的data structure，circular array 啥的,
: 但问题是还得算hashcode，override
: equals，麻烦不说，也不可能提高效率很多啊。想不通为什么被废
StringBuilder
【在 m**********4 的大作中提到】
: java中，strings immutable，最好不要append在string后面。所以要用StringBuilder
: ，但StringBuilder 的substring方法又不efficient。不知道他是不是想让你自己
: maintain一个能两头插入的data structure，circular array 啥的,
: 但问题是还得算hashcode，override
: equals，麻烦不说，也不可能提高效率很多啊。想不通为什么被废
s*w
22 楼
无脑 rolling hash，对付这种定长的字串专用
从头扫到尾，对当前长度10的子串算一个 hash code, 结果查询以前(set, 或者 unor
dered_set)存起来的 hash code，重复的话，就输出当前的子串
比直接存所有的unique子串要省时间省空间
【在 f********4 的大作中提到】
: 输入是个stream
: class input_stream
: {
: // Character or -1
: int read();
: }
: 每次call read（），返回一个char，如果到头了就是返回-1
: Find and print repeated sequences of 10 characters
: void find_repeated_sequences(input_stream in)
: {
从头扫到尾，对当前长度10的子串算一个 hash code, 结果查询以前(set, 或者 unor
dered_set)存起来的 hash code，重复的话，就输出当前的子串
比直接存所有的unique子串要省时间省空间
【在 f********4 的大作中提到】
: 输入是个stream
: class input_stream
: {
: // Character or -1
: int read();
: }
: 每次call read（），返回一个char，如果到头了就是返回-1
: Find and print repeated sequences of 10 characters
: void find_repeated_sequences(input_stream in)
: {
l*n
23 楼
rolling hash有collision怎么办？最后你还是得存所有unique字串。想省空间还是得
上trie，插入即查询。
unor
【在 s*w 的大作中提到】
: 无脑 rolling hash，对付这种定长的字串专用
: 从头扫到尾，对当前长度10的子串算一个 hash code, 结果查询以前(set, 或者 unor
: dered_set)存起来的 hash code，重复的话，就输出当前的子串
: 比直接存所有的unique子串要省时间省空间
上trie，插入即查询。
unor
【在 s*w 的大作中提到】
: 无脑 rolling hash，对付这种定长的字串专用
: 从头扫到尾，对当前长度10的子串算一个 hash code, 结果查询以前(set, 或者 unor
: dered_set)存起来的 hash code，重复的话，就输出当前的子串
: 比直接存所有的unique子串要省时间省空间
s*u
24 楼
rolling hash只要base取256即可，但好像会oveflow吧。不过我觉得的确是应该用循环
数组，因为你substr和pushback 恐怕都不是o1
数组，因为你substr和pushback 恐怕都不是o1
f*4
25 楼
哦，我去看看rolling hash是神马东西。。
push back和 substr时间复杂度应该都是liner的吧，因为只有10个character，但是空
间复杂度就不好说了，buf = buf.substr(1)我也搞不清是不是call 了copy
constructor
【在 s********u 的大作中提到】
: rolling hash只要base取256即可，但好像会oveflow吧。不过我觉得的确是应该用循环
: 数组，因为你substr和pushback 恐怕都不是o1
push back和 substr时间复杂度应该都是liner的吧，因为只有10个character，但是空
间复杂度就不好说了，buf = buf.substr(1)我也搞不清是不是call 了copy
constructor
【在 s********u 的大作中提到】
: rolling hash只要base取256即可，但好像会oveflow吧。不过我觉得的确是应该用循环
: 数组，因为你substr和pushback 恐怕都不是o1
J*3
26 楼
能举个overflow的例子吗 想半天没想明白， 这种1个char 1个char 读进来的情况 挺
符合用rh的啊。 先存第一个长度为10的string, 对新进来的chara, 去掉原string 头
， 加在最后 rehash. 你说的循环数组是类似思想吗？
【在 s********u 的大作中提到】
: rolling hash只要base取256即可，但好像会oveflow吧。不过我觉得的确是应该用循环
: 数组，因为你substr和pushback 恐怕都不是o1
符合用rh的啊。 先存第一个长度为10的string, 对新进来的chara, 去掉原string 头
， 加在最后 rehash. 你说的循环数组是类似思想吗？
【在 s********u 的大作中提到】
: rolling hash只要base取256即可，但好像会oveflow吧。不过我觉得的确是应该用循环
: 数组，因为你substr和pushback 恐怕都不是o1
l*n
27 楼
他说的的overflow是因为rolling hash是个多项式，每次roll的时候是lastHash*base+
newChar-firstChar*power(base, n)。overflow其实也无所谓的。rolling hash没有
rehash这一说。
这一题用rolling hash就只是在计算hash的时候节省一点，但还是需要像普通的hash
table那样处理collision，需要存所有unique字串。这么一来，感觉就需要自己搞一个
hashmap了，更麻烦。也许是我不知道有什么好办法能让rolling hash跟hashmap直接无
缝连接。
【在 J****3 的大作中提到】
: 能举个overflow的例子吗 想半天没想明白， 这种1个char 1个char 读进来的情况 挺
: 符合用rh的啊。 先存第一个长度为10的string, 对新进来的chara, 去掉原string 头
: ， 加在最后 rehash. 你说的循环数组是类似思想吗？
newChar-firstChar*power(base, n)。overflow其实也无所谓的。rolling hash没有
rehash这一说。
这一题用rolling hash就只是在计算hash的时候节省一点，但还是需要像普通的hash
table那样处理collision，需要存所有unique字串。这么一来，感觉就需要自己搞一个
hashmap了，更麻烦。也许是我不知道有什么好办法能让rolling hash跟hashmap直接无
缝连接。
【在 J****3 的大作中提到】
: 能举个overflow的例子吗 想半天没想明白， 这种1个char 1个char 读进来的情况 挺
: 符合用rh的啊。 先存第一个长度为10的string, 对新进来的chara, 去掉原string 头
: ， 加在最后 rehash. 你说的循环数组是类似思想吗？
J*3
28 楼
我以为每次算roll 那个方程的时候就是rehash。。
用roll出来的hash值重载下[] operator?
base+
【在 l*n 的大作中提到】
: 他说的的overflow是因为rolling hash是个多项式，每次roll的时候是lastHash*base+
: newChar-firstChar*power(base, n)。overflow其实也无所谓的。rolling hash没有
: rehash这一说。
: 这一题用rolling hash就只是在计算hash的时候节省一点，但还是需要像普通的hash
: table那样处理collision，需要存所有unique字串。这么一来，感觉就需要自己搞一个
: hashmap了，更麻烦。也许是我不知道有什么好办法能让rolling hash跟hashmap直接无
: 缝连接。
用roll出来的hash值重载下[] operator?
base+
【在 l*n 的大作中提到】
: 他说的的overflow是因为rolling hash是个多项式，每次roll的时候是lastHash*base+
: newChar-firstChar*power(base, n)。overflow其实也无所谓的。rolling hash没有
: rehash这一说。
: 这一题用rolling hash就只是在计算hash的时候节省一点，但还是需要像普通的hash
: table那样处理collision，需要存所有unique字串。这么一来，感觉就需要自己搞一个
: hashmap了，更麻烦。也许是我不知道有什么好办法能让rolling hash跟hashmap直接无
: 缝连接。
s*u
29 楼
如果是用256的底，没有collision，就像你一个数用十进制表示，只有唯一一种可能。
base+
【在 l*n 的大作中提到】
: 他说的的overflow是因为rolling hash是个多项式，每次roll的时候是lastHash*base+
: newChar-firstChar*power(base, n)。overflow其实也无所谓的。rolling hash没有
: rehash这一说。
: 这一题用rolling hash就只是在计算hash的时候节省一点，但还是需要像普通的hash
: table那样处理collision，需要存所有unique字串。这么一来，感觉就需要自己搞一个
: hashmap了，更麻烦。也许是我不知道有什么好办法能让rolling hash跟hashmap直接无
: 缝连接。
base+
【在 l*n 的大作中提到】
: 他说的的overflow是因为rolling hash是个多项式，每次roll的时候是lastHash*base+
: newChar-firstChar*power(base, n)。overflow其实也无所谓的。rolling hash没有
: rehash这一说。
: 这一题用rolling hash就只是在计算hash的时候节省一点，但还是需要像普通的hash
: table那样处理collision，需要存所有unique字串。这么一来，感觉就需要自己搞一个
: hashmap了，更麻烦。也许是我不知道有什么好办法能让rolling hash跟hashmap直接无
: 缝连接。
l*n
30 楼
不太明白。如果没有collision，那hashing的值域就跟定义域一样了，还需要hashing
作甚？
【在 s********u 的大作中提到】
: 如果是用256的底，没有collision，就像你一个数用十进制表示，只有唯一一种可能。
:
: base+
作甚？
【在 s********u 的大作中提到】
: 如果是用256的底，没有collision，就像你一个数用十进制表示，只有唯一一种可能。
:
: base+
m*4
31 楼
同觉得还是trie比较好。能否用trie＋circular array？ circular array只管记录，
两头插入删除都很方便, trie代替hash。不知道C＋＋如何，但我觉得java中的string
和StringBuilder都不efficient。
【在 l*n 的大作中提到】
: rolling hash有collision怎么办？最后你还是得存所有unique字串。想省空间还是得
: 上trie，插入即查询。
:
: unor
两头插入删除都很方便, trie代替hash。不知道C＋＋如何，但我觉得java中的string
和StringBuilder都不efficient。
【在 l*n 的大作中提到】
: rolling hash有collision怎么办？最后你还是得存所有unique字串。想省空间还是得
: 上trie，插入即查询。
:
: unor
m*4
32 楼
我是C＋＋盲，不知道这个CODE是不是有BUG：
１.你的read() return value是int，你可以直接转成char没有问题吗？
２.不知道unordered_set是啥，好象可以count。但你边读入边比较,这个count在到了
１以后就没有更新了吧，所以如果一个string出现了１０次，你要print 9次，这个对
吗？
【在 f********4 的大作中提到】
: 输入是个stream
: class input_stream
: {
: // Character or -1
: int read();
: }
: 每次call read（），返回一个char，如果到头了就是返回-1
: Find and print repeated sequences of 10 characters
: void find_repeated_sequences(input_stream in)
: {
１.你的read() return value是int，你可以直接转成char没有问题吗？
２.不知道unordered_set是啥，好象可以count。但你边读入边比较,这个count在到了
１以后就没有更新了吧，所以如果一个string出现了１０次，你要print 9次，这个对
吗？
【在 f********4 的大作中提到】
: 输入是个stream
: class input_stream
: {
: // Character or -1
: int read();
: }
: 每次call read（），返回一个char，如果到头了就是返回-1
: Find and print repeated sequences of 10 characters
: void find_repeated_sequences(input_stream in)
: {
f*4
33 楼
1。可以啊，这个和什么语言没有关吗。。ASCII的话都这样的吧。。
2。set就是hash—map啊，本来就不用更新啊，汗。出现十次说明9次是重复的啊，没有
问题的
[发表自未名空间手机版 - m.mitbbs.com]
【在 m**********4 的大作中提到】
: 我是C＋＋盲，不知道这个CODE是不是有BUG：
: １.你的read() return value是int，你可以直接转成char没有问题吗？
: ２.不知道unordered_set是啥，好象可以count。但你边读入边比较,这个count在到了
: １以后就没有更新了吧，所以如果一个string出现了１０次，你要print 9次，这个对
: 吗？
2。set就是hash—map啊，本来就不用更新啊，汗。出现十次说明9次是重复的啊，没有
问题的
[发表自未名空间手机版 - m.mitbbs.com]
【在 m**********4 的大作中提到】
: 我是C＋＋盲，不知道这个CODE是不是有BUG：
: １.你的read() return value是int，你可以直接转成char没有问题吗？
: ２.不知道unordered_set是啥，好象可以count。但你边读入边比较,这个count在到了
: １以后就没有更新了吧，所以如果一个string出现了１０次，你要print 9次，这个对
: 吗？
s*u
34 楼
关键是rolling hash可以做到增量的计算，string就不行了。而且你用一个unordered_
set去存，一个是存10字符的字符串，一个只是记一个long long，还是有优劣之分的
hashing
【在 l*n 的大作中提到】
: 不太明白。如果没有collision，那hashing的值域就跟定义域一样了，还需要hashing
: 作甚？
set去存，一个是存10字符的字符串，一个只是记一个long long，还是有优劣之分的
hashing
【在 l*n 的大作中提到】
: 不太明白。如果没有collision，那hashing的值域就跟定义域一样了，还需要hashing
: 作甚？
l*n
35 楼
好像明白你的意思，是在利用字符只有10这一点吗？只算小写字母有26个，每个需要5
个bit，10个数一共是50个bit，比64要小。这样long的取值能比10个小写字母的范围大
。但是一旦加入数字或者大写字母就还是会有collision了。
如果是你说的256为底，需要8个bit，直接对应10字符的话，需要一共80bit，超过long
的64了吧？longlong 是128bit么？那的确是一个longlong一个串了。
unordered_
【在 s********u 的大作中提到】
: 关键是rolling hash可以做到增量的计算，string就不行了。而且你用一个unordered_
: set去存，一个是存10字符的字符串，一个只是记一个long long，还是有优劣之分的
:
: hashing
个bit，10个数一共是50个bit，比64要小。这样long的取值能比10个小写字母的范围大
。但是一旦加入数字或者大写字母就还是会有collision了。
如果是你说的256为底，需要8个bit，直接对应10字符的话，需要一共80bit，超过long
的64了吧？longlong 是128bit么？那的确是一个longlong一个串了。
unordered_
【在 s********u 的大作中提到】
: 关键是rolling hash可以做到增量的计算，string就不行了。而且你用一个unordered_
: set去存，一个是存10字符的字符串，一个只是记一个long long，还是有优劣之分的
:
: hashing
m*4
36 楼
in java, if you do
int x = 5;
char c = x;
it won't compile... Not sure why you can do
char temp = in.read();
还有你能把－１赋给char？我试了下
char c = (char)-1;
System.out.println((int)c);
I get 65335.
【在 f********4 的大作中提到】
: 1。可以啊，这个和什么语言没有关吗。。ASCII的话都这样的吧。。
: 2。set就是hash—map啊，本来就不用更新啊，汗。出现十次说明9次是重复的啊，没有
: 问题的
:
: [发表自未名空间手机版 - m.mitbbs.com]
int x = 5;
char c = x;
it won't compile... Not sure why you can do
char temp = in.read();
还有你能把－１赋给char？我试了下
char c = (char)-1;
System.out.println((int)c);
I get 65335.
【在 f********4 的大作中提到】
: 1。可以啊，这个和什么语言没有关吗。。ASCII的话都这样的吧。。
: 2。set就是hash—map啊，本来就不用更新啊，汗。出现十次说明9次是重复的啊，没有
: 问题的
:
: [发表自未名空间手机版 - m.mitbbs.com]
f*4
37 楼
那个read函数，输出的本来就是字符啊。。就和97是‘a’一样
如果到头了才是－1
还有那个是typo。。应该是temp==－1
这些细枝末节的东西，非要在这里展示知道的很多，没有什么意思吧
【在 m**********4 的大作中提到】
: in java, if you do
: int x = 5;
: char c = x;
: it won't compile... Not sure why you can do
: char temp = in.read();
: 还有你能把－１赋给char？我试了下
: char c = (char)-1;
: System.out.println((int)c);
: I get 65335.
如果到头了才是－1
还有那个是typo。。应该是temp==－1
这些细枝末节的东西，非要在这里展示知道的很多，没有什么意思吧
【在 m**********4 的大作中提到】
: in java, if you do
: int x = 5;
: char c = x;
: it won't compile... Not sure why you can do
: char temp = in.read();
: 还有你能把－１赋给char？我试了下
: char c = (char)-1;
: System.out.println((int)c);
: I get 65335.
s*u
38 楼
long long是64，所以我前面说这个overflow很尴尬。正好差一些。
long是32吧一般。
5
long
【在 l*n 的大作中提到】
: 好像明白你的意思，是在利用字符只有10这一点吗？只算小写字母有26个，每个需要5
: 个bit，10个数一共是50个bit，比64要小。这样long的取值能比10个小写字母的范围大
: 。但是一旦加入数字或者大写字母就还是会有collision了。
: 如果是你说的256为底，需要8个bit，直接对应10字符的话，需要一共80bit，超过long
: 的64了吧？longlong 是128bit么？那的确是一个longlong一个串了。
:
: unordered_
long是32吧一般。
5
long
【在 l*n 的大作中提到】
: 好像明白你的意思，是在利用字符只有10这一点吗？只算小写字母有26个，每个需要5
: 个bit，10个数一共是50个bit，比64要小。这样long的取值能比10个小写字母的范围大
: 。但是一旦加入数字或者大写字母就还是会有collision了。
: 如果是你说的256为底，需要8个bit，直接对应10字符的话，需要一共80bit，超过long
: 的64了吧？longlong 是128bit么？那的确是一个longlong一个串了。
:
: unordered_
s*w
39 楼
只要你的 hash 足够好，collision 的几率很小的，和中彩票一样
hash 不够好，或者需要 double check 的话，多存一个 index
本来只需要存 hash code, 现在用 map/unordered_map 存 (hash code,ind); 发现有
collision 就一一对照一下
省空间，因为 存子串显然要很浪费, 你想假如现在要求算 1k 长的子串?
省时间，因为 你只需要对整数操作
说的够明白吧？
【在 l*n 的大作中提到】
: rolling hash有collision怎么办？最后你还是得存所有unique字串。想省空间还是得
: 上trie，插入即查询。
:
: unor
hash 不够好，或者需要 double check 的话，多存一个 index
本来只需要存 hash code, 现在用 map/unordered_map 存 (hash code,ind); 发现有
collision 就一一对照一下
省空间，因为 存子串显然要很浪费, 你想假如现在要求算 1k 长的子串?
省时间，因为 你只需要对整数操作
说的够明白吧？
【在 l*n 的大作中提到】
: rolling hash有collision怎么办？最后你还是得存所有unique字串。想省空间还是得
: 上trie，插入即查询。
:
: unor
l*n
40 楼
index就能表示字串了？stream读完了就没了，要index何用？
有
【在 s*w 的大作中提到】
: 只要你的 hash 足够好，collision 的几率很小的，和中彩票一样
: hash 不够好，或者需要 double check 的话，多存一个 index
: 本来只需要存 hash code, 现在用 map/unordered_map 存 (hash code,ind); 发现有
: collision 就一一对照一下
: 省空间，因为 存子串显然要很浪费, 你想假如现在要求算 1k 长的子串?
: 省时间，因为 你只需要对整数操作
: 说的够明白吧？
有
【在 s*w 的大作中提到】
: 只要你的 hash 足够好，collision 的几率很小的，和中彩票一样
: hash 不够好，或者需要 double check 的话，多存一个 index
: 本来只需要存 hash code, 现在用 map/unordered_map 存 (hash code,ind); 发现有
: collision 就一一对照一下
: 省空间，因为 存子串显然要很浪费, 你想假如现在要求算 1k 长的子串?
: 省时间，因为 你只需要对整数操作
: 说的够明白吧？
s*w
41 楼
没注意看题，居然是 stream, 那的确不能存 index 了，不过还是可以用 rolling
hash
还是那句话，你要相信概率；坐飞机掉下来的概率其实也不小，大家不还天天坐嘛
【在 l*n 的大作中提到】
: index就能表示字串了？stream读完了就没了，要index何用？
:
: 有
hash
还是那句话，你要相信概率；坐飞机掉下来的概率其实也不小，大家不还天天坐嘛
【在 l*n 的大作中提到】
: index就能表示字串了？stream读完了就没了，要index何用？
:
: 有
p*2
42 楼
这个circular array可以直接用ArrayDeque？
StringBuilder
【在 m**********4 的大作中提到】
: java中，strings immutable，最好不要append在string后面。所以要用StringBuilder
: ，但StringBuilder 的substring方法又不efficient。不知道他是不是想让你自己
: maintain一个能两头插入的data structure，circular array 啥的,
: 但问题是还得算hashcode，override
: equals，麻烦不说，也不可能提高效率很多啊。想不通为什么被废
StringBuilder
【在 m**********4 的大作中提到】
: java中，strings immutable，最好不要append在string后面。所以要用StringBuilder
: ，但StringBuilder 的substring方法又不efficient。不知道他是不是想让你自己
: maintain一个能两头插入的data structure，circular array 啥的,
: 但问题是还得算hashcode，override
: equals，麻烦不说，也不可能提高效率很多啊。想不通为什么被废
l*n
43 楼
good point, java arraydeque就是现成的circular array。
【在 p*******2 的大作中提到】
: 这个circular array可以直接用ArrayDeque？
:
: StringBuilder
【在 p*******2 的大作中提到】
: 这个circular array可以直接用ArrayDeque？
:
: StringBuilder
t*i
44 楼
abca, bcab, cabc 的话你这个程序就不work了吧。
set里面存了abca, count("bcab") 就是0了呀。
【在 f********4 的大作中提到】
: 是找另一个前面出现过的序列，也可以连续重复啊，只要重复就可以
: 算短一点，比如abcabcabcabc，比如说找长度为4
: abca,bcab,cabc都是啊
set里面存了abca, count("bcab") 就是0了呀。
【在 f********4 的大作中提到】
: 是找另一个前面出现过的序列，也可以连续重复啊，只要重复就可以
: 算短一点，比如abcabcabcabc，比如说找长度为4
: abca,bcab,cabc都是啊
d*g
45 楼
我amazon做个跟这个差不多的,如果读到-1的时候你一样把它传给char,这样是不行的,,
,,,
会爆掉,,
你觉得呢
,,,
会爆掉,,
你觉得呢
w*a
46 楼
不是只有4个字母么？ATGC。
那10个字符可能性就一百多万个啊。一个int就能搞定，也没有碰撞的担忧。
或者干脆用20个bit来存10个字符，每走一个，就往左边shift两位，然后或一下新拿到
的字符。
写了一下：
void find_repeated_sequences(const input_stream& in) {
static map table = {{'A', 0},{'T', 1},{'G', 2},{'C', 3}};
int cur_code = 0;
const int STR_SIZE = 10;
auto print_code = [](int code) {
static char inv_table[4] = {'A','T','G','C'};
for(int i = 0; i < STR_SIZE; ++i) {
cout << inv_table[code & 0x3];
code >>= 2;
}
cout << endl;
};
for(int i = 0; i < STR_SIZE; ++i) {
char c = in.read();
if(c == -1) return;
cur_code |= table[c] << i*2;
}
unordered_map counter = {{cur_code, 1}};
while(true) {
char c = in.read();
if(c == -1) break;
cur_code = (cur_code >> 2) | (table[c] << (STR_SIZE-1)*2);
++counter[cur_code];
}
for(auto &p : counter) {
if(p.second > 1) print_code(p.first);
}
}
那10个字符可能性就一百多万个啊。一个int就能搞定，也没有碰撞的担忧。
或者干脆用20个bit来存10个字符，每走一个，就往左边shift两位，然后或一下新拿到
的字符。
写了一下：
void find_repeated_sequences(const input_stream& in) {
static map
int cur_code = 0;
const int STR_SIZE = 10;
auto print_code = [](int code) {
static char inv_table[4] = {'A','T','G','C'};
for(int i = 0; i < STR_SIZE; ++i) {
cout << inv_table[code & 0x3];
code >>= 2;
}
cout << endl;
};
for(int i = 0; i < STR_SIZE; ++i) {
char c = in.read();
if(c == -1) return;
cur_code |= table[c] << i*2;
}
unordered_map
while(true) {
char c = in.read();
if(c == -1) break;
cur_code = (cur_code >> 2) | (table[c] << (STR_SIZE-1)*2);
++counter[cur_code];
}
for(auto &p : counter) {
if(p.second > 1) print_code(p.first);
}
}
t*e
47 楼
c++没看懂，能就你的思路举个例子么？
【在 w****a 的大作中提到】
: 不是只有4个字母么？ATGC。
: 那10个字符可能性就一百多万个啊。一个int就能搞定，也没有碰撞的担忧。
: 或者干脆用20个bit来存10个字符，每走一个，就往左边shift两位，然后或一下新拿到
: 的字符。
: 写了一下：
: void find_repeated_sequences(const input_stream& in) {
: static map table = {{'A', 0},{'T', 1},{'G', 2},{'C', 3}};
:
: int cur_code = 0;
: const int STR_SIZE = 10;
【在 w****a 的大作中提到】
: 不是只有4个字母么？ATGC。
: 那10个字符可能性就一百多万个啊。一个int就能搞定，也没有碰撞的担忧。
: 或者干脆用20个bit来存10个字符，每走一个，就往左边shift两位，然后或一下新拿到
: 的字符。
: 写了一下：
: void find_repeated_sequences(const input_stream& in) {
: static map
:
: int cur_code = 0;
: const int STR_SIZE = 10;
相关阅读
G家relocation都不管卖房子的closing cost吗？问一道leetcode题：recover BST奇怪的G家offer，请版上大牛们帮忙Hot startup coding test 的问题求一个AMAZON AWS 内推Qualcomm: Hire verification engineer (temp/contractor) (转载)Google电面多久会出结果？现在Twitter期望offer有多少？招人需要做一些什么样的背景调查？H1B & E-verifyLinkedin 面试好消息！Amazon 要招两千人！如何调研startup敢不敢去，帮忙看看sojern？跪求radiumone 面经opt 也有check啊Amazon的电面都是口述吗？请推荐电面用的headset如果新工作工资比原来少很多transfer H1-b会不会有问题？M 家真的不招人了么。。。PhD第三年了，到底是该自学CS还是重新申CS master?