谷歌 2021 技术岗位面试题

一、单选题

下列关于整数的说法中哪个是正确的？

A  在采用补码的计算机的系统中，无符号整数和有符号整数很容易区分开

B  在32位系统中计算8位加法会比32位加法快

C  作整数运算时应尽量避免溢出，因为溢出会占用额外的内存，影响系统性能。

D  常见计算机系统中整数除法比乘法慢。

A

第2题：

 按照OSI模型的层次概念，下列几个协议中哪一个协议在协议栈的最底层

A  HTTP

B  FTP

C  IP

D  TCP

 C

OSI模型的体系结构标准定义了网络互连的七层框架（物理层、数据链路层、网络层、传输层、会话层、表示层和应用层）。

HTTP和FTP都属于最高层，应用层

TCP是传输层

IP是网络层，是这几个协议在协议栈的最底层

第3题：

 请阅读下面代码片段并且回答问题：

#define SIZE_20M (20*1024*1024)

void func_a()

{

    char *tmp = malloc(SIZE_20M)

    return;

}

void func_b()

{

    char temp[SIZE_20M];

    //...do something using temp

    return;

}

 
关于这段代码，下列说法正确的是

A  func_a 获得临时内存的方式效率通常更高。

B  func_b 使用了太多的栈，程序可能会在运行时候崩溃。

C  func_b 存在内存泄露

D  func_a 和func_b 分配的内存会自动初始化0

 B

第4题：

 与十进制数28.5625相等的四进制数是

A  121.30

B  221.30

C  121.31

D  130.21

 D

先算整数部分28，做4的除法，倒序写出余数，四进制为130

后算小数部分0.5625，做4的乘法，取出整数部分，得到为0.21

参考进制转换方法

第5题：

 由3个a,5个b和2个c构成的所有长度为10的字符串中，包含子串"abc"的共有几个？

A  40320

B  39600

C  840

D  780

E  60

 D.

一共是780个假定abc为一个单位共有1个abc,
 2个a,4个b和1个c一共8个单位进行含有相同元素的全排列共有8!/1!/2!/4!/1!=840种方法
 含有相同元素的全排列算法
 总元素个数的阶乘依次除以每种元素相同元素的阶乘比如这里的共有1个abc,2个a,4个b和1个c一共8个单位进行含有相同元素的全排列总元素个数的阶乘8!依次除以每种元素相同元素的阶乘abc:1!,a:2!,b:4!,c:1!结果就是8!  /1! /2! /4! /1!=840

其中仍然有重复的就是出现了两个abc的情况
 共有2个abc,1个a和3个b一共6个单位进行含有相同元素的全排列共有6!/2!/1!/3!=60种方法840-60=780

第6题：

 一个有n个结点的连通图的生成树是原图的最小连通子图，且包含原图中所有n个结点，并且有保持图联通的最少的边。最大生成树就是权和最大生成树，现在给出一个无身带权图的邻接矩阵，权为0表示没有边。 ｛{0，4，5，0，3}，{4，0，4，2，3}，{5，4，0，2，0}，{0，2，2，0，1}，{3，3，0，1，0}｝，求这个图的最大生成树的权和。

A  11

B  12

C  13

D  14

E  15

 D

利用kruskal，不同的是，这次我们按照从大到小的顺序，从图中选择边，同时保证选择该边不会与之前选过的边组成一个回路。最终选择5 4 3 2 四条边 

第7题：

 一棵树（>=3个节点）最少需要删掉几个节点才能使得这棵树不连通？

A  0

B  1

C  2

D  3

 B

第8题：

 以下算法不能用于文本加密的是：

A  MD5

B  RSA

C  RC4

D  DES

 A

md5是摘要算法，单向，无法解密，只能用来验证完整性。  

第9题：

 下面关于垃圾收集的描述哪个是错误的？

A  使用垃圾收集的程序不需要明确释放对象

B  现代垃圾收集能够处理循环引用问题

