现在的位置: 首页 > 综合 > 正文

Google2012笔试题感想

2013年04月18日 ⁄ 综合 ⁄ 共 2062字 ⁄ 字号 评论关闭

一、选择

1、哪些不是加密算法?(MD5)

A、MD5     B、DES      C、RC4      D、RSA

2、垃圾回收相关表述错误?(B、计数引用不能处理循环引用,但垃圾回收可以,所以A没错)

A、垃圾回收可以处理循环引用

B、垃圾回收就不会有内存泄漏

3、最大生成树题(Kruskal按边排序,取不形成环的最大边即可)

4、5个a,3个b,2个c排列,其中包括abc子串的共有?(注意重复)

5、树最少去掉几个节点形成非连通图?(1个)

6、关于内核描述错误的是(D)

D、文件系统和驱动一定属于内核

总结:10个选择题,目前已经确定错了3个。

二、编程题

1、环形公路,D中存i,i+1距离,给任意i,j,求i,j最短距离。

2、字符串处理,压缩空格,字串反转。如"abc def     gk"=>"cba fed kg"

3、多种面值的纸币找零一个面值的方法数,标准硬币找零问题。

参考代码:

1、

#include <stdio.h>
#include <string.h>

const int N = 8;
double D[N]={5,4,3,8,2,1,9,6};
int n = sizeof(D)/sizeof(double);

void pre()
{
#ifdef DEBUG
	for(int i=0;i<n;i++)
		printf("D%d:%lf\n", i, D[i]);
#endif
	double tmp[N+1];
	memset(tmp,0,sizeof(int)*N);
	for(int i=1;i<n;i++)
		for(int j=i+1;j<=n;j++)
			tmp[j]+=D[i];
	D[0]+=tmp[n];
	memcpy(D+1,tmp+2,sizeof(double)*(N-1));
#ifdef DEBUG
	printf("All:%lf\n", D[0]);
	printf("1 to 1:0\n");
	for(int i=1;i<n;i++)
		printf("1 to %d:%lf\n", i+1, D[i]);
#endif
}
double dis(int i, int j)
{
	int a = i>j?j:i;
	int b = i>j?i:j;
	if(i==j || i<=0 || i>N || j<=0 || j>N)
		return 0;
	int db, da;
	db = b-1==0?0:D[b-1];
	da = a-1==0?0:D[a-1];
	double d1 = db-da;
	double d2 = D[0]-d1;
	return d1>d2?d2:d1; 
}
int main()
{
	int a = 1, b = 3;
	pre();
	printf("\nans:%d to %d:%lf\n", a, b, dis(a,b));
	a = 2, b = 5;
	printf("\nans:%d to %d:%lf\n", a, b, dis(a,b));
	
	return 0;
}

2、

#include <stdio.h>

void print(const char* s)
{
	bool space_flag = true;
	const int N = 1024;
	char buf[N];
	int i,j;
	i = j = 0;
	while(s[i]!='\0')
	{
		if(s[i]!=' ')
		{
			buf[j++]=s[i];
			space_flag = true;
		}else if(space_flag)
		{
			buf[j]='\0';
			for(int k=0;k<(j-1)/2;k++){
				char tmp = buf[k];
				buf[k]=buf[j-1-k];
				buf[j-1-k]=tmp;
			}
			printf("%s ", buf);
			buf[0]='\0';
			j=0;
			space_flag = false;
		}
		i++;
	}
	buf[j]='\0';
	printf("%s\n", buf);
}
int main()
{
	const char* str="abc  def gk";
	print(str);
	return 0;
}

3、

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

int value[]={1,2,5,10};
int size = sizeof(value)/sizeof(int);

int foo(int n)
{
	int* c[size+1];
	for(int i=0;i<size+1;i++)
		c[i]=(int*)calloc((n+1),sizeof(int));
	for(int i=0;i<=n;i++){
		c[0][i] = i%value[0]==0?1:0;
	}
	for(int i=1;i<size;i++)
		for(int j=0;j<=n;j++)
			for(int k=0;k<=j/value[i];k++)
			c[i][j]+=c[i-1][j-k*value[i]];
	int ans = c[size-1][n];
	for(int i=0;i<size+1;i++)
		free(c[i]);
	return ans;
}
int main()
{
	for(int i=0;i<7;i++){
		int a = (double)pow(10,i);
		printf("%d\t%d\n",a,foo(a));
	}

	return 0;
}

抱歉!评论已关闭.