S***w
发帖数: 1014 | 1 前面30分钟抓着问了我过去的经历，
做了一个小题目。
然后扔出这个大题 要求O(n)
且输出排序
我先用suffix array, 说不好
然后用hashmap, o(n), 但是输出不排行
恶心的地方，
输入不是string,是流
输出要排序
O(N)
最可气的是 找不到他想要的算法 不让写代码，
最后5分钟,找到他想要的答案，来不及了
好苦啊 为啥大家店面就那几道题，给我这么难的一个
This problem pertains to the field of bioinformatics, but it does not
require any specialized biological knowledge. All DNA is composed of
sequences of four "letters" of nucleotides, whose abbreviations are A, C, G,
and T, strung together, for example: "AAGATCCGTC". A typical chromosome (a
very long DNA molecule) may have several millions of these letters strung
together. When studying DNA, it is sometimes useful to know when a
particular sequence of letters is repeated.
For this problem, we would like to identify all the 10-letter-long
sequences that occur more than once in any given chromosome. Write a
program that prints out all such sequences to the standard output stream,
sorted in alphabetical order. Start with this code:
*/
/*
SIMPLE EXAMPLE
Question: (simplified version of the problem) Find all 2 letter sequences
that appear more than once and print them out in sorted order.
Input: 'AAGATCCGTCAGTTTTCAAT'
Output: 'AA', 'AG', 'AT', 'CA', 'GT', 'TC', 'TT' |
M**********7
发帖数: 378 | 2 Pat pat
拼命问过去是有黑的嫌疑 耽误30分钟挺坏的
就题来说输出最多16个 重排算o1
或者用堆或者bst
在 Solow (Solow) 的大作中提到: 】 |
S***w
发帖数: 1014 | 3 人要O(n)
不是o(n) 不让写代码
【在 M**********7 的大作中提到】
: Pat pat
: 拼命问过去是有黑的嫌疑 耽误30分钟挺坏的
: 就题来说输出最多16个 重排算o1
: 或者用堆或者bst
: 在 Solow (Solow) 的大作中提到: 】
|
s*****n
发帖数: 102 | 4 我擦啊，我也准备电面L家呢，看了LZ的经历，好吓人啊~~~
烙印怎么那么黑啊？ |
s*******m
发帖数: 228 | |
m*****n
发帖数: 2152 | 6 hash + radix。
烙印太tm的黑了。
【在 S***w 的大作中提到】
: 前面30分钟抓着问了我过去的经历，
: 做了一个小题目。
: 然后扔出这个大题 要求O(n)
: 且输出排序
: 我先用suffix array, 说不好
: 然后用hashmap, o(n), 但是输出不排行
: 恶心的地方，
: 输入不是string,是流
: 输出要排序
: O(N)
|
S***w
发帖数: 1014 | 7 好呢
这题目老复杂了， 30分钟写完真是大牛
这是我给他的O(N)打印所有repease substring len=10
Set set = new HashSet;
for(int i = 0; i <= s.length() - 10, ++i) {
String sub = s.substring(i, i + 10);
if (set.cotains(sub)) {
print
}
set.add(sub)
}
这样打印的结果不是排序的.
tricky的地方要，把
A -> 0
C -> 1
G -> 2
T -> 3
ACGT => 123
CGTA => 1230
把string转成int,
int[] marked = new int[4 ** 10];
set.cotains(sub)
set.add(sub)
=>
int = convert(sub)
marked(int) > 0
++marked[int]
=>
最后再 0 -> 4 ** 10,
if visited[int] > 1:
把数字转为字符串,
// 1230 => CGTA
// 123 => ACGT
打印出来
【在 s*******m 的大作中提到】
: 请问楼主，这题，他想要什么算法。
: 详细讲讲吧。
|
S***w
发帖数: 1014 | 8 就是 恨死了
【在 m*****n 的大作中提到】
: hash + radix。
: 烙印太tm的黑了。
|
e********2
发帖数: 495 | 9 4叉树，插入常时间，就是空间可能有点大。Bitmap之类的各有利弊。
【在 s*******m 的大作中提到】
: 请问楼主，这题，他想要什么算法。
: 详细讲讲吧。
|
y*****e
发帖数: 712 | 10 这题没见过的话很难30分钟做出来吧。就是做过leetcode那题，还得再写一个radix
sort!!! |
|
|
h*********o
发帖数: 26 | 11 我觉得可以用4x4的array记录frequency
(0,0) = AA
(0,1) = AC
(0,2) = AG
(0,3) = AT
(1,0) = CA
(1,1) = CC
。。。
(3,3) = TT
最後扫一次array就出答案 |
S***w
发帖数: 1014 | 12 所以 我很郁闷
【在 y*****e 的大作中提到】
: 这题没见过的话很难30分钟做出来吧。就是做过leetcode那题，还得再写一个radix
: sort!!!
|
D***n
发帖数: 149 | 13 Good idea indeed !
【在 h*********o 的大作中提到】
: 我觉得可以用4x4的array记录frequency
: (0,0) = AA
: (0,1) = AC
: (0,2) = AG
: (0,3) = AT
: (1,0) = CA
: (1,1) = CC
: 。。。
: (3,3) = TT
: 最後扫一次array就出答案
|
f****9
发帖数: 506 | 14 我也是这样被黑的。不过面试的是个越南人。
就是不让你写code，一拖就是30分钟。。。
【在 S***w 的大作中提到】
: 前面30分钟抓着问了我过去的经历，
: 做了一个小题目。
: 然后扔出这个大题 要求O(n)
: 且输出排序
: 我先用suffix array, 说不好
: 然后用hashmap, o(n), 但是输出不排行
: 恶心的地方，
: 输入不是string,是流
: 输出要排序
: O(N)
|
d******a
发帖数: 238 | 15 一年半前被老印以同样的题黑过。老印是中国人在it届的最大敌人。 |
f*******t
发帖数: 7549 | |
S***w
发帖数: 1014 | 17 Lol
【在 d******a 的大作中提到】
: 一年半前被老印以同样的题黑过。老印是中国人在it届的最大敌人。
|
S***w
发帖数: 1014 | 18 已经投诉了
估计没啥用
【在 f*******t 的大作中提到】
: 向HR投诉，就说30分钟后才让写题
|
f*******t
发帖数: 7549 | 19 一个人投诉没用，大家都投诉就有用了
【在 S***w 的大作中提到】
: 已经投诉了
: 估计没啥用
|
M**********7
发帖数: 378 | 20 哦 排序是按字典排 还以为是按重复数排
是很复杂 尤其是前面30分钟其实黑的挺明显的
是该投诉
【在 S***w 的大作中提到】
: 好呢
: 这题目老复杂了， 30分钟写完真是大牛
: 这是我给他的O(N)打印所有repease substring len=10
: Set set = new HashSet;
: for(int i = 0; i <= s.length() - 10, ++i) {
: String sub = s.substring(i, i + 10);
: if (set.cotains(sub)) {
: print
: }
: set.add(sub)
|
|
|
S***w
发帖数: 1014 | 21 按字典排序
【在 M**********7 的大作中提到】
: 哦 排序是按字典排 还以为是按重复数排
: 是很复杂 尤其是前面30分钟其实黑的挺明显的
: 是该投诉
|
s*******m
发帖数: 228 | 22 谢谢
今天刚面完电面一
【在 S***w 的大作中提到】
: 好呢
: 这题目老复杂了， 30分钟写完真是大牛
: 这是我给他的O(N)打印所有repease substring len=10
: Set set = new HashSet;
: for(int i = 0; i <= s.length() - 10, ++i) {
: String sub = s.substring(i, i + 10);
: if (set.cotains(sub)) {
: print
: }
: set.add(sub)
|
S***w
发帖数: 1014 | 23 一样题目？
【在 s*******m 的大作中提到】
: 谢谢
: 今天刚面完电面一
|
S***w
发帖数: 1014 | 24 更新一下
投诉了烙印，HR打电话，明天聊聊
【在 S***w 的大作中提到】
: 前面30分钟抓着问了我过去的经历，
: 做了一个小题目。
: 然后扔出这个大题 要求O(n)
: 且输出排序
: 我先用suffix array, 说不好
: 然后用hashmap, o(n), 但是输出不排行
: 恶心的地方，
: 输入不是string,是流
: 输出要排序
: O(N)
|
l********0
发帖数: 169 | 25 我遇到过类似的，不到最优不让我写，也是烙印
人要O(n)不是o(n) 不让写代码
【在 S***w 的大作中提到】
: 更新一下
: 投诉了烙印，HR打电话，明天聊聊
|
S*******C
发帖数: 822 | 26 这题到底怎么做？
下面解法对吗？
https://gitorious.org/interview/interview/commit/
59feda9ebfd68419a3ed842533a81a8acfa2e59a |
S*******C
发帖数: 822 | 27 用rolling hash算法对吗?但怎么得到排序的结果呢？ |
S*******C
发帖数: 822 | 28 知道了，用rolling hash + 长度为4^10的array记录所有出现的10-char
sequence，然后从这个array中从小到大取出所有10-char repeated sequences，这样
根本不需要排序 |
S***w
发帖数: 1014 | 29 对的
是这样
问题是这题 就是事先知道算法 30分钟写完也很难啊
他给的是stream,求rollinh 也很tricky
【在 S*******C 的大作中提到】
: 知道了，用rolling hash + 长度为4^10的array记录所有出现的10-char
: sequence，然后从这个array中从小到大取出所有10-char repeated sequences，这样
: 根本不需要排序
|
S*******C
发帖数: 822 | 30 第一次做一次性无bug写出来几乎不可能，大家都是练过才有可能现场解出这样的题目
【在 S***w 的大作中提到】
: 对的
: 是这样
: 问题是这题 就是事先知道算法 30分钟写完也很难啊
: 他给的是stream,求rollinh 也很tricky
|
|
|
y*****e
发帖数: 712 | 31 不太明白这个
“长度为4^10的array记录所有出现的10-char sequence，然后从这个array中从小到大
取出所有10-char repeated sequences，不需要排序”
请问到底是怎么实现不用排序的？
【在 S*******C 的大作中提到】
: 知道了，用rolling hash + 长度为4^10的array记录所有出现的10-char
: sequence，然后从这个array中从小到大取出所有10-char repeated sequences，这样
: 根本不需要排序
|
h********3
发帖数: 2075 | 32 没错，这才是最优的答案。题目里面已经有好多地方都在提示这trick。suffix array
和hashmap的解法都没有抓到这最关键的一点。
【在 h*********o 的大作中提到】
: 我觉得可以用4x4的array记录frequency
: (0,0) = AA
: (0,1) = AC
: (0,2) = AG
: (0,3) = AT
: (1,0) = CA
: (1,1) = CC
: 。。。
: (3,3) = TT
: 最後扫一次array就出答案
|
h********3
发帖数: 2075 | 33 这种问题很简单。你写不出最优的解法，跟没写都一样，都是挂掉。而且code一写几十
分钟就过去了，没时间挽回败局了。面试官明知道你在错误的方向上使劲跑，难道还不
拦住你？
【在 l********0 的大作中提到】
: 我遇到过类似的，不到最优不让我写，也是烙印
:
: 人要O(n)不是o(n) 不让写代码
|
S*******C
发帖数: 822 | 34 4种碱基组成的DNA序列相当于是base 为4的数
长度为10的sequence就是长度为10的数，一共有4^10个这样的不同的数
创建长度为4^10的array就可以记录所有可能的10-char sequence是否出现过
最后从小到大遍历一遍这样的array就可以从小到大打印出所有重复出现的10-char
sequence，这样花费4^10的内存空间不需要排序输出结果
【在 y*****e 的大作中提到】
: 不太明白这个
: “长度为4^10的array记录所有出现的10-char sequence，然后从这个array中从小到大
: 取出所有10-char repeated sequences，不需要排序”
: 请问到底是怎么实现不用排序的？
|
y*****e
发帖数: 712 | 35 天这个花的内存太大了吧。。。为啥不能用radix sort？也是扫一遍出结果。。。
【在 S*******C 的大作中提到】
: 4种碱基组成的DNA序列相当于是base 为4的数
: 长度为10的sequence就是长度为10的数，一共有4^10个这样的不同的数
: 创建长度为4^10的array就可以记录所有可能的10-char sequence是否出现过
: 最后从小到大遍历一遍这样的array就可以从小到大打印出所有重复出现的10-char
: sequence，这样花费4^10的内存空间不需要排序输出结果
|
y*****e
发帖数: 712 | 36 lz支持你，明天回来更新，记得投诉时不要使用情绪话的字眼，尽量客观冷静的描述事
实，争取hr的好感和同情，争取重新安排面试
【在 S***w 的大作中提到】
: 更新一下
: 投诉了烙印，HR打电话，明天聊聊
|
S*******C
发帖数: 822 | 37 这题你怎么用radix sort?
【在 y*****e 的大作中提到】
: 天这个花的内存太大了吧。。。为啥不能用radix sort？也是扫一遍出结果。。。
|
S*******C
发帖数: 822 | 38 CC 150中第10.3题用的内存空间是2^32个bits
我才用4^10 = 2^20个bits，才是人家的1/2^12
【在 y*****e 的大作中提到】
: 天这个花的内存太大了吧。。。为啥不能用radix sort？也是扫一遍出结果。。。
|
C****t
发帖数: 53 | 39 A python version:
def num(maps, s): ######## transform string to 4-based number
digit = 0
for i in range(len(s)):
digit = 4*digit + maps[s[i]]
return digit
def findRepeat(s):
maps = {'A':0, 'C':1,'G':2,'T':3}
bitmap = [0]*pow(4,2)
for i in range(len(s) - 2+1):
bitmap[ num[maps, s[i:i+2] ] += 1
invmaps = {v:k for k,v in maps.items()} ####### reverse maps
for i in range(len(bitmap)):
if bitmap[i] > 1:
print (invmaps[i//4] + invmaps[i%4]) |
e******1
发帖数: 7 | 40 This is actually a straightforward question. Use a hashmap to keep all the
10-letter-long sequences and the count. At the end, save all items that has
count > 1 in a list and sort the list.
Sorting the list takes constant time because there can only be up to 1
million (4^10) items in the list.
The overall complexity is O(n) |
|
|
x*******9
发帖数: 138 | 41 同情LZ遭遇，不过这题不算难的说。。。=。=。。。
随手写一下，缩进不太好看，直接在回复框里打的。
（又看了一下题，这个是2碱基的简单版本，10碱基的版本类似。）
// 约定：
// A -> 0, T -> 1, C -> 2, G -> 3
// AT -> (A << 2) + (T << 0) -> 1
// CG -> (C << 2) + (G << 0) -> 11
// vise versa. :)
class Solution {
public:
int solve(const NucFlow& nuc_flow) {
_mp.clear();
char pre = '\0';
while (nuc_flow.has_next()) {
if (!pre) {
pre = nuc_flow.next();
continue;
}
char now = nuc_flow().next();
int u = nuc_to_num(pre, now); // e.g. AT -> (0, 1) -> 1
_mp[u]++;
pre = now;
}
show_ans();
return 0;
}
private:
void show_ans() {
for (int i = 0; i < 16; i++) {
int cnt = _mp[i];
if (cnt < 2) {
continue;
}
string nuc_tuple = num_to_nuc(i);
printf("%s -> %d\n", nuc_tuple.c_str(), cnt);
}
private:
unordered_map _mp;
}; |
o**********e
发帖数: 18403 | 42 赞！问题本质。
烙印反白眼，打断您说话，
冷嘲热讽，语带轻蔑，晚到
早走，把您的信息传给印度
BUDDY（有损您的PRIVACY）。
这些都是可以投诉的。
有理有据，一剑封喉。
您要是拿不到机会，想搞大，
很多人都会支持您的。 祝好！ |
f********a
发帖数: 367 | 43 in order, doesn't mean in lexical order.
here, in order means in the order of appearance from the input
rolling hash
has
【在 e******1 的大作中提到】
: This is actually a straightforward question. Use a hashmap to keep all the
: 10-letter-long sequences and the count. At the end, save all items that has
: count > 1 in a list and sort the list.
: Sorting the list takes constant time because there can only be up to 1
: million (4^10) items in the list.
: The overall complexity is O(n)
|
n******n
发帖数: 12088 | 44 这不是高频题吗？
【在 S***w 的大作中提到】
: 前面30分钟抓着问了我过去的经历，
: 做了一个小题目。
: 然后扔出这个大题 要求O(n)
: 且输出排序
: 我先用suffix array, 说不好
: 然后用hashmap, o(n), 但是输出不排行
: 恶心的地方，
: 输入不是string,是流
: 输出要排序
: O(N)
|
n******n
发帖数: 12088 | 45 问经历多久？小题是什么？用了多少时间？答案对吗？
【在 S***w 的大作中提到】
: 前面30分钟抓着问了我过去的经历，
: 做了一个小题目。
: 然后扔出这个大题 要求O(n)
: 且输出排序
: 我先用suffix array, 说不好
: 然后用hashmap, o(n), 但是输出不排行
: 恶心的地方，
: 输入不是string,是流
: 输出要排序
: O(N)
|
S***w
发帖数: 1014 | 46 input stream not string
【在 C****t 的大作中提到】
: A python version:
: def num(maps, s): ######## transform string to 4-based number
: digit = 0
: for i in range(len(s)):
: digit = 4*digit + maps[s[i]]
: return digit
: def findRepeat(s):
: maps = {'A':0, 'C':1,'G':2,'T':3}
: bitmap = [0]*pow(4,2)
: for i in range(len(s) - 2+1):
|
S***w
发帖数: 1014 | 47 差不多这样吧
不过以前没看过这题目
【在 x*******9 的大作中提到】
: 同情LZ遭遇，不过这题不算难的说。。。=。=。。。
: 随手写一下，缩进不太好看，直接在回复框里打的。
: （又看了一下题，这个是2碱基的简单版本，10碱基的版本类似。）
: // 约定：
: // A -> 0, T -> 1, C -> 2, G -> 3
: // AT -> (A << 2) + (T << 0) -> 1
: // CG -> (C << 2) + (G << 0) -> 11
: // vise versa. :)
: class Solution {
: public:
|
s*******m
发帖数: 228 | 48 经典的nestedinteger
【在 S***w 的大作中提到】
: 一样题目？
|
s*******m
发帖数: 228 | 49 按楼主讲的方法，
A-> 0
C->1
G->2
T->3
因为子串长度是10，开一个4的10次方的数组。
把子串转化成数字，作为数组的index.
如果出现过，该数组的值加1.
最后遍历这个数组就可以了吧，应该是排好序的。
【在 m*****n 的大作中提到】
: hash + radix。
: 烙印太tm的黑了。
|
s*******m
发帖数: 228 | 50 烙印要求的子串长度是10
【在 h*********o 的大作中提到】
: 我觉得可以用4x4的array记录frequency
: (0,0) = AA
: (0,1) = AC
: (0,2) = AG
: (0,3) = AT
: (1,0) = CA
: (1,1) = CC
: 。。。
: (3,3) = TT
: 最後扫一次array就出答案
|
|
|
w****a
发帖数: 710 | |
a*****2
发帖数: 96 | 52 这不是leetcode的原题吗？
public class Solution {
public List findRepeatedDnaSequences(String s) {
List result=new ArrayList();
HashMap computed=new HashMap();
for(int i=0;i<=s.length()-10;i++)
{
String sub=s.substring(i,i+10);
int key=getKey(sub);
if(computed.containsKey(key))
{
computed.put(key,computed.get(key)+1);
if(computed.get(key)==2)
result.add(sub);
}
else
computed.put(key,1);
}
return result;
}
public int getKey(String s)
{
int result=0;
for(int i= 0 ; i < s.length(); i++)
{
int b=0;
switch(s.charAt(i))
{
case 'A':
b|=0;
break;
case 'C':
b|=1;
break;
case 'G':
b|=2;
break;
case 'T':
b|=3;
break;
}
result=b|result;
result=result<<2;
}
return result;
}
} |
m****v
发帖数: 88 | |
S***w
发帖数: 1014 | 54 前面30分钟抓着问了我过去的经历，
做了一个小题目。
然后扔出这个大题 要求O(n)
且输出排序
我先用suffix array, 说不好
然后用hashmap, o(n), 但是输出不排行
恶心的地方，
输入不是string,是流
输出要排序
O(N)
最可气的是 找不到他想要的算法 不让写代码，
最后5分钟,找到他想要的答案，来不及了
好苦啊 为啥大家店面就那几道题，给我这么难的一个
This problem pertains to the field of bioinformatics, but it does not
require any specialized biological knowledge. All DNA is composed of
sequences of four "letters" of nucleotides, whose abbreviations are A, C, G,
and T, strung together, for example: "AAGATCCGTC". A typical chromosome (a
very long DNA molecule) may have several millions of these letters strung
together. When studying DNA, it is sometimes useful to know when a
particular sequence of letters is repeated.
For this problem, we would like to identify all the 10-letter-long
sequences that occur more than once in any given chromosome. Write a
program that prints out all such sequences to the standard output stream,
sorted in alphabetical order. Start with this code:
*/
/*
SIMPLE EXAMPLE
Question: (simplified version of the problem) Find all 2 letter sequences
that appear more than once and print them out in sorted order.
Input: 'AAGATCCGTCAGTTTTCAAT'
Output: 'AA', 'AG', 'AT', 'CA', 'GT', 'TC', 'TT' |
M**********7
发帖数: 378 | 55 Pat pat
拼命问过去是有黑的嫌疑 耽误30分钟挺坏的
就题来说输出最多16个 重排算o1
或者用堆或者bst
在 Solow (Solow) 的大作中提到: 】 |
S***w
发帖数: 1014 | 56 人要O(n)
不是o(n) 不让写代码
【在 M**********7 的大作中提到】
: Pat pat
: 拼命问过去是有黑的嫌疑 耽误30分钟挺坏的
: 就题来说输出最多16个 重排算o1
: 或者用堆或者bst
: 在 Solow (Solow) 的大作中提到: 】
|
s*****n
发帖数: 102 | 57 我擦啊，我也准备电面L家呢，看了LZ的经历，好吓人啊~~~
烙印怎么那么黑啊？ |
s*******m
发帖数: 228 | 58 请问楼主，这题，他想要什么算法。
详细讲讲吧。 |
m*****n
发帖数: 2152 | 59 hash + radix。
烙印太tm的黑了。
【在 S***w 的大作中提到】
: 前面30分钟抓着问了我过去的经历，
: 做了一个小题目。
: 然后扔出这个大题 要求O(n)
: 且输出排序
: 我先用suffix array, 说不好
: 然后用hashmap, o(n), 但是输出不排行
: 恶心的地方，
: 输入不是string,是流
: 输出要排序
: O(N)
|
S***w
发帖数: 1014 | 60 好呢
这题目老复杂了， 30分钟写完真是大牛
这是我给他的O(N)打印所有repease substring len=10
Set set = new HashSet;
for(int i = 0; i <= s.length() - 10, ++i) {
String sub = s.substring(i, i + 10);
if (set.cotains(sub)) {
print
}
set.add(sub)
}
这样打印的结果不是排序的.
tricky的地方要，把
A -> 0
C -> 1
G -> 2
T -> 3
ACGT => 123
CGTA => 1230
把string转成int,
int[] marked = new int[4 ** 10];
set.cotains(sub)
set.add(sub)
=>
int = convert(sub)
marked(int) > 0
++marked[int]
=>
最后再 0 -> 4 ** 10,
if visited[int] > 1:
把数字转为字符串,
// 1230 => CGTA
// 123 => ACGT
打印出来
【在 s*******m 的大作中提到】
: 请问楼主，这题，他想要什么算法。
: 详细讲讲吧。
|
|
|
S***w
发帖数: 1014 | 61 就是 恨死了
【在 m*****n 的大作中提到】
: hash + radix。
: 烙印太tm的黑了。
|
e********2
发帖数: 495 | 62 4叉树，插入常时间，就是空间可能有点大。Bitmap之类的各有利弊。
【在 s*******m 的大作中提到】
: 请问楼主，这题，他想要什么算法。
: 详细讲讲吧。
|
y*****e
发帖数: 712 | 63 这题没见过的话很难30分钟做出来吧。就是做过leetcode那题，还得再写一个radix
sort!!! |
h*********o
发帖数: 26 | 64 我觉得可以用4x4的array记录frequency
(0,0) = AA
(0,1) = AC
(0,2) = AG
(0,3) = AT
(1,0) = CA
(1,1) = CC
。。。
(3,3) = TT
最後扫一次array就出答案 |
S***w
发帖数: 1014 | 65 所以 我很郁闷
【在 y*****e 的大作中提到】
: 这题没见过的话很难30分钟做出来吧。就是做过leetcode那题，还得再写一个radix
: sort!!!
|
D***n
发帖数: 149 | 66 Good idea indeed !
【在 h*********o 的大作中提到】
: 我觉得可以用4x4的array记录frequency
: (0,0) = AA
: (0,1) = AC
: (0,2) = AG
: (0,3) = AT
: (1,0) = CA
: (1,1) = CC
: 。。。
: (3,3) = TT
: 最後扫一次array就出答案
|
f****9
发帖数: 506 | 67 我也是这样被黑的。不过面试的是个越南人。
就是不让你写code，一拖就是30分钟。。。
【在 S***w 的大作中提到】
: 前面30分钟抓着问了我过去的经历，
: 做了一个小题目。
: 然后扔出这个大题 要求O(n)
: 且输出排序
: 我先用suffix array, 说不好
: 然后用hashmap, o(n), 但是输出不排行
: 恶心的地方，
: 输入不是string,是流
: 输出要排序
: O(N)
|
d******a
发帖数: 238 | 68 一年半前被老印以同样的题黑过。老印是中国人在it届的最大敌人。 |
f*******t
发帖数: 7549 | |
S***w
发帖数: 1014 | 70 Lol
【在 d******a 的大作中提到】
: 一年半前被老印以同样的题黑过。老印是中国人在it届的最大敌人。
|
|
|
S***w
发帖数: 1014 | 71 已经投诉了
估计没啥用
【在 f*******t 的大作中提到】
: 向HR投诉，就说30分钟后才让写题
|
f*******t
发帖数: 7549 | 72 一个人投诉没用，大家都投诉就有用了
【在 S***w 的大作中提到】
: 已经投诉了
: 估计没啥用
|
M**********7
发帖数: 378 | 73 哦 排序是按字典排 还以为是按重复数排
是很复杂 尤其是前面30分钟其实黑的挺明显的
是该投诉
【在 S***w 的大作中提到】
: 好呢
: 这题目老复杂了， 30分钟写完真是大牛
: 这是我给他的O(N)打印所有repease substring len=10
: Set set = new HashSet;
: for(int i = 0; i <= s.length() - 10, ++i) {
: String sub = s.substring(i, i + 10);
: if (set.cotains(sub)) {
: print
: }
: set.add(sub)
|
S***w
发帖数: 1014 | 74 按字典排序
【在 M**********7 的大作中提到】
: 哦 排序是按字典排 还以为是按重复数排
: 是很复杂 尤其是前面30分钟其实黑的挺明显的
: 是该投诉
|
s*******m
发帖数: 228 | 75 谢谢
今天刚面完电面一
【在 S***w 的大作中提到】
: 好呢
: 这题目老复杂了， 30分钟写完真是大牛
: 这是我给他的O(N)打印所有repease substring len=10
: Set set = new HashSet;
: for(int i = 0; i <= s.length() - 10, ++i) {
: String sub = s.substring(i, i + 10);
: if (set.cotains(sub)) {
: print
: }
: set.add(sub)
|
S***w
发帖数: 1014 | 76 一样题目？
【在 s*******m 的大作中提到】
: 谢谢
: 今天刚面完电面一
|
S***w
发帖数: 1014 | 77 更新一下
投诉了烙印，HR打电话，明天聊聊
【在 S***w 的大作中提到】
: 前面30分钟抓着问了我过去的经历，
: 做了一个小题目。
: 然后扔出这个大题 要求O(n)
: 且输出排序
: 我先用suffix array, 说不好
: 然后用hashmap, o(n), 但是输出不排行
: 恶心的地方，
: 输入不是string,是流
: 输出要排序
: O(N)
|
l********0
发帖数: 169 | 78 我遇到过类似的，不到最优不让我写，也是烙印
人要O(n)不是o(n) 不让写代码
【在 S***w 的大作中提到】
: 更新一下
: 投诉了烙印，HR打电话，明天聊聊
|
S*******C
发帖数: 822 | 79 这题到底怎么做？
下面解法对吗？
https://gitorious.org/interview/interview/commit/
59feda9ebfd68419a3ed842533a81a8acfa2e59a |
S*******C
发帖数: 822 | 80 用rolling hash算法对吗?但怎么得到排序的结果呢？ |
|
|
S*******C
发帖数: 822 | 81 知道了，用rolling hash + 长度为4^10的array记录所有出现的10-char
sequence，然后从这个array中从小到大取出所有10-char repeated sequences，这样
根本不需要排序 |
S***w
发帖数: 1014 | 82 对的
是这样
问题是这题 就是事先知道算法 30分钟写完也很难啊
他给的是stream,求rollinh 也很tricky
【在 S*******C 的大作中提到】
: 知道了，用rolling hash + 长度为4^10的array记录所有出现的10-char
: sequence，然后从这个array中从小到大取出所有10-char repeated sequences，这样
: 根本不需要排序
|
S*******C
发帖数: 822 | 83 第一次做一次性无bug写出来几乎不可能，大家都是练过才有可能现场解出这样的题目
【在 S***w 的大作中提到】
: 对的
: 是这样
: 问题是这题 就是事先知道算法 30分钟写完也很难啊
: 他给的是stream,求rollinh 也很tricky
|
y*****e
发帖数: 712 | 84 不太明白这个
“长度为4^10的array记录所有出现的10-char sequence，然后从这个array中从小到大
取出所有10-char repeated sequences，不需要排序”
请问到底是怎么实现不用排序的？
【在 S*******C 的大作中提到】
: 知道了，用rolling hash + 长度为4^10的array记录所有出现的10-char
: sequence，然后从这个array中从小到大取出所有10-char repeated sequences，这样
: 根本不需要排序
|
h********3
发帖数: 2075 | 85 没错，这才是最优的答案。题目里面已经有好多地方都在提示这trick。suffix array
和hashmap的解法都没有抓到这最关键的一点。
【在 h*********o 的大作中提到】
: 我觉得可以用4x4的array记录frequency
: (0,0) = AA
: (0,1) = AC
: (0,2) = AG
: (0,3) = AT
: (1,0) = CA
: (1,1) = CC
: 。。。
: (3,3) = TT
: 最後扫一次array就出答案
|
h********3
发帖数: 2075 | 86 这种问题很简单。你写不出最优的解法，跟没写都一样，都是挂掉。而且code一写几十
分钟就过去了，没时间挽回败局了。面试官明知道你在错误的方向上使劲跑，难道还不
拦住你？
【在 l********0 的大作中提到】
: 我遇到过类似的，不到最优不让我写，也是烙印
:
: 人要O(n)不是o(n) 不让写代码
|
S*******C
发帖数: 822 | 87 4种碱基组成的DNA序列相当于是base 为4的数
长度为10的sequence就是长度为10的数，一共有4^10个这样的不同的数
创建长度为4^10的array就可以记录所有可能的10-char sequence是否出现过
最后从小到大遍历一遍这样的array就可以从小到大打印出所有重复出现的10-char
sequence，这样花费4^10的内存空间不需要排序输出结果
【在 y*****e 的大作中提到】
: 不太明白这个
: “长度为4^10的array记录所有出现的10-char sequence，然后从这个array中从小到大
: 取出所有10-char repeated sequences，不需要排序”
: 请问到底是怎么实现不用排序的？
|
y*****e
发帖数: 712 | 88 天这个花的内存太大了吧。。。为啥不能用radix sort？也是扫一遍出结果。。。
【在 S*******C 的大作中提到】
: 4种碱基组成的DNA序列相当于是base 为4的数
: 长度为10的sequence就是长度为10的数，一共有4^10个这样的不同的数
: 创建长度为4^10的array就可以记录所有可能的10-char sequence是否出现过
: 最后从小到大遍历一遍这样的array就可以从小到大打印出所有重复出现的10-char
: sequence，这样花费4^10的内存空间不需要排序输出结果
|
y*****e
发帖数: 712 | 89 lz支持你，明天回来更新，记得投诉时不要使用情绪话的字眼，尽量客观冷静的描述事
实，争取hr的好感和同情，争取重新安排面试
【在 S***w 的大作中提到】
: 更新一下
: 投诉了烙印，HR打电话，明天聊聊
|
S*******C
发帖数: 822 | 90 这题你怎么用radix sort?
【在 y*****e 的大作中提到】
: 天这个花的内存太大了吧。。。为啥不能用radix sort？也是扫一遍出结果。。。
|
|
|
S*******C
发帖数: 822 | 91 CC 150中第10.3题用的内存空间是2^32个bits
我才用4^10 = 2^20个bits，才是人家的1/2^12
【在 y*****e 的大作中提到】
: 天这个花的内存太大了吧。。。为啥不能用radix sort？也是扫一遍出结果。。。
|
C****t
发帖数: 53 | 92 A python version:
def num(maps, s): ######## transform string to 4-based number
digit = 0
for i in range(len(s)):
digit = 4*digit + maps[s[i]]
return digit
def findRepeat(s):
maps = {'A':0, 'C':1,'G':2,'T':3}
bitmap = [0]*pow(4,2)
for i in range(len(s) - 2+1):
bitmap[ num[maps, s[i:i+2] ] += 1
invmaps = {v:k for k,v in maps.items()} ####### reverse maps
for i in range(len(bitmap)):
if bitmap[i] > 1:
print (invmaps[i//4] + invmaps[i%4]) |
e******1
发帖数: 7 | 93 This is actually a straightforward question. Use a hashmap to keep all the
10-letter-long sequences and the count. At the end, save all items that has
count > 1 in a list and sort the list.
Sorting the list takes constant time because there can only be up to 1
million (4^10) items in the list.
The overall complexity is O(n) |
x*******9
发帖数: 138 | 94 同情LZ遭遇，不过这题不算难的说。。。=。=。。。
随手写一下，缩进不太好看，直接在回复框里打的。
（又看了一下题，这个是2碱基的简单版本，10碱基的版本类似。）
// 约定：
// A -> 0, T -> 1, C -> 2, G -> 3
// AT -> (A << 2) + (T << 0) -> 1
// CG -> (C << 2) + (G << 0) -> 11
// vise versa. :)
class Solution {
public:
int solve(const NucFlow& nuc_flow) {
_mp.clear();
char pre = '\0';
while (nuc_flow.has_next()) {
if (!pre) {
pre = nuc_flow.next();
continue;
}
char now = nuc_flow().next();
int u = nuc_to_num(pre, now); // e.g. AT -> (0, 1) -> 1
_mp[u]++;
pre = now;
}
show_ans();
return 0;
}
private:
void show_ans() {
for (int i = 0; i < 16; i++) {
int cnt = _mp[i];
if (cnt < 2) {
continue;
}
string nuc_tuple = num_to_nuc(i);
printf("%s -> %d\n", nuc_tuple.c_str(), cnt);
}
private:
unordered_map _mp;
}; |
o**********e
发帖数: 18403 | 95 赞！问题本质。
烙印反白眼，打断您说话，
冷嘲热讽，语带轻蔑，晚到
早走，把您的信息传给印度
BUDDY（有损您的PRIVACY）。
这些都是可以投诉的。
有理有据，一剑封喉。
您要是拿不到机会，想搞大，
很多人都会支持您的。 祝好！ |
f********a
发帖数: 367 | 96 in order, doesn't mean in lexical order.
here, in order means in the order of appearance from the input
rolling hash
has
【在 e******1 的大作中提到】
: This is actually a straightforward question. Use a hashmap to keep all the
: 10-letter-long sequences and the count. At the end, save all items that has
: count > 1 in a list and sort the list.
: Sorting the list takes constant time because there can only be up to 1
: million (4^10) items in the list.
: The overall complexity is O(n)
|
n******n
发帖数: 12088 | 97 这不是高频题吗？
【在 S***w 的大作中提到】
: 前面30分钟抓着问了我过去的经历，
: 做了一个小题目。
: 然后扔出这个大题 要求O(n)
: 且输出排序
: 我先用suffix array, 说不好
: 然后用hashmap, o(n), 但是输出不排行
: 恶心的地方，
: 输入不是string,是流
: 输出要排序
: O(N)
|
n******n
发帖数: 12088 | 98 问经历多久？小题是什么？用了多少时间？答案对吗？
【在 S***w 的大作中提到】
: 前面30分钟抓着问了我过去的经历，
: 做了一个小题目。
: 然后扔出这个大题 要求O(n)
: 且输出排序
: 我先用suffix array, 说不好
: 然后用hashmap, o(n), 但是输出不排行
: 恶心的地方，
: 输入不是string,是流
: 输出要排序
: O(N)
|
S***w
发帖数: 1014 | 99 input stream not string
【在 C****t 的大作中提到】
: A python version:
: def num(maps, s): ######## transform string to 4-based number
: digit = 0
: for i in range(len(s)):
: digit = 4*digit + maps[s[i]]
: return digit
: def findRepeat(s):
: maps = {'A':0, 'C':1,'G':2,'T':3}
: bitmap = [0]*pow(4,2)
: for i in range(len(s) - 2+1):
|
S***w
发帖数: 1014 | 100 差不多这样吧
不过以前没看过这题目
【在 x*******9 的大作中提到】
: 同情LZ遭遇，不过这题不算难的说。。。=。=。。。
: 随手写一下，缩进不太好看，直接在回复框里打的。
: （又看了一下题，这个是2碱基的简单版本，10碱基的版本类似。）
: // 约定：
: // A -> 0, T -> 1, C -> 2, G -> 3
: // AT -> (A << 2) + (T << 0) -> 1
: // CG -> (C << 2) + (G << 0) -> 11
: // vise versa. :)
: class Solution {
: public:
|
|
|
s*******m
发帖数: 228 | 101 经典的nestedinteger
【在 S***w 的大作中提到】
: 一样题目？
|
s*******m
发帖数: 228 | 102 按楼主讲的方法，
A-> 0
C->1
G->2
T->3
因为子串长度是10，开一个4的10次方的数组。
把子串转化成数字，作为数组的index.
如果出现过，该数组的值加1.
最后遍历这个数组就可以了吧，应该是排好序的。
【在 m*****n 的大作中提到】
: hash + radix。
: 烙印太tm的黑了。
|
s*******m
发帖数: 228 | 103 烙印要求的子串长度是10
【在 h*********o 的大作中提到】
: 我觉得可以用4x4的array记录frequency
: (0,0) = AA
: (0,1) = AC
: (0,2) = AG
: (0,3) = AT
: (1,0) = CA
: (1,1) = CC
: 。。。
: (3,3) = TT
: 最後扫一次array就出答案
|
w****a
发帖数: 710 | |
a*****2
发帖数: 96 | 105 这不是leetcode的原题吗？
public class Solution {
public List findRepeatedDnaSequences(String s) {
List result=new ArrayList();
HashMap computed=new HashMap();
for(int i=0;i<=s.length()-10;i++)
{
String sub=s.substring(i,i+10);
int key=getKey(sub);
if(computed.containsKey(key))
{
computed.put(key,computed.get(key)+1);
if(computed.get(key)==2)
result.add(sub);
}
else
computed.put(key,1);
}
return result;
}
public int getKey(String s)
{
int result=0;
for(int i= 0 ; i < s.length(); i++)
{
int b=0;
switch(s.charAt(i))
{
case 'A':
b|=0;
break;
case 'C':
b|=1;
break;
case 'G':
b|=2;
break;
case 'T':
b|=3;
break;
}
result=b|result;
result=result<<2;
}
return result;
}
} |
m****v
发帖数: 88 | |
c******n
发帖数: 4965 | 107 你前头都做出来了， 为什么说后面的sort 难呢？
难道不是
ArrayList arr = new ArrayList();
arr.add(your_set)
Collections.sort(arr);
??
另外你说什么A-->0, C-->1 转换完全没有必要，即使你自己写sorting, 比较就用字符
比较就好了，就是alphabetical sorting 的定义。 不知道为什么你说要转换。 感觉
你想难了
【在 S***w 的大作中提到】
: 好呢
: 这题目老复杂了， 30分钟写完真是大牛
: 这是我给他的O(N)打印所有repease substring len=10
: Set set = new HashSet;
: for(int i = 0; i <= s.length() - 10, ++i) {
: String sub = s.substring(i, i + 10);
: if (set.cotains(sub)) {
: print
: }
: set.add(sub)
|
c******n
发帖数: 4965 | 108 对啊 ， 楼上那么多越说越玄乎。。。
https://leetcode.com/problems/repeated-dna-sequences/
【在 a*****2 的大作中提到】
: 这不是leetcode的原题吗？
: public class Solution {
: public List findRepeatedDnaSequences(String s) {
: List result=new ArrayList();
: HashMap computed=new HashMap();
: for(int i=0;i<=s.length()-10;i++)
: {
: String sub=s.substring(i,i+10);
: int key=getKey(sub);
: if(computed.containsKey(key))
|
y*****e
发帖数: 712 | 109 LZ面这题的时候这题还没加到leetcode上，这题是不是高频不知道，但肯定没现在普及
度这么高，因为进了leetcode吗。所以不要用现在的角度衡量当时的情景，发面经这事
就是前人种树后人乘凉，有了前面的人的失败，被黑，才有了后面的人觉得这题简单的
时候。
【在 c******n 的大作中提到】
: 对啊 ， 楼上那么多越说越玄乎。。。
: https://leetcode.com/problems/repeated-dna-sequences/
|
y*****e
发帖数: 712 | 110 sorting难是因为要求o(n)
【在 c******n 的大作中提到】
: 你前头都做出来了， 为什么说后面的sort 难呢？
: 难道不是
: ArrayList arr = new ArrayList();
: arr.add(your_set)
: Collections.sort(arr);
: ??
: 另外你说什么A-->0, C-->1 转换完全没有必要，即使你自己写sorting, 比较就用字符
: 比较就好了，就是alphabetical sorting 的定义。 不知道为什么你说要转换。 感觉
: 你想难了
|
|
|
b**********5
发帖数: 7881 | 111 哎， 所以说啊， 我N年前面试时， 问的就一题， circular linkedlist。。。
现在有了leetcode这种网站， 我刷了N个年的题， 还是一个公司都刷不进去。。。
【在 y*****e 的大作中提到】
: LZ面这题的时候这题还没加到leetcode上，这题是不是高频不知道，但肯定没现在普及
: 度这么高，因为进了leetcode吗。所以不要用现在的角度衡量当时的情景，发面经这事
: 就是前人种树后人乘凉，有了前面的人的失败，被黑，才有了后面的人觉得这题简单的
: 时候。
|
i******s
发帖数: 301 | 112 你说的这个老印我可能认识，是不是名字是s开头？如果是，他以前害过老中，也被我
们黑过，所以有仇恨。你不要太放心里去，垃圾哪里都有。可以去投诉，我已经做过了。
【在 S***w 的大作中提到】
: 前面30分钟抓着问了我过去的经历，
: 做了一个小题目。
: 然后扔出这个大题 要求O(n)
: 且输出排序
: 我先用suffix array, 说不好
: 然后用hashmap, o(n), 但是输出不排行
: 恶心的地方，
: 输入不是string,是流
: 输出要排序
: O(N)
|
c******n
发帖数: 4965 | 113 哦，明白了。
O(N) 那真是很难，不是店面该出的题。真是被黑了。 L 家烙印那么多不是没有原因的
【在 y*****e 的大作中提到】
: sorting难是因为要求o(n)
|
c******n
发帖数: 4965 | 114 不对啊，我再想了下， “流”（stream) 根本就没有size /length 的概念， 是
infinite 的， 还扯什么O(N). 如果有截止， 那你用radix 本身的4^10 的size 都要
遍历， 如果input size 比4^10 小很多，那还叫什么O(N)
anyway, 作为一个讨论倒是出了很多可以学习的地方， 纠结题本身已经没有什么意义
了， 尤其是这样一个烙印聚居的地方
【在 c******n 的大作中提到】
: 哦，明白了。
: O(N) 那真是很难，不是店面该出的题。真是被黑了。 L 家烙印那么多不是没有原因的
|
s********a
发帖数: 19 | 115 被楼主的头像炸出来了。。楼主是妹子吗？头像居然是我的初恋T部！！！！ |
k******a
发帖数: 44 | 116 我的思路是：
1. 以k letter大的滑动窗口处理stream，用hashmap记录统计结果
2. 按照A,C,G,T的字母组合[AA, AC, AG, AT, CA, CC, CG, ....]查询hashmap，如果
value>1, 输出key
可能可以用rolling hash customize hashmap来优化
靠谱？ |
f*****i
发帖数: 835 | 117 一共就16种输出，自己建个look up table就好了. 把16种输出按排序map到0-15。
A -> 00
C->01
G->10
T->11
（真的在存取data时也应该这样表示，用字母浪费了）
Count[lut[AA]]++;
...
按顺序输出大于2的。
10个letter也一样。
【在 M**********7 的大作中提到】
: 哦 排序是按字典排 还以为是按重复数排
: 是很复杂 尤其是前面30分钟其实黑的挺明显的
: 是该投诉
|
c*******e
发帖数: 373 | 118 4^10
1M内存就够了，不算大吧
这种题目，可能出现全排列，又要求计数，还要求天然就排序了，那就没有其他可能了
，最好只能是这种数组的解决方案。
用hash只能是更慢更费内存，其他数据结构就更差了。
【在 y*****e 的大作中提到】
: 天这个花的内存太大了吧。。。为啥不能用radix sort？也是扫一遍出结果。。。
|
p*******7
发帖数: 48 | |
x*******9
发帖数: 138 | 120 import collections
dna = 'AAGATCCGTCAGTTTTCAAT'
dna_group = [dna[i: i + 2] for i in xrange(len(dna) - 1)]
c = collections.Counter(dna_group)
print sorted(c.most_common(), key=lambda x: x[0])
五行搞定嘛。。。 |
