谷歌 2021 技術(shù)崗位面試題

?一、單選題

如果把傳輸速率定義為單位時(shí)間內傳送的信息量（以字節計算）多少。關(guān)于一下幾種典型的數據傳輸速率：
1.使用USB2.0閃存盤(pán)，往USB閃存盤(pán)上拷貝文件的數據傳輸速率
2.使用100M以太網(wǎng)，在局域網(wǎng)內拷貝大文件時(shí)網(wǎng)絡(luò )上的數據傳輸速率
3.使用一輛卡車(chē)拉1000塊單塊1TB裝滿(mǎn)數據的硬盤(pán)，以100km/h的速度從上海到天津（100km）一趟所等價(jià)的數據傳輸帶寬
4.使用電腦播放MP3，電腦的PCI總線(xiàn)到聲卡的數據傳輸速率
在通常情況下，關(guān)于這幾個(gè)傳輸速率的排序正確的是(? )

A? 4<1<2<3

B? 1<4<2<3

C? 4<1<3<2

D? 1<4<3<2

?

?A

?普通U盤(pán)寫(xiě)數據的6MB/s，即48Mbps； 100M以太網(wǎng)的速率就是100Mbps； 卡車(chē)拉硬盤(pán)，1000x1000x8/3600=2222Mbps，這個(gè)應該是最快的； MP3在256kbps碼率下也平均只有1分鐘2MB，所以不會(huì )超過(guò)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? 程序可以正確編譯連接，但是運行時(shí)會(huì )崩潰

D? 程序語(yǔ)法錯誤，編譯不成功

?D

第3題：

?在區間[-2, 2]里任取兩個(gè)實(shí)數，它們的和>1的概率是()

????

A? 3/8

B? 3/16

C? 9/32

D? 9/64

?C

第4題：

?小組賽，每個(gè)小組有5支隊伍，互相之間打單循環(huán)賽，勝一場(chǎng)3分，平一場(chǎng)1分，輸一場(chǎng)不得分，小組前三名出線(xiàn)。平分抽簽。問(wèn)一個(gè)隊最少拿()分就有理論上的出線(xiàn)希望：

A? 1

B? 2

C? 3

D? 4

?B

\后3名球隊兩兩之間打平，對前兩名都輸球，依據抽簽的運氣決出誰(shuí)是第三名出線(xiàn)

第5題：

?用二進(jìn)制來(lái)編碼字符串“abcdabaa”，需要能夠根據編碼，解碼回原來(lái)的字符串，最少需要()長(cháng)的二進(jìn)制字符串？

A? 12

B? 14

C? 18

D? 24

?B

這道題需要對abcd進(jìn)行Huffman編碼。首先根據權值建立Huffman樹(shù)，得到最優(yōu)編碼：
a=0, b=10, c=110, d=111
然后數一下就行了。

第6題：

?10個(gè)相同的糖果，分給三個(gè)人，每個(gè)人至少要得一個(gè)。有()種不同分法

????????

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題：

?下列程序段，循環(huán)體執行次數是()：

int y = 2;

while (y <= 8) {

????y = y + y;

}

A? 2

B? 16

C? 4

D? 3

?D

第8題：

?下面哪種機制可以用來(lái)進(jìn)行進(jìn)程間通信()

???

A? Socket

B? PIPE

C? SHARED MEMORY

D? 以上皆可

?D

進(jìn)程間通信（IPC，InterProcess Communication）通信方法有管道、消息隊列、信號、共享內存、套接口等。

