科大的google笔试.txt

google的面试题

1. typedef struct {

            Node * node;

}Tree;

 

typedef struct {

           Node * left;

           Node * right;

}Node;

 

请写出深拷贝函数：Tree * deepCopy(Tree *tree);

#include "StructTree.h"

#include <malloc.h>

#include<iostream.h>

Node * copyTree(Node *node);

 
Me的答案：
//之所以分开两个函数是因为 Tree(相当于根)与node是不同的 Tree相单独处理一下
Tree *deepCopy(Tree *tree)
{
	if (tree == NULL)
	{
		return NULL;
	}
	Tree *newtree = new Tree;
	Tree.node = new Node;
	Tree.node->left = copyTree(tree->node->left);
	Tree.node->right = copyTree(tree->node->right);
	retrun newtree;
}

Node *copyTree(Node *oldnode)
{
	Node *newnode;
	if (odlnode== NULL)
	{
		return NULL;
	}
	newnode = New Node;
	newnode->left = copyTree(oldnode->left);
	newnode->right = copyTree(oldnode->right); 
	return newnode;
}


//网上答案 我觉得有问题
Tree *deepCopy(Tree *tree)
{
	if( !tree ) return NULL;

 Tree *re = new Tree;
re->node = tree->node;

re->node->left = copyTree(tree->node->left);

re->node->right = copyTree(tree->node->right);

return re;
}


Node

 * copyTree(Node *node)

{
if( !node ) return NULL;

Node *re = new Node;
re->left = copyTree(node->left);
re->right = copyTree(node->right);

return re;
}

 

void main()

{

   Node *node=new Node;

   node->left=NULL;

   node->right=NULL;

 Tree *tree=new Tree,*tree1=new Tree;

tree->node=node;

tree1=deepCopy(tree);

 

}

 
//据说STL中的函数
2. 输入一个整型数组，对该数组进行随机排序，写出该函数
void randomShuffle(int *a, int len);
可以使用随机函数发生器
int random(int N); //假设是完全的随机函数，返回值是0 - N-1的整数

Me的思路：
void randomShuffle(int *a, int len)
{
 	int num[len];
	int pos;
	for (i=0; i<len; i++)
	{
		num[i] = -1;
	}
	
	for (i=0; i<len; i++)
	{
		pos = random(len+1);
		if (num[pos] == -1)
			num[pos] = len[i];
		else
			i--; 
	}
}
 

法2
void randomShuffle(int *a, int len)
{	
	int i;
	for (i=0; i<len; i++)
	{
		swap(a[i], a[randon(len+1)]);
	}
}


i位的与随机位上的数换
好处：空间复杂度小


3. N个人排成一圈，指定第一个人，去除他，然后跳着一人去除第3人，以次类推，最后
的那一人获胜。给定这N个人和第一个人的位置，你该如何选取位置才会获胜。
让你写最优算法，并计算时间和空间复杂度。不要求写出代码，解释算法即可。

法1：
去掉第一人后，成为真正的约瑟夫环。
设k = N - 1;
公式：
J(K) = 2J(K/2) - 1	//K为偶
J(K) = 2J(K/2) + 1        //K为奇
算出的J(K) + 1即是答案 (加1是为还原回来的序号)

法2：
去掉第一人后，成为真正约瑟夫环。
f[0] = 0
f[i] = (f[i-1] + m) % i
m是步长 i是人数 i的初值从N开取
算出的最终值仍要+1得答案