谷歌 2021 技术岗位面试题

 一、单选题

如果把传输速率定义为单位时间内传送的信息量（以字节计算）多少。关于一下几种典型的数据传输速率：
1.使用USB2.0闪存盘，往USB闪存盘上拷贝文件的数据传输速率
2.使用100M以太网，在局域网内拷贝大文件时网络上的数据传输速率
3.使用一辆卡车拉1000块单块1TB装满数据的硬盘，以100km/h的速度从上海到天津（100km）一趟所等价的数据传输带宽
4.使用电脑播放MP3，电脑的PCI总线到声卡的数据传输速率
在通常情况下，关于这几个传输速率的排序正确的是(  )

A  4<1<2<3

B  1<4<2<3

C  4<1<3<2

D  1<4<3<2

 A

 普通U盘写数据的6MB/s，即48Mbps； 100M以太网的速率就是100Mbps； 卡车拉硬盘，1000x1000x8/3600=2222Mbps，这个应该是最快的； MP3在256kbps码率下也平均只有1分钟2MB，所以不会超过0.3Mbps，所以一定是最慢的。

第2题：

 对以下程序，正确的输出结果是(  )

#include

#define SUB(x,y) x-y

#define ACCESS_BEFORE(element,offset,value) *SUB(&element, offset) = value

