paper help - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Biology - 生物学

paper help

paper help# Biology - 生物学

j*y2013-05-16 07:05

1 楼

1. 一个很大的整型数组，里面有duplicate，用怎样的方法可以快速地去除这些duplicate？
我感觉应该先把这个数组sort一下，但是之后该怎么办呢？完全没有思路。
2. 给我9999个数字，数值连续从1到10000，但缺了一个。要求用一种非常简洁的方法得出缺了哪个数字？
3. 一个storage server的运行过程中，突然出现stop responding的现象。如果不看code，不看GDB的trace和应用程序的log，该怎样快速诊断出可能的原因？
这几个题我一个都没有答上来，请大家帮帮忙看一下，谢了先。

s*n2013-05-16 07:05

2 楼

thanks for sharing.

g*y2013-05-16 07:05

3 楼

need the pdf of this paper. Thanks much!
http://www.thelancet.com/journals/lancet/article/PIIS0140-6736(
A strong correlation between expression of Wntless and of human epidermal
growth factor receptor 2 in gastric, ovarian, and breast cancers suggests a
novel-signalling pathway involving NFκB and STAT3

C*y2013-05-16 07:05

4 楼

1. bitmap比较好，当然sort也可以做
这个有个问题就是，可能in-place remove 所用的两个指针所指的位置不能同时装入内
存，这个问题还没想好如何解决
2. 方法很多
a. 全部加起来，看缺多少，就是哪个数
b. 1xor2xor...10000，然后继续xor给的9999个数字
3.
不知道，太开放了，先说集中可能，再跟面试官交流，慢慢讨论吧

duplicate？
法得出缺了哪个数字？
code，不看GDB的trace和应用程序的log，该怎样快速诊断出可能的原因？

【在 j***y 的大作中提到】

: 1. 一个很大的整型数组，里面有duplicate，用怎样的方法可以快速地去除这些duplicate？
: 我感觉应该先把这个数组sort一下，但是之后该怎么办呢？完全没有思路。
: 2. 给我9999个数字，数值连续从1到10000，但缺了一个。要求用一种非常简洁的方法得出缺了哪个数字？
: 3. 一个storage server的运行过程中，突然出现stop responding的现象。如果不看code，不看GDB的trace和应用程序的log，该怎样快速诊断出可能的原因？
: 这几个题我一个都没有答上来，请大家帮帮忙看一下，谢了先。

s*t2013-05-16 07:05

5 楼

问你公司 management。

【在 s********n 的大作中提到】

: thanks for sharing.

g*y2013-05-16 07:05

6 楼

email: a********[email protected]
Thank you.

j*y2013-05-16 07:05

7 楼

bitmap不是图形格式吗？能把数组变成一个bitmap？不太懂啊。能不能给段代码的例子？
这个方法就是面试官后来跟我说的。不过他后来又说，如果是9998个数字，数值从1到
10000，缺两个，加法就貌似不行了。这种情况下，该用什么方法呢？
这个方法是个什么原理啊？xor完这19999个数字之后就能保证得出漏掉的那个数吗？
当时面试官和我说的是这种问题，第一个想法应该是不是disk IO出问题了？不过我想
，不看log，不看trace，怎么能断定是disk IO的问题？莫非去看硬盘指示灯？
因为电面表现太差，也没好意思去详细问这个问题的思路。
对了，忘了提公司的名字了，NetApp。很好的机会被我浪费了，还是弱。

【在 C***y 的大作中提到】

: 1. bitmap比较好，当然sort也可以做
: 这个有个问题就是，可能in-place remove 所用的两个指针所指的位置不能同时装入内
: 存，这个问题还没想好如何解决
: 2. 方法很多
: a. 全部加起来，看缺多少，就是哪个数
: b. 1xor2xor...10000，然后继续xor给的9999个数字
: 3.
: 不知道，太开放了，先说集中可能，再跟面试官交流，慢慢讨论吧
:
: duplicate？

c*g2013-05-16 07:05

8 楼

没说一定该谁付
看你公司policy

【在 s********n 的大作中提到】

: thanks for sharing.

l*n2013-05-16 07:05

9 楼

兄弟，这这只是会议摘要啊，没全文啊。摘要你看得到的吧？

C*y2013-05-16 07:05

10 楼

1.bitmap你可以看看programming pearls的第一章
2.两个话，可以解方程：
x+y+其他9998个数 = 1+...+10000
x^2+y^2+...=1^2+...+10000^2

子？

【在 j***y 的大作中提到】

