2013年小米校园招聘笔试题

[工商银行2014校园招聘笔试经验]考完出来就在朋友圈声讨工行今次太不人道了!!!!后来坐车人都浑浑噩噩的，直到吃个饱饭后才来上网，看到网友戏称诺鑫银行突然很无奈笑了。先说说整个考试的流程。提前来到考场，...+阅读

一、填空题(5分每题，一共8题)

1、两个人A(速度为a)、B(速度为b)在一直路上相向而行。在A、B距离为s的时候，A放出一个鸽子C(速度为c)，C飞到B后，立即掉头飞向A，遇到A在掉头飞向B......就这样在AB之间飞来飞去，直到A、B相遇，这期间鸽子共飞行路程为?

答案是：s*c/(a+b)

2、(he)的平方=she。h、e、s代表的数字?

答案是：分别代表

2、

5、6

3、运算(93-8)的结果为：88

4、将一个无序整数数组构造成一个最大堆，最差时间复杂度为：

5、int *p = n;

那么*p的值是()

A、p的值 B、p的地址 C、n的值 D、n的地址

6、一个完全二叉树有770个节点，那么其叶子的个数为：385

7、有一个二维数组a[1...100 , 1...65]有100行，65列，我们以行序为主序，如果该数组的基地址是10000，且每个元素占2个存储单元，请问a[56 , 22]的存储地址是：17324

8、以下代码输出结果是：

[cpp] view plaincopyprint?

class B

{

public:

B()

{

coutB constructor\n;

s = B;

}

void f()

{

cout

}

private:

string s;

};

class D : public B

{

public:

D() : B()

{

coutD constructor\n;

s = D;

}

void f()

{

cout

}

private:

string s;

};

int main(void)

{

B *b = new D();

b-f();

((D*)b)-f();

delete b;

return 0;

}

class B

{

public:

B()

{

coutB constructor\n;

s = B;

}

void f()

{

cout

}

private:

string s;

};

class D : public B

{

public:

D() : B()

{

coutD constructor\n;

s = D;

}

void f()

{

cout

}

private:

string s;

};

int main(void)

{

B *b = new D();

b-f();

((D*)b)-f();

delete b;

return 0;

}

输出结果是

B constructor

D constructor

二、编程题

1、数组乘积(15分)

输入：一个长度为n的整数数组input

输出：一个长度为n的整数数组result，满足result[i] = input数组中除了input[i]之外所有数的乘积(假设不会溢出)。

比如输入：input = {2,3,4,5}，输出result = {60,40,30,24}

程序时间和空间复杂度越小越好。

C/C++：

int *cal(int* input , int n);

Ja:

int[] cal(int[] input);

[cpp] view plaincopyprint?

int *cal(int* input , int n)

{

int i ;

int *result = new int[n];

result[0] = 1;

for(i = 1 ; i n ; ++i)

result[i] = result[i-1]*input[i-1];

result[0] = input[n-1];

for(i = n-2 ; i 0 ; --i)

{

result[i] *= result[0];

result[0] *= input[i];

}

return result;

}

int *cal(int* input , int n)

{

int i ;

int *result = new int[n];

result[0] = 1;

for(i = 1 ; i n ; ++i)

result[i] = result[i-1]*input[i-1];

result[0] = input[n-1];

for(i = n-2 ; i 0 ; --i)

{

result[i] *= result[0];

result[0] *= input[i];

}

return result;

}

2、异形数(25分)

在一个长度为n的整形数组a里，除了三个数字只出现一次外，其他的数字都出现了2次。

请写程序输出任意一个只出现一次的数字，程序时间和空间复杂度越小越好。

例如： a = {1,3,7,9,5,9,4,3,6,1,7}，输出4或5或6

C/C++：

void find(int* a , int n);

Ja:

void find(int[] a);

[cpp] view plaincopyprint?

lowbit表示的是某个数从右往左扫描第一次出现1的位置

int lowbit(int x)

{

return x~(x-1);

}

void find(int* a , int n)

{

int i , xors;

xors = 0;

for(i = 0 ; i n ; ++i)

xors ^= a[i];

三个数两两的异或后lowbit有两个相同，一个不同，可以分为两组

int fips = 0;

for(i = 0 ; i n ; ++i)

fips ^= lowbit(xors ^ a[i]);

表示的是：flips=lowbit(a^b)^lowbit(a^c)^lowbit(b^c)

int b; 假设三个只出现一次的其中一个数为b

b = 0;

for(i = 0 ; i n ; ++i)

{

if(lowbit(xors ^ a[i]) == fips)

b ^= a[i];

}

成功找到三个数中一个数

cout

}

lowbit表示的是某个数从右往左扫描第一次出现1的位置

int lowbit(int x)

{

return x~(x-1);

}

void find(int* a , int n)

{

int i , xors;

xors = 0;

for(i = 0 ; i n ; ++i)

xors ^= a[i];

三个数两两的异或后lowbit有两个相同，一个不同，可以分为两组

int fips = 0;

for(i = 0 ; i n ; ++i)

fips ^= lowbit(xors ^ a[i]);

表示的是：flips=lowbit(a^b)^lowbit(a^c)^lowbit(b^c)

int b; 假设三个只出现一次的其中一个数为b

b = 0;

for(i = 0 ; i n ; ++i)

{

if(lowbit(xors ^ a[i]) == fips)

b ^= a[i];

}

成功找到三个数中一个数

cout

}

3、朋友圈(25分)

假如已知有n个人和m对好友关系(存于数字r)。

如果两个人是直接或间接的好友(好友的好友的好友...)，则认为他们属于同一个朋友圈，请写程序求出这n个人里一共有多少个朋友圈。

假如：n = 5 ， m = 3 ， r = {{1 , 2} , {2 , 3} , {4 , 5}}，表示有5个人，1和2是好友，2和3是好友，4和5是好友，则

1、

2、3属于一个朋友圈，

4、5属于另一个朋友圈，结果为2个朋友圈。

最后请分析所写代码的时间、空间复杂度。评分会参考代码的正确性和效率。

C/C++：

int friends(int n , int m , int* r[]);

Ja:

int friends(int n , int m , int[][] r);

[cpp] view plaincopyprint?

简单的并查集应用

int set[10001];

inline int find(int x) 带路径优化的并查集查找算法

{

int i , j , r;

r = x;

while(set[r] != r)

r = set[r];

i = x;

while(i != r)

{

j = set[i];

set[i] = r;

i = j;

}

return r;

}

inline void merge(int x , int y) 优化的并查集归并算法

{

int t = find(x);

int h = find(y);

if(t h)

set[h] = t;

else

set[t] = h;

}

int friends(int n , int m , int* r[])

{

int i , count;

for(i = 1 ; i = n ; ++i) 初始化并查集，各点为孤立点，分支数为n

set[i] = i;

for(i = 0 ; i m ; ++i)

merge(r[i][0] , r[i][1]);

count = 0;

for(i = 1 ; i = n ; ++i)

{

if(set[i] == i)

++count;

}

return count;

}