int main() {

    int array[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

    int i;

    ACCESS_BEFORE(array[5], 4, 6);

    printf("array: ");

    for (i = 0; i < 10; ++i) {

        printf("%d", array[i]);

    }

    printf("\n");

    return (0);

}

A  array: 1 6 3 4 5 6 7 8 9 10

B  array: 6 2 3 4 5 6 7 8 9 10

C  程序可以正确编译连接，但是运行时会崩溃

D  程序语法错误，编译不成功

 D

第3题：

 在区间[-2, 2]里任取两个实数，它们的和>1的概率是()

A  3/8

B  3/16

C  9/32

D  9/64

 C

第4题：

 小组赛，每个小组有5支队伍，互相之间打单循环赛，胜一场3分，平一场1分，输一场不得分，小组前三名出线。平分抽签。问一个队最少拿()分就有理论上的出线希望：

A  1

B  2

C  3

D  4

 B

\后3名球队两两之间打平，对前两名都输球，依据抽签的运气决出谁是第三名出线

第5题：

 用二进制来编码字符串“abcdabaa”，需要能够根据编码，解码回原来的字符串，最少需要()长的二进制字符串？

A  12

B  14

C  18

D  24

 B

这道题需要对abcd进行Huffman编码。首先根据权值建立Huffman树，得到最优编码：
a=0, b=10, c=110, d=111
然后数一下就行了。

第6题：

 10个相同的糖果，分给三个人，每个人至少要得一个。有()种不同分法

A  33

B  34

C  35

D  36

 D

一共这么几种情况：
118,127,136,145;
226,235,244;
334;
然后有数字重复的算3种排列，不重复的算6种排列，共计4×3+4×6=36种。

第7题：

 下列程序段，循环体执行次数是()：

int y = 2;

while (y <= 8) {

    y = y + y;

}

A  2

B  16

C  4

D  3

 D

第8题：

 下面哪种机制可以用来进行进程间通信()

A  Socket

B  PIPE

C  SHARED MEMORY

D  以上皆可

 D

进程间通信（IPC，InterProcess Communication）通信方法有管道、消息队列、信号、共享内存、套接口等。

# 管道( pipe  )：管道是一种半双工的通信方式，数据只能单向流动，而且只能在具有亲缘关系的进程间使用。进程的亲缘关系通常是指父子进程关系。
#   有名管道 (named pipe) ： 有名管道也是半双工的通信方式，但是它允许无亲缘关系进程间的通信。
# 信号量(   semophore ) ：  信号量是一个计数器，可以用来控制多个进程对共享资源的访问。它常作为一种锁机制，防止某进程正在访问共享资源时，其他进程也访问该资源。因此，主要作为进程间以及同一进程内不同线程之间的同步手段。
# 消息队列( message queue ) ：  消息队列是由消息的链表，存放在内核中并由消息队列标识符标识。消息队列克服了信号传递信息少、管道只能承载无格式字节流以及缓冲区大小受限等缺点。
# 信号 ( signal ) ： 信号是一种比较复杂的通信方式，用于通知接收进程某个事件已经发生。
# 共享内存( shared  memory ) ：共享内存就是映射一段能被其他进程所访问的内存，这段共享内存由一个进程创建，但多个进程都可以访问。共享内存是最快的 IPC   方式，它是针对其他进程间通信方式运行效率低而专门设计的。它往往与其他通信机制，如信号两，配合使用，来实现进程间的同步和通信。
#   套接字( socket ) ： 套解口也是一种进程间通信机制，与其他通信机制不同的是，它可用于不同及其间的进程通信。

第9题：

 下列关于编程优化的说法正确的是()：

A  使用编译器的优化选项(如-O3)后程序性能一定会获得提高

B  循环展开得越多越彻底，程序的性能越好

C  寄存器分配能够解决程序中的数据依赖问题

D  现代主流C/C++编译器可以对简单的小函数进行自动Iinline

 D

D肯定是对的，而且ABC的言论太绝对。但如果一定要给出解释的话……
A选项的优化只能针对代码本身，纯系统调用什么的是不会性能提升的（当然也不会下降），
B选项我觉得是在并行优化方面，好的编译器可以从循环中发掘并行性，展开之后就不行了，
C选项有点说不清。消除数据依赖主要有两个方法，一种是SSA，即静态单赋值[3]，这是通过对变量进行重命名实现的，严格的说应该叫“寄存器重命名”[4]而不是“寄存器分配”；另外一种是调换指令顺序，这种只要不是真相关（写后读，RAW）的话都可以消除掉，也不属于寄存器分配。所以感觉不应该选这个。

第10题：

 以下程序是用来计算两个非负数之间的最大公约数：

long long gcd(long long x, long long y) {

    if (y == 0)

        return x;

    else

        return gcd(y, x % y);

}

我们假设x,y中最大的那个数的长度为n，基本运算时间复杂度为O(1)，那么该程序的时间复杂度为()：

A  O(1)

B  O(logn)

C  O(n)

D  O(n^2)

 B

对于gcd(a,b),假设a,b中最大的数为a,则若调用了k次，则a>=F(k+2),b>=F(k+1),F(x)为第x个斐波拉切数，而F(x)=m^x/sqrt(5),因此这题最坏时间复杂度应该为O(n)，与这个数的长度成正比

第11题：

二、问答题 

长度为n的数组乱序存放着0至n-1. 现在只能进行0与其他数的交换，完成以下函数

for (int i = len-1; i>=0; i--){

 if (array[i] == i){

 //i--;

 continue;

 }

 int k = array[i];

 while (array[k] != k&&array[k] != i)

 {

 k = array[k];

 }

 swap_with_zero(array, len, i);

 swap_with_zero(array, len, k);

 }

第12题：

 给定一个原串和目标串，能对源串进行如下操作： 

1.在给定位置插入一个字符 

2.替换任意字符 

3.删除任意字符 要求完成一下函数，返回最少的操作数，使得源串进行这些操作后等于目标串。源串和目标串长度都小于2000。

public int min(int a, int b, int c){

        if(a < b){

            return a < c ? a : c;

        }else{

            return b < c ? b : c;

        }

    }

public int getMinDis(String s1, String s2){

        int n1 = s1.length();

        int n2 = s2.length();

        int f[][] = new int [n1+1][n2+1];

        for(int i = 1; i <= n1; i ++){

            f[i][0] = i;

        }

        for(int i = 1; i <= n2; i ++){

            f[0][i] = i;

        }

        for(int i = 1; i <= n1; i ++){

            for(int j = 1; j <= n2; j ++){

                if(s1.charAt(i-1) == s2.charAt(j-1)){

                    f[i][j] = f[i-1][j-1];

                }else{

                    f[i][j] = min(f[i-1][j-1], f[i][j-1], f[i-1][j]) + 1;

                }

            }

        }

        return f[n1][n2];

    }

第13题：

 写函数，输出前N个素数。不需要考虑整数溢出问题，也不需要使用大数处理算法。

import java.util.ArrayList;

import java.util.List;

public class Solution {

    /**

     * 获取n个素数

     * n: 素数个数

     * 返回：最小的N个素数

     */

    public List getPrimes(int n) {

     List ret = new ArrayList();

        // ret.add(x);

        int number = Integer.MAX_VALUE;

        int counter = 0;

        for (int i = 2; i < number; i++) {

            if (n <= 0) {

                break;

            }

            counter = 0;

            for (int j = 2; j <= Math.sqrt(i); j++) {

                if (i % j == 0) {

                    counter++;

                    break;

                }

            }

            if (counter == 0) {

                ret.add(i);

                n--;

            }

        }

        return ret;

    }

}