网易、小米、华为历年笔试面试60题


## 网易 ##

1、两个圆相交,交点是A1,A2。现在过A1点做一直线与两个圆分别相交另外一点B1,B2。B1B2可以绕着A1点旋转。问在什么情况下,B1B2最长?

2、Smith夫妇召开宴会,并邀请其他4对夫妇参加宴会。在宴会上,他们彼此握手,
并且满足没有一个人同自己握手,没有两个人握手一次以上,并且夫妻之间不握手。
然后Mr. Smith问其它客人握手的次数,每个人的答案是不一样的。求Mrs Smith握手的次数?

3、有6种不同颜色的球,分别记为1,2,3,4,5,6,每种球有无数个。现在取5个球,求在以下的条件下:
1). 5种不同颜色,
2). 4种不同颜色的球,
3). 3种不同颜色的球, 
4). 2种不同颜色的球,
它们的概率。

4、有一次数学比赛,共有A,B和C三道题目。所有人都至少解答出一道题目,总共有25人。在没有答出A的人中,答出B的人数是答出C的人数的两倍;单单答出A的人,比其他答出A的人总数多1;在所有只有答出一道题目的人当中,答出B和C的人数刚好是一半。求只答出B的人数?

5、输入一个链表的头结点,从尾到头反过来输出每个结点的值。链表结点定义如下:
struct ListNode
{
  int  m_nKey;
  ListNode* m_pNext;
};


6、题意很简单,写一个程序,打印出以下的序列。
(a),(b),(c),(d),(e)........(z)
(a,b),(a,c),(a,d),(a,e)......(a,z),(b,c),(b,d).....(b,z),(c,d).....(y,z)
(a,b,c),(a,b,d)....(a,b,z),(a,c,d)....(x,y,z)
....
(a,b,c,d,.....x,y,z)(思路:全排列问题)

7、给一个有序数组array[n],和一个数字m,判断m是否是这些数组里面的数的和。

8、对于一个内存地址是32位、内存页是8KB的系统。0X0005F123这个地址的页号与页内偏移分别是多少。

9、如果X大于0并小于65536,用移位法计算X乘以255的值为:-X+X<<8
X<<8-X是不对的,X<<8,已经把X的值改变了(订正:X<<8是个临时变量,不会改变X的值,就像a+1不会改变a一样)。

10、一个包含n个节点的四叉树,每个节点都有四个指向孩子节点的指针,这4n个指针中有   3n+1   个空指针。

11、以下两个语句的区别是什么:
int *p1 = new int[10];  
2.int *p2 = new int10;  

12、计算机在内存中存储数据时使用了大、小端模式,请分别写出A=0X123456在不同情况下的首字节是,大端模式:0X12           小端模式:0X56           X86结构的计算机使用  小端    模式。

13、在游戏设计中,经常会根据不同的游戏状态调用不同的函数,我们可以通过函数指针来实现这一功能,请声明一个参数为int *,返回值为int的函数指针:
int (*fun)(int *)

14、在一冒险游戏里,你见到一个宝箱,身上有N把钥匙,其中一把可以打开宝箱,假如没有任何提示,随机尝试,问:
1). 恰好第K次(1=<K<=N)打开宝箱的概率是多少。
2). 平均需要尝试多少次。

15、判断一个数字序列是BST后序遍历的结果,现场写代码。
来源:http://blog.csdn.net/hopeztm/a ... 01028

16、1-9,9个数组成三个三位数,且都是完全平方数(三个三位数 占据 9个数)求解法。
点评@林晚枫&归云见鸿:
(a*10+b)(a*10+b)
100a^2+20ab+b^2
a 属于 [1,2,3]
a=3,b=1 31  961,
a=2,b=3 23  529 400+40b+b^2 
        25  625
        27  729
        28  784
        29  841
a=1,b=3 13  169  100+20b+b^2
        14  196
        16  256
        17  289
        18  324
        19  361
=>最终唯一解  529  784 361
具体代码如下(3个for循环,然后hash):

6.jpg


17、英雄升级,从0级升到1级,概率100%。
从1级升到2级,有1/3的可能成功;1/3的可能停留原级;1/3的可能下降到0级;
从2级升到3级,有1/9的可能成功;4/9的可能停留原级;4/9的可能下降到1级。
每次升级要花费一个宝石,不管成功还是停留还是降级。
求英雄从0级升到3级平均花费的宝石数目。
点评:题目的意思是,从第n级升级到第n+1级成功的概率是(1/3)^n(指数),停留原级和降级的概率一样,都为[1-(1/3)^n]/2)。

18、将一个很长的字符串,分割成一段一段的子字符串,子字符串都是回文字符串。
有回文字符串就输出最长的,没有回文就输出一个一个的字符。
例如:
habbafgh
输出h,abba,f,g,h。
点评:编程艺术第十五章有这个回文问题的解答,参见:http://blog.csdn.net/v_july_v/ ... 12171。此外,一般的人会想到用后缀数组来解决这个问题,其余更多的方法请见:http://dsqiu.iteye.com/blog/1688736。最后,还可以看下这个链接:http://www.51nod.com/question/ ... 3D672

