google秋天校招的一套笔试题求解

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)
[解决办法]

引用:

引用:第二题，赫夫曼编码出来是
a:1
b:01
c:000
d:001
那么选B
不知道有什么更牛逼些的编码？这是哪方面的知识

哈夫曼编码，数据结构里的。
[解决办法]
最后一题，动态规划经典题
[解决办法]
标记一下：
1.最坏开始，1分输三人，最差也有三人能拿三分了，顶多第四名，排除。2分平两局，输两局，就是说有两个人肯定>=3分占2人了还有一名额，三人都平局2输2，抽签有希望赢
2.只想到哈夫曼编码，（等大神学习更牛的编码）
3.排除法选 b 不懂怎么算。。。（回去恶补。。）
4.蛮力法。。。可以优化一点点的把，不懂更好的了（等大神学习）
5.先找到0放到a[0] , 然后快排，交换每次都通过a[0] 就不违规把（等大神指教）
6.貌似只能动态规划吧。。不过没具体思路了。。（等大神学习。。。）
[解决办法]
第一题的话：每个人一共打4局，总共10局比赛，我们看最终分数，每局可能得到分数为0,1,3，根据得分分析胜败
设定当前得分人称A，其他4人BCDE。
1分：
平1局，输3局了，肯定挂掉。
2分：
那肯定是平2局，输2局了，有2个哥们BC赢了他令2个哥们DE跟他平手，DE这2哥们中至少赢一局的话前3名就没A什么事了，机会不是很大，还是有机会的,我们来看一下DE哥们继续比赛的话会不会比A输的更惨，接下来还有4个人6场比赛，既然比输的惨那么D->BC和E->BC的4场比赛DE全部输掉最后剩下2场比赛一场是BC巅峰对决一场是DE争夺老三现在BC情况一样都是平1场输2场BC，对决有2种情况，有人赢再不就是平局，有人赢的话老三肯定没有A啥事了，但是平局的话ABC最终都是2分，好吧最终3个人抽签决定谁当老三，机会还是有的。。。
3分：
平3局输1局
[解决办法]
赢1局输3局
4分：
平4局
[解决办法]
赢1局平1局输2局
我们从低分开始寻找A的一丝出现的可能，2分就够了，3,4分就不用多说了。
[解决办法]
第五题，写了个耍哈。

#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;

#define MAX 10

void swap_zero(int* s)
{
  if(s[0] ==  0)
  {
      return;
  }
  else
  {
      int i =1; 
 
      for(i; i&lt;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] &gt; 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&lt;MAX; i++)
    {
        int j = i+1;
        for(j; j&lt;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&lt;MAX; i++)
    {
        printf("%d\n", s[i]);
    }
    return 0;
}

[解决办法]

引用:

引用:第二题，赫夫曼编码出来是
a:1
b:01
c:000
d:001
那么选B
不知道有什么更牛逼些的编码？赫夫曼编码对吗？Ｃ不是００１Ｄ０００１吧

他的思路是对的，只是和标准的方法弄反了。标准的做法是二叉树的左枝标0右枝标1
0/\1
a 0/\1
b 0/\1
c d
a:0 b:10 c:110 d:111

google秋天校招的一套笔试题求解

热点推荐