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

avatar
s*t
5
问你公司 management。

【在 s********n 的大作中提到】
: thanks for sharing.
avatar
j*y
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?

avatar
c*g
8
没说一定该谁付
看你公司policy

【在 s********n 的大作中提到】
: thanks for sharing.
avatar
l*n
9
兄弟,这这只是会议摘要啊,没全文啊。摘要你看得到的吧?
avatar
C*y
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。很好的机会被我浪费了,还是弱。

avatar
g*8
11
re

【在 c*******g 的大作中提到】
: 没说一定该谁付
: 看你公司policy

avatar
f*g
13
两个仍然用xor
不然很可能溢出
avatar
F*p
14
either way
avatar
g*y
15
Thank you
avatar
j*y
16

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

【在 f***g 的大作中提到】
: 两个仍然用xor
: 不然很可能溢出

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

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

【在 e*****e 的大作中提到】
: A xor A = 0
avatar
j*y
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

avatar
i*e
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
avatar
j*y
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?
avatar
m*v
23
1. hashmap?
2. summation equation

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

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

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

avatar
j*y
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{

avatar
r*e
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){

avatar
j*y
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));

avatar
r*e
28
怎么扩展到3个呢?如果缺的数字是2,4,6的话,
xor的结果就是0了。没有任何bit有1了。

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

avatar
r*e
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,也是有通不过这个模板类的编译。
: 为什么呢?

相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。