f****9
发帖数: 506 | 1 1. Binary Tree Upside Down.
2. given a sequence of DNA (ATGC), print all 10-letter sequences that
appears more than once in alphabetical order.
这年头只做两题是不是没戏了，好像大家都做3题。
第一题几分钟就做完了，然后面试官问full binary tree怎么弄，我说不会，后来他说
他把题目看错了。。。
第二题折腾了40分钟，也没让写代码，最后老让我纠结一些没用的东西，比如把hash
value从int换成boolean可以省空间，你以为全世界的人都用java。。。 |
y*****e
发帖数: 712 | 2 沙漠叫bottom up a binary tree? |
f****9
发帖数: 506 | 3 改了，学名叫 Binary Tree Upside Down
【在 y*****e 的大作中提到】
: 沙漠叫bottom up a binary tree?
|
s******t
发帖数: 104 | 4
【在 f****9 的大作中提到】
: 1. Binary Tree Upside Down.
: 2. given a sequence of DNA (ATGC), print all 10-letter sequences that
: appears more than once in alphabetical order.
: 这年头只做两题是不是没戏了，好像大家都做3题。
: 第一题几分钟就做完了，然后面试官问full binary tree怎么弄，我说不会，后来他说
: 他把题目看错了。。。
: 第二题折腾了40分钟，也没让写代码，最后老让我纠结一些没用的东西，比如把hash
: value从int换成boolean可以省空间，你以为全世界的人都用java。。。
|
s******t
发帖数: 104 | 5 第二题问的是什么意思。LZ能不能举个例
【在 f****9 的大作中提到】
: 1. Binary Tree Upside Down.
: 2. given a sequence of DNA (ATGC), print all 10-letter sequences that
: appears more than once in alphabetical order.
: 这年头只做两题是不是没戏了，好像大家都做3题。
: 第一题几分钟就做完了，然后面试官问full binary tree怎么弄，我说不会，后来他说
: 他把题目看错了。。。
: 第二题折腾了40分钟，也没让写代码，最后老让我纠结一些没用的东西，比如把hash
: value从int换成boolean可以省空间，你以为全世界的人都用java。。。
|
o***c
发帖数: 32 | 6 请问非US的new grad如何拿到L的电面....真是太惨了。求内推了n家公司都没信。 |
f****9
发帖数: 506 | 7 都是老题了。
就是输入是一个DNA序列串，由ATGC构成，比如AATTGGCCCAAA...。让你看输入中所有长
度为10的子序列，如果它再之前出现过，就输出。输出要求按照字母排序。
【在 s******t 的大作中提到】
: 第二题问的是什么意思。LZ能不能举个例
|
y*****e
发帖数: 712 | 8 lz, 当把每个sequence都放到hashmap里后怎么sort才能达到O(n）啊，难道要用
treeMap?
【在 f****9 的大作中提到】
: 都是老题了。
: 就是输入是一个DNA序列串，由ATGC构成，比如AATTGGCCCAAA...。让你看输入中所有长
: 度为10的子序列，如果它再之前出现过，就输出。输出要求按照字母排序。
|
|
g****v
发帖数: 971 | 9 为什么我的solution老是提示超时？
TreeNode *upsideDownBinaryTree(TreeNode *root) {
if(!root) return NULL;
stack store;
TreeNode *current = root;
while(current->left)
{
store.push(current);
current = current->left;
}
//now current is the new root;
TreeNode *newRoot = current;
while(!store.empty())
{
//store.top() is the parent node of current
current->left = store.top()->right;
current->right = store.top();
current = store.top();
store.pop();
}
return newRoot;
}
【在 f****9 的大作中提到】
: 1. Binary Tree Upside Down.
: 2. given a sequence of DNA (ATGC), print all 10-letter sequences that
: appears more than once in alphabetical order.
: 这年头只做两题是不是没戏了，好像大家都做3题。
: 第一题几分钟就做完了，然后面试官问full binary tree怎么弄，我说不会，后来他说
: 他把题目看错了。。。
: 第二题折腾了40分钟，也没让写代码，最后老让我纠结一些没用的东西，比如把hash
: value从int换成boolean可以省空间，你以为全世界的人都用java。。。
|
x*******i
发帖数: 777 | 10 第二题难道要把所有可能的10-char sequence都存在HashSet里或者HashMap里？ |
|
|
f****9
发帖数: 506 | 11 最后应该
root->right = NULL;
吧。。。
【在 g****v 的大作中提到】
: 为什么我的solution老是提示超时？
: TreeNode *upsideDownBinaryTree(TreeNode *root) {
: if(!root) return NULL;
: stack store;
: TreeNode *current = root;
:
: while(current->left)
: {
: store.push(current);
: current = current->left;
|
s******d
发帖数: 9806 | 12 key不要存char,存int。 value确实应该是boolean。
DNA只有四个字母，ATGC，这样一个字母用2个bit就能存，10个字母的sequence相当于
20个bit。每次左移两位去掉最老的字母，在最末尾加上新字母的两位，然后乘以
0XFFFFF（取后20位），就是新的key值啦。
【在 x*******i 的大作中提到】
: 第二题难道要把所有可能的10-char sequence都存在HashSet里或者HashMap里？
|
y*****e
发帖数: 712 | 13 这个办法好高端，完全被镇住了。。。
我想问问啊，是不是每个key放一个int的地方也就是32bit就够了？
如果一个key出现过，第二次出现的时候把value换成true?
还有就是是不是需要写个小的encoder来encode ATGC,
比如A == 00, C = 01, G = 10, T == 11之类的？
一碰到bit operation就蒙，牛人能写写读sequence到存key这个部分吗
【在 s******d 的大作中提到】
: key不要存char,存int。 value确实应该是boolean。
: DNA只有四个字母，ATGC，这样一个字母用2个bit就能存，10个字母的sequence相当于
: 20个bit。每次左移两位去掉最老的字母，在最末尾加上新字母的两位，然后乘以
: 0XFFFFF（取后20位），就是新的key值啦。
|
U***A
发帖数: 849 | |
U***A
发帖数: 849 | 15 看看这个可以不？
vector DNA10letter(string &s){
map mp_itoc;
mp_itoc.insert(make_pair(0,'A'));
mp_itoc.insert(make_pair(1,'C'));
mp_itoc.insert(make_pair(2,'G'));
mp_itoc.insert(make_pair(3,'T'));
map mp_ctoi;
mp_ctoi.insert(make_pair('A',0));
mp_ctoi.insert(make_pair('C',1));
mp_ctoi.insert(make_pair('G',2));
mp_ctoi.insert(make_pair('T',3));
vector result;
map mp;
int len = (int)s.length();
if(len<=10) return result;
for(int i=0; i<=len-10; i++){
int j=i;
unsigned int key = 0;
while(j
key = (key<<2) | mp_ctoi[s[j]];
j++;
}
if(mp.find(key) == mp.end()){
mp.insert(make_pair(key, false));
}
else{
mp[key] = true;
}
}
unsigned int flag = 3;
for(map::iterator it = mp.begin(); it!=mp.end();
it++){
if(it->second){
unsigned int tmp = it->first;
string s="";
int j = 10;
while(j>0){
s = mp_itoc[tmp&flag]+s;
tmp = tmp>>2;
j--;
}
result.push_back(s);
}
}
return result;
}
【在 y*****e 的大作中提到】
: 这个办法好高端，完全被镇住了。。。
: 我想问问啊，是不是每个key放一个int的地方也就是32bit就够了？
: 如果一个key出现过，第二次出现的时候把value换成true?
: 还有就是是不是需要写个小的encoder来encode ATGC,
: 比如A == 00, C = 01, G = 10, T == 11之类的？
: 一碰到bit operation就蒙，牛人能写写读sequence到存key这个部分吗
|
P****i
发帖数: 1362 | 16 第二题不得用suffix tree么
【在 f****9 的大作中提到】
: 都是老题了。
: 就是输入是一个DNA序列串，由ATGC构成，比如AATTGGCCCAAA...。让你看输入中所有长
: 度为10的子序列，如果它再之前出现过，就输出。输出要求按照字母排序。
|
x*x
发帖数: 156 | 17 Still too complicated ... like a finite state automata?
【在 f****9 的大作中提到】
: 都是老题了。
: 就是输入是一个DNA序列串，由ATGC构成，比如AATTGGCCCAAA...。让你看输入中所有长
: 度为10的子序列，如果它再之前出现过，就输出。输出要求按照字母排序。
|
S*******C
发帖数: 822 | 18 怎么把bit sequence存在HashMap里？
没有bit sequence这种数据类型，难道要把它转成10进制数Integer再存在HashMap<
Integer, Boolean>里？
【在 s******d 的大作中提到】
: key不要存char,存int。 value确实应该是boolean。
: DNA只有四个字母，ATGC，这样一个字母用2个bit就能存，10个字母的sequence相当于
: 20个bit。每次左移两位去掉最老的字母，在最末尾加上新字母的两位，然后乘以
: 0XFFFFF（取后20位），就是新的key值啦。
|
S*******C
发帖数: 822 | 19 好方法，DNA序列本质是四进制数字，用radix为4的BigInteger作为key也可以啊
【在 s******d 的大作中提到】
: key不要存char,存int。 value确实应该是boolean。
: DNA只有四个字母，ATGC，这样一个字母用2个bit就能存，10个字母的sequence相当于
: 20个bit。每次左移两位去掉最老的字母，在最末尾加上新字母的两位，然后乘以
: 0XFFFFF（取后20位），就是新的key值啦。
|
f****9
发帖数: 506 | 20 Java 的 boolean不是不一定比int短么？
我说用bits，面试官说用boolean。我说不知道java的boolean多长，然后就没话说了。
碰上sb的面试官自认倒霉。
当然我自己水平也不咋地。。。
【在 s******d 的大作中提到】
: key不要存char,存int。 value确实应该是boolean。
: DNA只有四个字母，ATGC，这样一个字母用2个bit就能存，10个字母的sequence相当于
: 20个bit。每次左移两位去掉最老的字母，在最末尾加上新字母的两位，然后乘以
: 0XFFFFF（取后20位），就是新的key值啦。
|
f********a
发帖数: 367 | 21 Same here.. and i have experience and no visa problems. Sent out about 6,7
emails based on the posts here, and no replies...
【在 o***c 的大作中提到】
: 请问非US的new grad如何拿到L的电面....真是太惨了。求内推了n家公司都没信。
|