C  垃圾收集能提高程序员效率

D  使用垃圾收集的语言没有内在泄漏问题

 D

也会有内存泄露问题，例如访问资源文件，流不关闭，访问数据库等连接不关闭

第10题：

 下面关于操作系统的概念，哪个是错误的？

A  Micro-kernel和Monolithic-kernel都还是现代操作系统的常用技术

B  操作系统为应用软件提供运行环境

C  操作系统的系统调用是应用软件与操作系统交互的接口

D  文件系统和设备驱动必须运行在内核态

 D

对于文件系统来说，则可以一部分放在用户态，一部分放在内核态。文件系统本身的管理，即文件系统的宏数据部分的管理必须放在内核态，否则任何人都可能破坏文件系统的结构；用户数据的管理则可以放在用户态。

第11题：

 二、问答题

某环形公路上有N个站点，分别记为A1......An，从Ai到A（ i+1）的距离为Di。An到A1的距离为Do，假设Do=Dn=1，保存在数组D（N）中，现在要求你与一个函数，能够高效的计算出公路上任意两点的最近距离，要求空间复杂度不能超过O(N)。

const int N=100;

double D(N);

...

Void preprocess(){

//Write your code here,        (1)

}

double Distance(int i, int j){

// Write your code bere         (2)

}

#include"iostream"

#include"math.h"

#define MAX 100

using namespace std;

int main(int argc, char* argv[])

{

    int N;

    double D[MAX],sum=0,SumD[MAX];

    cin>>N;

    for(int i=0;i

    {

        cin>>D[i];

        sum+=D[i];

        SumD[i] = sum;

    }

    while(true)

    {

        int a,b;

        cin>>a>>b;

        if(a>N||b>N)

            break;

        float temp = fabs(SumD[a-1]-SumD[b-1]);

        cout<<"result: "<<(temp>(sum-temp)?(sum-temp):temp)<

    }

    return 0;

}

第12题：

 给定字符串s, 要求把s中多于一个的连续空压缩成一个空格，并将连续的非空格字符串倒序打印出来，例如，给定"abc def efg"，打印"cba fed gfe"

 说明：两个循环，第一个循环去掉连续空格，第二个循环倒叙输出

void RPutString(char * src,int n)
{

    if(src==null&&n<2) return;

    char * first = src;

    char * second = src;

    for(int i=0;i

    {

        //second 先找到第一个非空格字符串

        if(*second != ' ')

            first++ = second;           

        else//*second==' '

            if(first != src && *(first-1) != ' ')

                first++ = ' ';

        ++second;

    }

    char * Rfirst = NULL;//用于指向新的末尾字符

    //设置结尾标记

    if(*first==' ')

    {

        *first='\0';

        Rfirst = first-1;  

    }

    else

    {

        *(first+1)='\0';

        Rfirst = first;  

    }

    //然后倒叙排列

    char temp;

    first = str;

    while(Rfirst > first)

    {

        temp = Rfirst;

        Rfirst = first;

        first = temp;

        ++first;

        --Rfirst;

    }

    //到此完成，最终字符串中头尾都非空格。

}

第13题：

 给你一个数小于1000000，分别用100,50,20,10,5块表示出来，有多少种表示方法。写出算法即可。

#include

#include

#include

using namespace std;

int base[] = { 5, 10, 20, 50, 100 };

unordered_map store[5];

int getTotal(int num, int index){

    int total = 0;

    if (index == 0)

        return 1;

    int groups = num / base[index];

    for (int i = 0; i <= groups;i++){

        total += getTotal(num - base[index] * i, index - 1);

    }

    store[index].insert(make_pair(num, total));

    return total;

}

int main(){

    int n;

    scanf("%d", &n);

    if (n % 5 != 0||n==0)

        printf("0");

    int i;

    for (i = 4; i >= 0;i--)

        if (n >= base[i])

            break;

    printf("%d", getTotal(n, i));

    system("pause");

    return 0;

}