:
: bitmap不是图形格式吗？能把数组变成一个bitmap？不太懂啊。能不能给段代码的例子？
: 这个方法就是面试官后来跟我说的。不过他后来又说，如果是9998个数字，数值从1到
: 10000，缺两个，加法就貌似不行了。这种情况下，该用什么方法呢？
: 这个方法是个什么原理啊？xor完这19999个数字之后就能保证得出漏掉的那个数吗？
: 当时面试官和我说的是这种问题，第一个想法应该是不是disk IO出问题了？不过我想
: ，不看log，不看trace，怎么能断定是disk IO的问题？莫非去看硬盘指示灯？
: 因为电面表现太差，也没好意思去详细问这个问题的思路。
: 对了，忘了提公司的名字了，NetApp。很好的机会被我浪费了，还是弱。

g*82013-05-16 07:05

11 楼

re

【在 c*******g 的大作中提到】

: 没说一定该谁付
: 看你公司policy

m*s2013-05-16 07:05

12 楼

only abstract
http://www.sendspace.com/file/eklrge

f*g2013-05-16 07:05

13 楼

两个仍然用xor
不然很可能溢出

F*p2013-05-16 07:05

14 楼

either way

g*y2013-05-16 07:05

15 楼

Thank you

j*y2013-05-16 07:05

16 楼

不明白这个xor解法的原理是什么，可以简单讲一下或给个参考文献吗？

【在 f***g 的大作中提到】

: 两个仍然用xor
: 不然很可能溢出

f*g2013-05-16 07:05

17 楼

没找到，我试着讲一下：
仍然按照Chevy的方法做
如果是一个数：
最后的结果就是 M
如果是两个数：结果就是M1 xor M2
从这个结果中挑一个bit为1的，就可以把原数组划分为两组。missing numbers分别在
这两个组中。
按照1个数的方法再分别做一遍。
据说这个思路可以扩展到3个，4个数去
有个类似的http://geeksforgeeks.org/?p=2457

e*e2013-05-16 07:05

18 楼

A xor A = 0

j*y2013-05-16 07:05

19 楼

啊，这个重要的xor的性质我忘记了，谢谢提醒。

【在 e*****e 的大作中提到】

: A xor A = 0

j*y2013-05-16 07:05

20 楼

知道A xor A == 0之后，明白对一个数的解法了。
嗯，现在也还明白。
详细读了链接里面的文章，终于弄懂了。多谢。
另外想再请教一下，对第一个duplicate的问题，有什么好的方法吗？

【在 f***g 的大作中提到】

: 没找到，我试着讲一下：
: 仍然按照Chevy的方法做
: 如果是一个数：
: 最后的结果就是 M
: 如果是两个数：结果就是M1 xor M2
: 从这个结果中挑一个bit为1的，就可以把原数组划分为两组。missing numbers分别在
: 这两个组中。
: 按照1个数的方法再分别做一遍。
: 据说这个思路可以扩展到3个，4个数去
: 有个类似的http://geeksforgeeks.org/?p=2457

i*e2013-05-16 07:05

21 楼

Remove duplicates 的 Sort 的方法如下：
// Remove the duplicates in place, and returns the new size of the array
// Assumes the array is already sorted.
int removeDuplicates(int A[], int n) {
int j = 0;
for (int i = 0; i < n; i++) {
if (A[i] != A[j])
A[++j] = A[i];
}
return j+1;
}
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

j*y2013-05-16 07:05

22 楼

Hi, 1337:
非常感谢你的解答。已经验证过了，确实可以实现in place remove duplicates. 顺便
问一下，这段code在你的blog里面出现过吗？这是个有名的算法吗？
当时面试官给的提示是再新建一个数组，似乎他的意思是把没有duplicate的element往
新数组里面扔。他还提到要用hashtable的方法，这个地方该怎样应用hashtable呢？据
他说用hashtable的话，就用不着先对数组进行排序了。
我对hashtable没什么概念，只知道是个key-value pair的table。似乎还要定义一个
hash function来建立从key到value之间的mapping关系。
如果用面试官所说的方法，该怎么解呢？可否给个example code？

m*v2013-05-16 07:05

23 楼

1. hashmap?
2. summation equation

duplicate？
法得出缺了哪
个数字？
code，
不看GDB的trace和应用程序的log，该怎样快速诊断出可能的原因？

【在 j***y 的大作中提到】

i*92013-05-16 07:05

24 楼

