谷歌 2013 技术岗位
技术研发 技术支持
本套题共13题,并含有参考答案
题目详情
第1题

 一、单选题

如果把传输速率定义为单位时间内传送的信息量(以字节计算)多少。关于一下几种典型的数据传输速率:
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 <stdio.h>

#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<Integer> getPrimes(int n) {

     List<Integer> ret = new ArrayList<Integer>();

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

    }

}


共有 13 道题目