j***y
发帖数: 2074 | 1 1. 一个很大的整型数组，里面有duplicate，用怎样的方法可以快速地去除这些duplicate？
我感觉应该先把这个数组sort一下，但是之后该怎么办呢？完全没有思路。
2. 给我9999个数字，数值连续从1到10000，但缺了一个。要求用一种非常简洁的方法得出缺了哪个数字？
3. 一个storage server的运行过程中，突然出现stop responding的现象。如果不看code，不看GDB的trace和应用程序的log，该怎样快速诊断出可能的原因？
这几个题我一个都没有答上来，请大家帮帮忙看一下，谢了先。 |
C***y
发帖数: 2546 | 2 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，该怎样快速诊断出可能的原因？
: 这几个题我一个都没有答上来，请大家帮帮忙看一下，谢了先。
|
j***y
发帖数: 2074 | 3
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***y
发帖数: 2546 | 4 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。很好的机会被我浪费了，还是弱。
|
f***g
发帖数: 214 | |
j***y
发帖数: 2074 | 6
不明白这个xor解法的原理是什么，可以简单讲一下或给个参考文献吗？
【在 f***g 的大作中提到】
: 两个仍然用xor
: 不然很可能溢出
|
f***g
发帖数: 214 | 7 没找到，我试着讲一下：
仍然按照Chevy的方法做
如果是一个数：
最后的结果就是 M
如果是两个数：结果就是M1 xor M2
从这个结果中挑一个bit为1的，就可以把原数组划分为两组。missing numbers分别在
这两个组中。
按照1个数的方法再分别做一遍。
据说这个思路可以扩展到3个，4个数去
有个类似的http://geeksforgeeks.org/?p=2457 |
e*****e
发帖数: 1275 | |
j***y
发帖数: 2074 | 9
啊，这个重要的xor的性质我忘记了，谢谢提醒。
【在 e*****e 的大作中提到】
: A xor A = 0
|
j***y
发帖数: 2074 | 10
知道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**********e
发帖数: 1145 | 11 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***y
发帖数: 2074 | 12 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****v
发帖数: 84 | 13 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，该怎样快速诊断出可能的原因？
: 这几个题我一个都没有答上来，请大家帮帮忙看一下，谢了先。
|
i**9
发帖数: 351 | 14
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{
hash[a[i]]=1;
}
}
int j=0;
int i=0;
while(i
while(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，该怎样快速诊断出可能的原因？
: 这几个题我一个都没有答上来，请大家帮帮忙看一下，谢了先。
|
j***y
发帖数: 2074 | 15
谢谢啊。这两天我也在学习hashtable的方法，刚好看到C++里面有个map可以用。
调试了一下你的程序，稍作调整后的code如下：
－－－
#include
//#include
#include |
r*******e
发帖数: 7583 | 16 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
|
j***y
发帖数: 2074 | 17
多谢，确实是这个问题。我的疏忽。改成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*****e
发帖数: 792 | 18 怎么扩展到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
|
r*******e
发帖数: 7583 | 19 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，也是有通不过这个模板类的编译。
: 为什么呢？
|