duplicate？
不要sorting的 remove duplicate
const int REMOVE=-1000;
int removeduplicate(int a[],int n){
unordered_map hash;
for(int i=0;iif(hash.find(a[i])!=hash.end()){
a[i]=REMOVE;
}else{
hash[a[i]]=1;
}
}
int j=0;
int i=0;
while(iwhile(a[i]==REMOVE){
i++;
}
a[j]=a[i];
i++;
j++;
}
return j;
}
法得出缺了
哪个数字？
code，不看GDB的trace和应用程序的log，该怎样快速诊断出可能的原因？

【在 j***y 的大作中提到】

j*y2013-05-16 07:05

25 楼

谢谢啊。这两天我也在学习hashtable的方法，刚好看到C++里面有个map可以用。
调试了一下你的程序，稍作调整后的code如下：
－－－
#include
//#include
#include
using namespace std;
const int REMOVE = -1000;
int remove_duplicate(int a[],int n){
int i = 0, j = 0;
//unordered_map hash;
map hash;
for(i = 0; i < n; ++i){
if(hash.find(a[i]) != hash.end()) {
a[i] = REMOVE;
} else {
hash[a[i]] = 1;
}
}
j = 0;
i = 0;
while (i < n){
while (a[i] == REMOVE){
i++;
}
a[j] = a[i];
i++;
j++;
}
return j;
}
int main()
{
int arr[8] = {3, 2, 7, 4, 4, 6, 1, 5};
int len = 0;
int i = 0;

len = remove_duplicate(arr, sizeof(arr));
cout << "The new size of arr[] is " << len << endl;
for (i = 0; i < len; ++i)
cout << arr[i] << "\t";
cout << endl;
getchar();
return 0;
}
－－－
我在windows xp下的用的是Dev-C++，似乎比较老，因此而不支持，因
此我把它改成map了。
但编译通过后，跑出来的结果很奇怪，见附图。能帮我看一下是什么导致的吗？
谢谢。

【在 i**9 的大作中提到】

:
: duplicate？
: 不要sorting的 remove duplicate
: const int REMOVE=-1000;
: int removeduplicate(int a[],int n){
: unordered_map hash;
: for(int i=0;i: if(hash.find(a[i])!=hash.end()){
: a[i]=REMOVE;
: }else{

r*e2013-05-16 07:05

26 楼

You passed a wrong size of the array and accessed memory out of boundary
int arr[8] = {3, 2, 7, 4, 4, 6, 1, 5};
...
len = remove_duplicate(arr, sizeof(arr));
When sizeof is applied to an array, the result is the size in bytes of the
array in memory. Thus, it should be changed to:
len = remove_duplicate(arr, sizeof(arr)/sizeof(int));

【在 j***y 的大作中提到】

:
: 谢谢啊。这两天我也在学习hashtable的方法，刚好看到C++里面有个map可以用。
: 调试了一下你的程序，稍作调整后的code如下：
: －－－
: #include
: //#include
: #include
: using namespace std;
: const int REMOVE = -1000;
: int remove_duplicate(int a[],int n){

j*y2013-05-16 07:05

27 楼

多谢，确实是这个问题。我的疏忽。改成remove_duplicate(arr, sizeof(arr)/sizeof
(arr[0]))了，编译通过，运行正常。多谢指出这个错误。
不过，Dev-C++似乎不支持unordered_map。这个模板类不在C++的标准库里面吗？但是
我用了1337coder的coding panel，也是有通不过这个模板类的编译。
为什么呢？

【在 r*******e 的大作中提到】

: You passed a wrong size of the array and accessed memory out of boundary
: int arr[8] = {3, 2, 7, 4, 4, 6, 1, 5};
: ...
: len = remove_duplicate(arr, sizeof(arr));
: When sizeof is applied to an array, the result is the size in bytes of the
: array in memory. Thus, it should be changed to:
: len = remove_duplicate(arr, sizeof(arr)/sizeof(int));

r*e2013-05-16 07:05

28 楼

怎么扩展到3个呢？如果缺的数字是2，4，6的话，
xor的结果就是0了。没有任何bit有1了。

【在 f***g 的大作中提到】

r*e2013-05-16 07:05

29 楼

http://mitbbs.com/article1/JobHunting/31808443_3_0.html

the
sizeof

【在 j***y 的大作中提到】

:
: 多谢，确实是这个问题。我的疏忽。改成remove_duplicate(arr, sizeof(arr)/sizeof
: (arr[0]))了，编译通过，运行正常。多谢指出这个错误。
: 不过，Dev-C++似乎不支持unordered_map。这个模板类不在C++的标准库里面吗？但是
: 我用了1337coder的coding panel，也是有通不过这个模板类的编译。
: 为什么呢？