2014各大网络公司校招笔试算法题(搜集并更新中)
从博客中整理，并不断的更新，供大家学习和交流，随后会给出部分算法题的参考代码。
腾讯
1、请设计一个排队系统，能够让每个进入队伍的用户都能看到自己在 中所处的位置和变化。队伍可能随时有人加入和退出，当有人退出影响到用户的位置排名时需要即时反馈到用户。
2、A、B两个整数集合，设计一个算法求他们的交集，尽可能的高效。
百度
百度2014笔试算法题汇总
科大讯飞
1.求一个整数数组的最大元素，用递归方法实现。
#include <cmath>
using namespace std;
int maxnum(int a[], int n)
{
if(n == 1)
return a[0];
if(n>1)
{
return max(a[0], maxnum(a+1,n-1));
}
}
int main()
{
int num[10] = {0,1,2,3,4,5,6,7,8,9};
cout<<maxnum(num,10)<<endl;
return 0;
}
2.已知一个整数数组A[n]，写出算法实现将奇数元素放在数组的左边，将偶数放在数组的右边。要求时间复杂度为O(n)。
void partition(int A[], int n)
{
int x;
int i = 0;
int j = n-1;
while(i != j)
{
while( a[i]%2 == 1)
i++;
while (a[j]%2 == 0)
j++;
if(i < j)
{
x = a[i];
a[i] = a[j];
a[j] = x;
}
}
}
金山办公
1.[长沙理工站]给定 一个int型的整数，编程输出其LED显示屏形式。如0为：
---
| |
| |
| |
---
每个数字之间用空格分开。
2.[湖南大学站]有一个函数：
void unique(std::vector<int> &v);
用来给数组去重，试写一段测试代码检查其正确性。
提示1：尽可能找出bug
提示2：你的代码应该返回int型，0表示测试通过，1表示出错。
3.有如下函数原型:
void transferToChinese(int num);（ps:函数名记不太清了，但是无关紧要）
该函数把小于一亿的int型数字转换成中文表示，如：
17：一十七；
110：一百一十；
12345：一万两千三百四十五；
10101：一万零一百零一
提示：注意零的情况。
拓展：考虑缩写情况，如：
17：十七
美团网
美团网2014笔试算法题汇总
去哪儿网
1.写一个函数，转换相对路径为绝对路径，比如：/home/abs/../temp/new/../,输出路径为：/home/temp。
2.一个10*10的矩阵（可以理解为棋盘），随时生成一组数据填入矩阵，任何一个位置的数字除4进行计算，按余数着色，余数为0着色为red，1为blue，2为green，3为black，可以理解为生成4中颜色的棋子放入棋盘，如果存在其中同色五星连珠的情况（规则通五子棋），找出任意一组，输出5个棋子的位置下标值。
3.
有两个文件context.txt和words.conf,请尝试将他们合并成为一段文字，并打印出来。
这两个文件内容如下：
context.txt
“并不是每个人都需要$(qunar)自己的粮食，$(flight.1)每个人都需要做自己穿的$(fight.2)，我们说着别人发明的$(hotel)，使用别人发明的数学......我们一直在$(tuan)别人的成果。使用人类的已有经验和知识$(travel.1)来进行，是一件$(travel.2)的事情”
word.conf
flight=也不是：衣服
qunar=种植
hotel=语言
tuan=使用
travel=发明创造：很了不起
4.
一个文件里有10万个随机正整数，按照以下规则能组合出一份新的数据：
A． 如果当前数字能被3整除，那么它和文件中所有数字（包括自己）两两相加后生成一组数字替代自己的位置。
B． 如果不能被3整除，则它只需要乘以二，生成一个数字替代自己的位置。
例如：[3,7,6] 会组合出[6,10,9,14,9,13,12]
再如：[5,12,9,6,2]会组合出[10,17,24,21,18,14,14,21,18,15,11,11,18,15,12,8,4]
写一个程序找出并打印出新数据的最小的前200个数字。请考虑优化算法复杂度。
5.已知字母序列【d, g, e, c, f, b, o, a】，请实现一个函数针对输入的一组字符串 input[] = {"bed", "dog", "dear", "eye"}，按照字母顺序排序并打印。
本例的输出顺序为：dear, dog, eye, bed。
6.有一万个北京单身男女向你提交了基本资料，包括：姓名、性别、年龄、星座，写一段程序尝试找出他们最匹配的一对。华为
华为2014笔试算法题汇总
暴风影音
暴风影音2014笔试算法题汇总
阿里巴巴
1.两棵二叉树T1和T2，T1的节点数是百万量级，T2的节点数一千以内，请给出判断T2是否T1子树的可行算法。
分析：首先想到的是递归，但是T1的数量级太大，递归会导致栈溢出，于是以非递归实现。
bool IsSubtree(BinaryTreeNode* pRoot1, BinaryTreeNode* pRoot2) {
if (pRoot1 == NULL || pRoot2 == NULL) {
return false;
}
stack<BinaryTreeNode*> stk;
stk.push(pRoot1);
while (!stk.empty()) {
BinaryTreeNode *tmp = stk.top();
stk.pop();
if (tmp->m_nValue == pRoot2->m_nValue) {
stack<BinaryTreeNode*> first;
BinaryTreeNode *f;
stack<BinaryTreeNode*> second;
BinaryTreeNode *s;
first.push(tmp);
second.push(pRoot2);
bool find = true;
while (!first.empty()) {
f = first.top();
first.pop();
s = second.top();
second.pop();
if (f->m_nValue != s->m_nValue) {
find = false;
break;
}
if (s->m_pLeft != NULL) {
if (f->m_pLeft == NULL) {
find = false;
break;
} else {
first.push(f->m_pLeft);
second.push(s->m_pLeft);
}
}
if (s->m_pRight != NULL) {
if (f->m_pRight == NULL) {
find = false;
break;
} else {
first.push(f->m_pRight);
second.push(s->m_pRight);
}
}
}
if (find == true && first.empty()) {
return true;
}
}
if (tmp->m_pLeft != NULL) {
stk.push(tmp->m_pLeft);
}
if (tmp->m_pRight != NULL) {
stk.push(tmp->m_pRight);
}
}
return false;
}
从1到500的500个数，第一次删除奇数位，第二次删除剩下来的奇数位，以此类推，最后剩下的唯一一位数是：
A.500 B.256C.250 D.128
3.
人人网
人人网2014笔试算法题汇总
创新工场
1. 堆排序
#include<iostream>
usingnamespace std;
void SwapValue(int &m, int &n)
{
int temp = m;
m = n;
n = temp;
}
void max_heap(vector<int> &vec, int i, int heap_size)
{
int l = 2*i;
int r = 2*i+1;
int largest = i;
if(l<=heap_size && vec[l-1]>vec[largest-1])
largest = l;
if(r<=heap_size && vec[r-1]>vec[largest-1])
largest = r;
if(largest!=i)
{
SwapValue(vec[largest-1],vec[i-1]);
max_heap(vec, largest, heap_size);
}
}
void heapSort(vector<int> &vec)
{
int heap_size = vec.size();
for(int i=heap_size/2; i>=1; i--)
max_heap(vec, i, heap_size);
for(int i=heap_size; i>=1; i--)
{
SwapValue(vec[0],vec[i-1]);
max_heap(vec, 1, i);
}
}
void print(vector<int> vec)
{
for(int i=0; i<vec.size(); i++)
cout<<vec[i]<<" ";
cout<<endl;
}
int main()
{
vector<int> vec;
vec.push_back(23);
vec.push_back(5);
vec.push_back(1);
vec.push_back(10);
vec.push_back(13);
vec.push_back(32);
vec.push_back(21);
vec.push_back(14);
vec.push_back(19);
vec.push_back(20);
cout<<"排序前： "<<endl;
print(vec);
heapSort(vec);
cout<<"排序后： "<<endl;
print(vec);
return 0;
}
2.求一个正整数N的开方，要求不能用库函数sqrt()，结果的精度在0.001
解析：牛顿迭代
#include<iostream>
using namespace std;
int main()
{
int N;
cout<<"输入N的值：";
cin>>N
double x1 = 1;//初值
double x2 = x1/2.0+N/2.0/x1;
while( fabs(x2-x1)>0.001)
{
x1 = x2;
x2 = x1/2.0+N/2.0/x1;
}
cout<<x1<<endl;
return 0;
}
3.给定一个矩阵intmaxtrixA[m][n],每行和每列都是增序的，实现一个算法去找矩阵中的某个元素element.
解法一：
#include<iostream>
using namespace std;
const int M = 4;
const int N = 4;
int main
{
int matrix[M][N] = {};
double element;
int flag = 1;
for(int j=0; j<N; j++)
{
if(matrix[i][j] == element)
cout<<"位置"<<endl;
while( flag<M && matrix[i][j]<element )
--flag;
while( flag<M && matrix[i][j]>element )
++flag;
}
}
解法二：
bool Find(int *matrixA, int m, int n, int element)
{
bool found = false;
if(matrixA != NULL & m & n)
{
int i,j;
i=0;j=n-1;
while(i<m;j>=0)
{
if(maxtrixA[i*n+j] == element)
{
found = true;
break;
}
else if(matrix[i*n+j]>element
--j;
else
++i
}
}
}
优酷
1.N个台阶，1<=N<90,每次一个台阶或两个台阶，求到达台阶N共有多少种方法
2.将long型整数转换成字符串，不能使用库函数
3.含有n个元素的整型数组，将这个n个元素重新组合，求出最小的数，如{321,3,32}，最小的数为 321323
4.有一根27厘米的细木杆，在第3厘米、7厘米、11厘米、17厘米、23厘米这五个位置上各有一只蚂蚁。 木杆很细，不能同时通过一只蚂蚁。开始 时，蚂蚁的头朝左还是朝右是任意的，它们只会朝前走或调头， 但不会后退。当任意两只蚂蚁碰头时，两只蚂蚁会同时调头朝反方向走。假设蚂蚁们每秒钟可以走一厘米的距离。 编写程序，求所有蚂蚁都离开木杆 的最小时间和最大时间。
网易
1、f(0)=0;f(1)=1；f(n)=f(n-1)+f(n-2)，求f（n）。
2、有主字符串A，子字符串B，在A中查找B
3、写出你熟悉的排序算法，并说明其优缺点