f********4
发帖数: 988 | 1 输入是个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的。。不过后来想了一下，也没想出更好的
大家看看咋写更好 |
a********9
发帖数: 129 | 2 我也是这么做的，国人大哥，所以过了。。。 还有更好的方法么？这个已经是O(n)了
啊 |
f********4
发帖数: 988 | 3 。。。。
fb二面碰见国人挂了
L一面碰见红毛又挂了。。
我真的很想去CA旅游啊。。。让我过一次吧。。
【在 a********9 的大作中提到】
: 我也是这么做的，国人大哥，所以过了。。。 还有更好的方法么？这个已经是O(n)了
: 啊
|
n****e
发帖数: 678 | 4 试着写一写：
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)
: {
|
w********s
发帖数: 214 | 5 这个题目用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)
|
m********c
发帖数: 105 | 6 这个repeated sequences of 10 characters怎么理解？是说找出input_stream里，长
度为10的，重复出现的的吗？ |
z*****5
发帖数: 38 | |
m**********4
发帖数: 774 | 8 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)
: {
|
l*n
发帖数: 529 | 9 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)
: {
|
f********4
发帖数: 988 | 10 是找另一个前面出现过的序列，也可以连续重复啊，只要重复就可以
算短一点，比如abcabcabcabc，比如说找长度为4
abca,bcab,cabc都是啊
【在 l*n 的大作中提到】
: repeated sequence of 10 characters，是找另一个abcdefghij？
: 也算abcabcabcabcabcabc...这种连续重复的？string是要unique的还是所有的？问题
: 多多啊。
|
|
|
f********4
发帖数: 988 | 11 嗯，一开始我也提了，面试官也没答腔。我就说那我先写个work的吧
StringBuilder
【在 m**********4 的大作中提到】
: java中，strings immutable，最好不要append在string后面。所以要用StringBuilder
: ，但StringBuilder 的substring方法又不efficient。不知道他是不是想让你自己
: maintain一个能两头插入的data structure，circular array 啥的,
: 但问题是还得算hashcode，override
: equals，麻烦不说，也不可能提高效率很多啊。想不通为什么被废
|
s*w
发帖数: 729 | 12 无脑 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)
: {
|
l*n
发帖数: 529 | 13 rolling hash有collision怎么办？最后你还是得存所有unique字串。想省空间还是得
上trie，插入即查询。
unor
【在 s*w 的大作中提到】
: 无脑 rolling hash，对付这种定长的字串专用
: 从头扫到尾，对当前长度10的子串算一个 hash code, 结果查询以前(set, 或者 unor
: dered_set)存起来的 hash code，重复的话，就输出当前的子串
: 比直接存所有的unique子串要省时间省空间
|
s********u
发帖数: 1109 | 14 rolling hash只要base取256即可，但好像会oveflow吧。不过我觉得的确是应该用循环
数组，因为你substr和pushback 恐怕都不是o1 |
f********4
发帖数: 988 | 15 哦，我去看看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
|
J****3
发帖数: 427 | 16 能举个overflow的例子吗 想半天没想明白， 这种1个char 1个char 读进来的情况 挺
符合用rh的啊。 先存第一个长度为10的string, 对新进来的chara, 去掉原string 头
， 加在最后 rehash. 你说的循环数组是类似思想吗？
【在 s********u 的大作中提到】
: rolling hash只要base取256即可，但好像会oveflow吧。不过我觉得的确是应该用循环
: 数组，因为你substr和pushback 恐怕都不是o1
|
l*n
发帖数: 529 | 17 他说的的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. 你说的循环数组是类似思想吗？
|
J****3
发帖数: 427 | 18 我以为每次算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直接无
: 缝连接。
|
s********u
发帖数: 1109 | 19 如果是用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直接无
: 缝连接。
|
l*n
发帖数: 529 | 20 不太明白。如果没有collision，那hashing的值域就跟定义域一样了，还需要hashing
作甚？
【在 s********u 的大作中提到】
: 如果是用256的底，没有collision，就像你一个数用十进制表示，只有唯一一种可能。
:
: base+
|
|
|
m**********4
发帖数: 774 | 21 同觉得还是trie比较好。能否用trie＋circular array？ circular array只管记录，
两头插入删除都很方便, trie代替hash。不知道C＋＋如何，但我觉得java中的string
和StringBuilder都不efficient。
【在 l*n 的大作中提到】
: rolling hash有collision怎么办？最后你还是得存所有unique字串。想省空间还是得
: 上trie，插入即查询。
:
: unor
|
m**********4
发帖数: 774 | 22 我是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)
: {
|
f********4
发帖数: 988 | 23 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次，这个对
: 吗？
|
s********u
发帖数: 1109 | 24 关键是rolling hash可以做到增量的计算，string就不行了。而且你用一个unordered_
set去存，一个是存10字符的字符串，一个只是记一个long long，还是有优劣之分的
hashing
【在 l*n 的大作中提到】
: 不太明白。如果没有collision，那hashing的值域就跟定义域一样了，还需要hashing
: 作甚？
|
l*n
发帖数: 529 | 25 好像明白你的意思，是在利用字符只有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
|
m**********4
发帖数: 774 | 26 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]
|
f********4
发帖数: 988 | 27 那个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.
|
s********u
发帖数: 1109 | 28 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_
|
s*w
发帖数: 729 | 29 只要你的 hash 足够好，collision 的几率很小的，和中彩票一样
hash 不够好，或者需要 double check 的话，多存一个 index
本来只需要存 hash code, 现在用 map/unordered_map 存 (hash code,ind); 发现有
collision 就一一对照一下
省空间，因为 存子串显然要很浪费, 你想假如现在要求算 1k 长的子串?
省时间，因为 你只需要对整数操作
说的够明白吧？
【在 l*n 的大作中提到】
: rolling hash有collision怎么办？最后你还是得存所有unique字串。想省空间还是得
: 上trie，插入即查询。
:
: unor
|
l*n
发帖数: 529 | 30 index就能表示字串了？stream读完了就没了，要index何用？
有
【在 s*w 的大作中提到】
: 只要你的 hash 足够好，collision 的几率很小的，和中彩票一样
: hash 不够好，或者需要 double check 的话，多存一个 index
: 本来只需要存 hash code, 现在用 map/unordered_map 存 (hash code,ind); 发现有
: collision 就一一对照一下
: 省空间，因为 存子串显然要很浪费, 你想假如现在要求算 1k 长的子串?
: 省时间，因为 你只需要对整数操作
: 说的够明白吧？
|
|
|
s*w
发帖数: 729 | 31 没注意看题，居然是 stream, 那的确不能存 index 了，不过还是可以用 rolling
hash
还是那句话，你要相信概率；坐飞机掉下来的概率其实也不小，大家不还天天坐嘛
【在 l*n 的大作中提到】
: index就能表示字串了？stream读完了就没了，要index何用？
:
: 有
|
p*******2
发帖数: 50 | 32 这个circular array可以直接用ArrayDeque？
StringBuilder
【在 m**********4 的大作中提到】
: java中，strings immutable，最好不要append在string后面。所以要用StringBuilder
: ，但StringBuilder 的substring方法又不efficient。不知道他是不是想让你自己
: maintain一个能两头插入的data structure，circular array 啥的,
: 但问题是还得算hashcode，override
: equals，麻烦不说，也不可能提高效率很多啊。想不通为什么被废
|
l*n
发帖数: 529 | 33 good point, java arraydeque就是现成的circular array。
【在 p*******2 的大作中提到】
: 这个circular array可以直接用ArrayDeque？
:
: StringBuilder
|
t******i
发帖数: 483 | 34 abca, bcab, cabc 的话你这个程序就不work了吧。
set里面存了abca, count("bcab") 就是0了呀。
【在 f********4 的大作中提到】
: 是找另一个前面出现过的序列，也可以连续重复啊，只要重复就可以
: 算短一点，比如abcabcabcabc，比如说找长度为4
: abca,bcab,cabc都是啊
|
d******g
发帖数: 42 | 35 我amazon做个跟这个差不多的,如果读到-1的时候你一样把它传给char,这样是不行的,,
,,,
会爆掉,,
你觉得呢 |
w****a
发帖数: 710 | 36 不是只有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);
}
} |
t*******e
发帖数: 274 | 37 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;
|