19、简述你对数据与处理的认识。

20、简述你对中文分词的理解,说明主要难点和常用算法。

21、常见的分类算法有哪些。

22、简述K-MEANS算法。

23、设计一个智能的商品推荐系统。

24、简述你对观点挖掘的认识。

25、HashMap与HashTable区别
点评:HashMap基于Hashtable实现,不同之处在于HashMap是非同步的,并且允许null,即null value和null key,Hashtable则不允许null,详见:http://oznyang.iteye.com/blog/30690。此外,记住一点:hashmap/hashset等凡是带有hash字眼的均基于hashtable实现,没带hash字眼的如set/map均是基于红黑树实现,前者无序,后者有序,详见此文第一部分:http://blog.csdn.net/v_july_v/ ... 82693
不过,估计还是直接来图更形象点,故直接上图:

7.jpg


26、怎么判断单链表有没有环。

27、怎么判断两个无环单链表是否相交。

28、101个硬币中有一个假币,有一个无砝码的天平,称两次,判断假币比真币重还是轻。

29
Class A{  
....  
};  
A *pa = new A();  
A *pas = new ANUM;  
  
delete []pas;                //详细流程  
delete []pa;                //会发生什么  
delete pas;                //哪些指针会变成野指针  
2). 为什么不建议经常手动new和delete而以内存池取代
3). malloc函数本身涉及的几种系统调用
4). 内存分配算法伙伴算法

30、任意2n个正整数,从其中选出n个整数,使得选出的n个整数和同剩下的n个整数之和的差最小。

## 小米 ##

1、字符串重组
输入:****a * b * c*.....
输出:*******abc.....
将所有的*都移动到字符串的前半部分,字符移动到后半部分,保证字符的顺序。

2、电影院座位分布是这样,第一排座位号1-5共5个座位,中间是过道,然后6-12共7个座位,第2排13号座位近邻12号座位后面,即首尾相连状,一共30排。共计360个座位。
现在有3个大人和2个小孩一起去看电影,买票有个要求:
1). 5个座位号必须相连(像11 12 13 14 15这样跨排也算);
2). 过道的座位(像1 5 6 12 13等)必须让大人做,不能让小孩做;
3). 小孩的旁边必须有个大人;
问一共有多少种买票方案,必须写出计算的伪代码?

3、给定一个由N个整数元素组成的数组arr,数组中有正数也有负数,这个数组不是一般的数组,其首尾是相连的。数组中一个或多个连续元素可以组成一个子数组,其中存在这样的子数组arr[i],…arr[n-1],arr[0],…,arr[j],现在请你这个ACM_Lover用一个最高效的方法帮忙找出所有连续子数组和的最大值(如果数组中的元素全部为负数,则最大和为0,即一个也没有选)。
输入:
输入包含多个测试用例,每个测试用例共有两行,第一行是一个整数n(1=<n<=100000),表示数组的长度,第二行依次输入n个整数(整数绝对值不大于1000)。
输出:
对于每个测试用例,请输出子数组和的最大值。
样例输入:
6
1 -2 3 5 -1 2
5
6 -1 5 4 -7
样例输出:
10
14

4、两个多项式为:
pa = an*x^n + an-1*x^(n-1) + ... + a1*x + a0;
pb = bm*x^n + bm-1*x^(n-1) + ... + b1*x + b0;
其中,an,an-1...a1,a0,bm,bm-1...b1,b0都是整数,范围是[-1000,1000],0<=n,m<=1000。
pa * pb的结果也是多项式,请你设计如何表示一个多项式,并写出两个多项式相乘的程序。
c++:
string multiplyPloynomial(const string&pA,const string&pB);
java:
String multiplyPloynomial(String pA,String pB);
其中pA和pB的格式都是“(-3,5),(87,4),(93,3),(3,0)”,表示一个多项式为-3*x^5 + 87*x^4 + 93*x^3 + 3。
输入都是合法的,除了数字,左右括号和逗号没有别的任何字符,并且幂次都是从高到低排列的,输出也要求是这样的标准格式。

5、给一个浮点数序列,取最大乘积子序列的值,例如 -2.5,4,0,3,0.5,8,-1,则取出的最大乘积子序列为3,0.5,8。

6、一个数组里,数都是两两出现的,但是有三个数是唯一出现的,找出这三个数。

7、括号序列由(){}[]组成,例如(([{}]))()这样的序列式合法的,(}{)或者(}(}或者({)}就是不合法的序列。要求用程序实现:
1). 判断一个括号序列是否合法
Boolean isValidSeq(String input){}
2). 如果一个序列不合法,请加入最少的括号数,将这个序列变成合法的。
String fixSeq(String input){}

