google秋季校招的一套笔试题求解
google秋季校招的一套笔试题求解
1 小组赛，每个小组有5支队伍，互相之间打单循环赛，胜一场3分，平一场1分，
输一场不得分，小组前三名出线，平分抽签。问一个队最少拿几分就有理论上的出线希
望
：
A.1
B.2
C.3
D.4
2 用二进制来编码字符串“abcdabaa”,需要能够根据编码，解码回原来的字符串，
最少需要多长的二进制字符串？
A.12
B.14
C.18
D.24
3 一下程序是用来计算两个非负数之间的最大公约数：
long long gcd(long long x, long long y){
if( y==0) return 0;
else return gcd (y, x%y);
}
我们假设x,y中最大的那个数的长度为n，基本运算时间复杂度为O（1），那么该程序
的时间复杂度为：
A.O(1)
B.O(logn)
C.O(n)
D.O(n^2)
4 写函数，输出前n个素数。函数原型：void print_prime(int N); 不需要考虑整
数溢出问题，也不许使用大数处理算法。
5 长度为n的数组乱序存放着0至n-1. 现在只能进行0与其他数的swap，请设计并实
现排序（ 必须采用交换实现）。
6 给定一个原串和目标串，能对原串进行如下操作：
1 在给定位置插入一个字符
2 替换任意字符
3 删除任意字符
要求写一个程序，返回最少的操作数，使得原串进行这些操作后等于目标串。原串和
目标串长度都小于2000.
[解决办法]
第三题是辗转相除法，复杂度O(1)
[解决办法]
#include <stdio.h>
#include <stdlib.h>
#define MAX 10
void swap_zero(int* s)
{
if(s[0] == 0)
{
return;
}
else
{
int i =1;
for(i; i<MAX; i++)
{
if(s[i] == 0)
{
s[i] = s[0];
s[0] = 0;
break;
}
}
}
}
void swap(int* s, int i, int j)
{
if(s[i] > s[j])
{
s[0] = s[i]; //s[0] == 0
s[i] = 0;
s[i] = s[j]; //s[i] == 0;
s[j] = 0;
s[j] = s[0]; //s[j] == 0;
s[0] = 0;
}
}
void bubble_sort(int* s)
{
int i = 0;
for(i; i<MAX; i++)
{
int j = i+1;
for(j; j<MAX; j++)
{
swap(s, i, j);
}
}
}
int main()
{
int s[MAX] = {6,2,3,0,8,4,1,7,5,9};
swap_zero(s);
bubble_sort(s);
int i = 0;
for(i; i<MAX; i++)
{
printf("%d\n", s[i]);
}
return 0;
}