# 管道( pipe ?)：管道是一種半雙工的通信方式，數據只能單向流動(dòng)，而且只能在具有親緣關(guān)系的進(jìn)程間使用。進(jìn)程的親緣關(guān)系通常是指父子進(jìn)程關(guān)系。
# ? 有名管道 (named pipe) ： 有名管道也是半雙工的通信方式，但是它允許無(wú)親緣關(guān)系進(jìn)程間的通信。
# 信號量( ? semophore ) ： ?信號量是一個(gè)計數器，可以用來(lái)控制多個(gè)進(jìn)程對共享資源的訪(fǎng)問(wèn)。它常作為一種鎖機制，防止某進(jìn)程正在訪(fǎng)問(wèn)共享資源時(shí)，其他進(jìn)程也訪(fǎng)問(wèn)該資源。因此，主要作為進(jìn)程間以及同一進(jìn)程內不同線(xiàn)程之間的同步手段。
# 消息隊列( message queue ) ： ?消息隊列是由消息的鏈表，存放在內核中并由消息隊列標識符標識。消息隊列克服了信號傳遞信息少、管道只能承載無(wú)格式字節流以及緩沖區大小受限等缺點(diǎn)。
# 信號 ( signal ) ： 信號是一種比較復雜的通信方式，用于通知接收進(jìn)程某個(gè)事件已經(jīng)發(fā)生。
# 共享內存( shared ?memory ) ：共享內存就是映射一段能被其他進(jìn)程所訪(fǎng)問(wèn)的內存，這段共享內存由一個(gè)進(jìn)程創(chuàng )建，但多個(gè)進(jìn)程都可以訪(fǎng)問(wèn)。共享內存是最快的 IPC ? 方式，它是針對其他進(jìn)程間通信方式運行效率低而專(zhuān)門(mén)設計的。它往往與其他通信機制，如信號兩，配合使用，來(lái)實(shí)現進(jìn)程間的同步和通信。
# ? 套接字( socket ) ： 套解口也是一種進(jìn)程間通信機制，與其他通信機制不同的是，它可用于不同及其間的進(jìn)程通信。

第9題：

?下列關(guān)于編程優(yōu)化的說(shuō)法正確的是()：

???

A? 使用編譯器的優(yōu)化選項(如-O3)后程序性能一定會(huì )獲得提高

B? 循環(huán)展開(kāi)得越多越徹底，程序的性能越好

C? 寄存器分配能夠解決程序中的數據依賴(lài)問(wèn)題

D? 現代主流C/C++編譯器可以對簡(jiǎn)單的小函數進(jìn)行自動(dòng)Iinline

?D

D肯定是對的，而且ABC的言論太絕對。但如果一定要給出解釋的話(huà)……
A選項的優(yōu)化只能針對代碼本身，純系統調用什么的是不會(huì )性能提升的（當然也不會(huì )下降），
B選項我覺(jué)得是在并行優(yōu)化方面，好的編譯器可以從循環(huán)中發(fā)掘并行性，展開(kāi)之后就不行了，
C選項有點(diǎn)說(shuō)不清。消除數據依賴(lài)主要有兩個(gè)方法，一種是SSA，即靜態(tài)單賦值[3]，這是通過(guò)對變量進(jìn)行重命名實(shí)現的，嚴格的說(shuō)應該叫“寄存器重命名”[4]而不是“寄存器分配”；另外一種是調換指令順序，這種只要不是真相關(guān)（寫(xiě)后讀，RAW）的話(huà)都可以消除掉，也不屬于寄存器分配。所以感覺(jué)不應該選這個(gè)。

第10題：

?以下程序是用來(lái)計算兩個(gè)非負數之間的最大公約數：

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

????if (y == 0)

????????return x;

????else

????????return gcd(y, x % y);

}

????

我們假設x,y中最大的那個(gè)數的長(cháng)度為n，基本運算時(shí)間復雜度為O(1)，那么該程序的時(shí)間復雜度為()：

???

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個(gè)斐波拉切數，而F(x)=m^x/sqrt(5),因此這題最壞時(shí)間復雜度應該為O(n)，與這個(gè)數的長(cháng)度成正比

第11題：

二、問(wèn)答題?

長(cháng)度為n的數組亂序存放著(zhù)0至n-1. 現在只能進(jìn)行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題：

?給定一個(gè)原串和目標串，能對源串進(jìn)行如下操作：?

1.在給定位置插入一個(gè)字符?

2.替換任意字符?

3.刪除任意字符 要求完成一下函數，返回最少的操作數，使得源串進(jìn)行這些操作后等于目標串。源串和目標串長(cháng)度都小于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題：

?寫(xiě)函數，輸出前N個(gè)素數。不需要考慮整數溢出問(wèn)題，也不需要使用大數處理算法。

?

import java.util.ArrayList;

import java.util.List;

public class Solution {

??? /**

??? ?* 獲取n個(gè)素數

??? ?* n: 素數個(gè)數

??? ?* 返回：最小的N個(gè)素數

??? ?*/

??? 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;

??? }

}