招聘笔试题

人人网算法类笔试题和面试题答案汇总

如下为大家汇总的内容是人人网算法类笔试题,感兴趣的朋友可以练习下。
1.给出一个有序数组啊,长度为len,另外给出第三个数X,问是否能在数组中找到两个数,这两个数之和等于第三个数X。

我们首先看到第一句话,这个数组是有序的,所以,我们可以定义两个指针,一个指向数组的第一个元素,另一个指向应该指向的位置(这个需要看具体的实现和数组给定的值),首先计算两个位置的和是否等于给定的第三个数,如果等于则算法结束,如果大于,则尾指针向头指针方向移动,如果小于,则头指针向尾指针方向移动,当头指针大于等于尾指针时算法结束,没有找到这样的两个数。

解法一:

#include

int judge(int a, int len, int k, int num1, int num2);

int main(int argc, char argv)

{

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 %d ", num1, num2);

}

else if(result == -1)

{

printf("can't 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))

{

cout<<"Yes"<

}

else

{

cout<<"No"<

}

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 Complexity: O(n)

Space Complexity:O(1) 更多热门的笔试题目推荐:
中国人民银行的笔试题
上海东方传媒集团笔试题
广东北电研发工程师笔试题
金融投资顾问常考笔试题目

大家都在看