[2015KPMG毕马威笔试经验]先说一下我背景吧，我是上海复旦大学旁边的某个知名财经大学的学生，专业是工商管理，成绩一般般，在工商管理班是属于倒数的，不过放到年级上就是前30%的水平，所以填成绩排名时从来只...+阅读
1.给出一个有序数组啊，长度为len，另外给出第三个数X，问是否能在数组中找到两个数，这两个数之和等于第三个数X。
我们首先看到第一句话，这个数组是有序的，所以，我们可以定义两个指针，一个指向数组的第一个元素，另一个指向应该指向的位置(这个需要看具体的实现和数组给定的值)，首先计算两个位置的和是否等于给定的第三个数，如果等于则算法结束，如果大于，则尾指针向头指针方向移动，如果小于，则头指针向尾指针方向移动，当头指针大于等于尾指针时算法结束，没有找到这样的两个数。
解法一：
#include
int judge(int *a, int len, int k, int *num1, int *num2);
int main(int argc, char **ar)
{
int test_array[] = {3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16};
int result = -1;
int num1, num2;
result = judge(test_array, sizeof(test_array) / sizeof(int), 12, num1, num2);
if(result == 0)
{
printf(%d\t%d\n, num1, num2);
}
else if(result == -1)
{
printf(cant find);
}
else
{
printf(error);
}
}
int judge(int *a, int len, int k, int *num1, int *num2)
{
int *low = NULL;
int *high = NULL;
int i = 0;
int result = -1;
if(a == NULL || len 2)
{
return result;
}
if(a[0] = k)
{
return result;
}
while(a[i] = k i len)
{
i++;
}
low = a;
high = a + i - 1;
while(low high)
{
*num1 = *low;
*num2 = *high;
if((*low + *high) == k)
{
result = 0;
break;
}
else if((*low + *high) k)
{
high--;
}
else if((*low + *high) k)
{
low++;
}
}
return result;
}
解法二：
#include
using namespace std;
int hash_table[100];
bool judge(int *a, int len, int x)
{
memset(hash_table, 0, sizeof(hash_table));
for (int i=0; i
{
hash_table[x - a[i]] = 1;
}
for (int i=0; i
{
if (hash_table[i] == 1)
{
return true;
}
}
return false;
}
int main()
{
int len = 10;
int a[10] = {1, 3, 5, 7, 9, 4, 2, 8, 10, 6};
int x = 19;
if (judge(a, len, x))
{
coutYes
}
else
{
coutNo
}
system(pause);
return 0;
}
本题解决方法：hash table。
时间复杂度：O(N)
空间复杂度：O(N)
2.给定有n个数的数组a，其中有超过一半的数为一个定值，在不进行排序，不开设额外数组的情况下，以最高效的算法找出这个数。
int find(int* a, int n);
#include
using namespace std;
int find(int *a, int n)
{
int t = a[0];
int count = 0;
for (int i=0; i
{
if (count == 0)
{
t = a[i];
count = 1;
continue;
}
else
{
if (a[i] == t)
{
count++;
}
else
{
count--;
}
}
}
return t;
}
int main()
{
int n = 10;
int a[10] = {1, 3, 2, 3, 3, 4, 3, 3, 3, 6};
cout
system(pause);
return 0;
}
Time plexity: O(n)
Space plexity:O(1)
延伸阅读：
2015重庆移动校招笔试经验重庆移动重庆地区的校招终于是告一段落了，今天刚好闲下来，想想移动校招这一路走来，还是有所收获，自己也是从前辈的帖子获取了很多信息，所以在这里也跟大家分享下自己一路走来的经...
2015天职国际网测笔试经验我坐标南京，非211非965学校，投的也是南京所。一直很中意天职国际，实习的时候和天职是同一座大厦，那时候就很希望能去楼上工作，所以宣讲会的话特地从江宁跑去浦口去听，还算幸运，简历...
2015中国银行笔试经验分享今年中行笔试时间好早啊!是所有银行中最早的一个了，楼主之前准备了两个月，今天考完的感觉就是、、、都白看了= =超级难!好吧可能有些复习的好的觉得还行吧，废话不多说，直接上。...
衣恋2014笔试经验30日晚广州在中大笔试。 什么文具用品都不用带，现场会发(其实只有一支笔而已，要用修正带可以跟工作人员借)。 hr一上来就跟我们说，这次笔试非常难，甚至有人一道题都做不对什么的...
安永2014年笔试经验分享关于考几道 怎么考 时间巴拉巴拉的就不赘述了 就简单说一下我记得的题目吧 Verbal 比较多以下哪个正确或者以下哪个错误的题目 比较麻烦 难度递增 一篇文章2道题 1. GPS定位...
欢聚时代2017校招产品经理笔试经验今年的笔试是在华工五山校区举行的，风尘仆仆的从大学城赶过去啊!去了之后按照短信的通知找教室，教室里有笔试技术的也有笔试产品的，没有固定位置，但按照一列技术类一列非技术类...
中行2015校园招聘笔试经验我2014年11月1日下午1点30到4点30参加了中国银行2015校招笔试，上午在仙林南邮参加江苏电信笔试，2个小时的时间内赶到了江宁南医参加了中行的考试。以下是考试内容和时间段，都是...
百度2015软件开发工程师笔试题百度的题总体来说不难，都是一些基础的题。好像近几年都有这样的趋势，计算机网络，操作系统，数据库，每个基础课出一道题。接着是三道程序设计题。最后是系统设计题。所以好好看计算...
笔试的几个面试技巧笔试的几个面试技巧1.科学答卷拿到试卷后，首先应通览一追，了解题目的多少和难易程度，以便掌握答题的速度，然后根据先易后难的原则排出答题的顺序、先攻相对简单的题，后攻难题。这...