8、问:最后程序输出是多少?
void fun()  
{  
    unsigned int a = 2013;  
    int b = -2;  
    int c = 0;  
    while (a + b > 0)  
    {  
        a = a + b;  
        c++;  
    }  
    printf("%d", c);  



9、给定一个浮点数的序列,F1,F2,F3,...Fn(1<=n<=1000),定义P(s,e)(1<=s<=e<=n)为子序列Fi(s=<i<=e)的所有元素的乘积。写一个函数,求P的最大值。输入保证对任意s,e,p不会超过double能表示的数据范围。

10、假如已知有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[])
Java:
Int friends(int n,int m,int[][]r)

11、一共有100万,抽中的2万,每月增加4万,问20个月能抽中的概率为:?

12、 for(int i=0;i<strlen(s);i++){n+=I;}时间复杂度O(n)。

13、手机wifi(A)….wifi ap….局域网(B)…..路由器…ADSL(C)…..互联网…..服务器
  断掉上述ABC哪些点TCP链接会立刻断掉?

14、12345入栈,出栈结果 21543 31245 43215 12534 可能的为?(第一个和第三个)

15、x^n+a1x^n-1+…+an-1x+an,最少要做—乘法?题目中a1,a2,an为常数。

16、一场星际争霸比赛,共8个人,每个人的实力用分数表示,要分成两队,如何保证实力最平均?给定一个浮点数的序列,F1,F2,……,Fn(1<=n<=1000),定义P(s,e)为子序列Fi(s<=i<=e)的积,求P的最大值。

17、数组里找到和最接近于0的两个值。

18、行列有序的矩阵查找一个数。

19、直方图最大矩形。
点评:这里有此题的具体表述及一份答案:http://blog.csdn.net/xybsos/ar ... 49048
 
20、字符串匹配 含有* ? (写代码)
 
21、给出一个int数组,通过变换使得左边全为奇数右边全为偶数。

22、给出一颗有序二叉树,将它转换为有序的双向链表输出。
有序二叉树形如:
          10
          /   \
        6     14
      /   \    /    \
    4    8 12  16
双向链表形如:
4=6=8=10=12=14=16

23、字符串的四则运算。给出一个字符串,包含0~9的数字和+-*/()的运算符,-仅代表减号不代表负数。举例如下:
输入:1+2*(3-4)
输出:-1.
参考分析见:http://www.itmian4.com/forum.p ... D3713

## 华为 ##

1、char *str = "AbcABca";
写出一个函数,查找出每个字符的个数,区分大小写,要求时间复杂度是n(提示用ASCⅡ码)

2、请使用代码计算1234567891011121314151617181920*2019181716151413121110987654321 。

3、1分2分5分的硬币,组成1角,共有多少种组合。

4、选秀节目打分,分为专家评委和大众评委,score[] 数组里面存储每个评委打的分数,judge_type[] 里存储与 score[] 数组对应的评委类别,judge_type == 1,表示专家评委,judge_type == 2,表示大众评委,n表示评委总数。打分规则如下:专家评委和大众评委的分数先分别取一个平均分(平均分取整),然后,总分 = 专家评委平均分 * 0.6 + 大众评委 * 0.4,总分取整。如果没有大众评委,则 总分 = 专家评委平均分,总分取整。函数最终返回选手得分。
函数接口 int cal_score(int score[], int judge_type[], int n)  
 上机题目需要将函数验证,但是题目中默认专家评委的个数不能为零,但是如何将这种专家数目为0的情形排除出去。
来源:http://topic.csdn.net/u/201209 ... .html

5、将一个普通的二叉树转换为二叉排序树?

6、随便写一个排序算法。

7、通过键盘输入一串小写字母(a~z)组成的字符串。请编写一个字符串压缩程序,将字符串中连续出席的重复字母进行压缩,并输出压缩后的字符串。
压缩规则:
1). 仅压缩连续重复出现的字符。比如字符串"abcbc"由于无连续重复字符,压缩后的字符串还是"abcbc"。
2). 压缩字段的格式为"字符重复的次数+字符"。例如:字符串"xxxyyyyyyz"压缩后就成为"3x6yz"。
要求实现函数: 
     void stringZip(const char *pInputStr, long lInputLen, char *pOutputStr);
    输入pInputStr:  输入字符串lInputLen:  输入字符串长度
    输出 pOutputStr: 输出字符串,空间已经开辟好,与输入字符串等长;
注意:只需要完成该函数功能算法,中间不需要有任何IO的输入输出
示例 
    输入:“cccddecc”   输出:“3c2de2c”
    输入:“adef”     输出:“adef”
    输入:“pppppppp” 输出:“8p”
已邀请:

金哈哈哈哈哈

赞同来自:


献丑试试第一题。

我才不会告诉你们,刚才专门请教了我的初中生表弟。

要回复问题请先登录注册

收藏七月在线,一起向大牛进阶

ctrl+D或command+D可以快速收藏哦~