2021年腾讯面试题(后台开发岗位)

小编:管理员 463阅读 2021.06.09

第1题:


一、不定项选择

将一组无序的数据重新排列成有序序列,其方法有()

 

A  拓扑排序

B  快速排序

C  堆排序

D  基数排序



答案:BCD

解析:在图论中,由一个有向无环图的顶点组成的序列,当且仅当满足下列条件时,称为该图的一个拓扑排序(英语:Topological sorting)。

每个顶点出现且只出现一次;
若A在序列中排在B的前面,则在图中不存在从B到A的路径。
也可以定义为:拓扑排序是对有向无环图的顶点的一种排序,它使得如果存在一条从顶点A到顶点B的路径,那么在排序中B出现在A的后面


第2题:


 某服务请求经负载均衡设备分配到集群A、B、C、D进行处理响应的概率分别是10%、20%、30%和40%。已知测试集群所得的稳定性指标分别是90%、95%、99%和99.9%。现在该服务器请求处理失败,且已排除稳定性以外的问题,那么最有可能在处理该服务请求的集群是________。

A、A

B、B

C、C

D、D



答案:A B

解析:选中该集群,并且处理失败了的概率为:10%*10%、20%*5%、30%*1%、40%*0.1%。A与B的概率最高。


第3题:


下列说法正确的有( )

 

A  环境变量可在编译source code时指定

B  在编译程序时,所能指定的环境变量不包括class path

C  javac一次可同时编译数个Java源文件

D  javac.exe能指定编译结果要置于哪个目录(directory)


答案:A C D


第4题:


下列说法错误的有( )

         

A  数组是一种对象

B  数组属于一种原生类

C  int number=[]={31,23,33,43,35,63}

D  数组的大小可以任意改变



答案: B C D

解答:Java把数组当作一个java类来处理

java是纯面向对象的语言,他的数组也是一个对象。


第5题:


下列说法错误的有( )

         

A  能被java.exe成功运行的java class文件必须有main()方法

B  J2SDK就是Java API

C  Appletviewer.exe可利用jar选项运行.jar文件

D  能被Appletviewer成功运行的java class文件必须有main()方法



答案:B C D

解析如下:

B选项中J2SDK是编程工具,不是API.

C选项中      Appletviewer.exe   就是用来解释执行java       applet应用程序的,简单理解就是没有main函数的继承applet类的java类。

D选项中      能被Appletviewer成功运行的java class文件没有main()方法


第6题:


 卡方分布的方差为2倍的自由度为?

     

A  n

B  1

C  2n

D  4n



答案:C

注解: 分布的均值为自由度 n,记为 E() = n。

分布的方差为2倍的自由度(2n),记为 D() = 2n。


第7题:


如何减少换页错误?

  

A  进程倾向于占用CPU

B  访问局部性(locality of reference)满足进程要求

C  进程倾向于占用I/O

D  使用基于最短剩余时间(shortest remaining time)的调度机制



答案: B

解析如下:

换页错误又称缺页错误,当一个程序试图访问没有映射到物理内存的地方时,就会出现缺页错误,   这时操作系统就要去虚拟内存中加载这块内存页。

百度了一下,减少换页错误的方法,即降低缺页中断率:      
1、内存页框数。增加作业分得的内存块数。      
2、页面大小。页面划分越大,中断率越低。      
3、替换算法的优劣影响缺页中断次数      
4、程序局部性。程序局部性好可减少缺页中断(为什么?)。      
 

那么B是对的,而对于D,最短剩余时间调度是CPU调度就绪进程的方式,与页面置换算法无关,不要搞混淆了。  


第8题:


 Please choose the right statement about constusage:
 

A  const int a; //const integer

B  int const a; //const integer

C  int const *a; //a pointer which point to const integer

D  const int *a; //a const pointer which point to integer

E  int const *a; // a const pointer which point to integer



答案:ABC

解析如下:

对于A和B,int const 和 const int 可以颠倒位置,意义不变

CDE都表示指向const int 的指针,而int *const a 才表示指向int的const指针


第9题:


下列定义语句中,错误的是

 

A  int px*;

B  char*acp[10];

C  char(*pac)[10];

D  int(*p)();


答案: A


第10题:

对类成员访问权限的控制,是通过设置成员的访问控制属性实现的,下列不是访问控制属性的是(    )

 

A  公有类型

B  私有类型

C  保护类型

D  友元类型


答案:D

解析如下:

C++中有三种权限控制类型,分别是共有类型public,私有类型private,保护类型protected.

友元是声明一个类外的方法具有类方法同样的访问权限,目的是让类外的方法可以访问类内部的属性,不是访问控制属性。


第11题:


给出以下定义,下列哪些操作是合法的?
 

const char *p1 = “hello”;

char *const p2 = “world”;

    

A  p1++;

B  p1[2] = ‘w’;

C  p2[2] = ‘l’;

D  p2++;



答案:A

解析如下:

p1是指向字符常量的指针,p1本身不是常量,所以p1++合法,A正确。

p2本身是指针常量,可以指向非常量的字符。但是"hello"这样声明的字符串是存储在只读存储区的,不可修改,所以B,C,D都错误。


第12题:

以下集合对象中哪几个是线程安全的?(       )

 

A  ArrayList

B  Vector

C  Hashtable

D  Stack


答案: BCD  

解析如下:

在集合框架中,有些类是线程安全的,这些都是jdk1.1中的出现的。在jdk1.2之后,就出现许许多多非线程安全的类。  下面是这些线程安全的同步的类:

vector:就比arraylist多了个同步化机制(线程安全),因为效率较低,现在已经不太建议使用。在web应用中,特别是前台页面,往往效率(页面响应速度)是优先考虑的。

statck:堆栈类,先进后出

hashtable:就比hashmap多了个线程安全

enumeration:枚举,相当于迭代器

除了这些之外,其他的都是非线程安全的类和接口。


第13题:

若下列所用变量均已经正确定义,一下表达式中不合法的是

 

A  x>>3

B  +++j

C  a=x>y?x:y

D  x%=4


答案:B

解析如下:

A ,x右移三位

B,++j是j自增1,+++j是不合法的,编译出错

C,这是一个三目运算符,(exp1)?(exp2):(exp3)

   当exp1为true时个表达式结果为exp2

   当exp1为false时整个表达式结果为exp3

D,取余运算,等价于x=x%4


第14题:

test.c文件中包括如下语句:

#define INT_PTR int*

typedef int* int_ptr;

INT_PTR a,b;

int_ptr c,d;    

文件中定义的四个变量中,哪个变量类型不是指针类型?

A  a

B  b

C  c

D  d

E  都是指针

F  都不是指针



答案:B

解析如下:
#define INT_PTR int* 这是宏定义,编译预处理阶段要进行宏替换,INT_PTR a,b会变成 int* a,b 所以b不是指针类型
typedef int* int_ptr; 这是自定义类型,也就是把int_ptr定义为 int型指针,编译阶段会把c,d都识别为指针


第15题:

不属于冯诺依曼体系结构必要组成部分是:

 A  CPU

B  Cache

C  RAM

D  ROM


答案:B


第16题:


 二、问答题

有1000亿条记录,每条记录由url,ip,时间组成,设计一个系统能够快速查询以下内容
1.给定url和时间段(精确到分钟)统计url的访问次数
2.给定ip和时间段(精确到分钟)统计ip的访问次数



 答:首先,1000亿条记录全部放到内存肯定不够,那就是分成小文件了,然后整合;
公共的时间段,因为精确到分钟,我们把这每一分钟建成一个小文件,每个小文件肯定会有许多重复的ip,url;
现在统计每个小的文件中url的访问量和ip的访问次数,方法就是建立索引;
(建立索引的目的是为了减少查询次数,但是随着索引级数增多也会造成花更多的时间在建立索引上);
建立url的索引,假如是www.nowcoder.com/question,可以分别给www.nowcoder.com和question建立索引,那么来了一条url,先看一级索引是不是匹配,匹配再看二级索引,相同的话就是我们要的url目标;
ip的索引也是一样,ip分成4段建立索引;
所以这里影响效率的就是在索引建立这块,索引建立好那就是查询的事了的,就会变得非常快。
假定给定了某个时间段,找出url的访问量,那么先找到给定的时间段,对应着刚开始分割的小的文件(每一个分钟)中搜索,通过索引找到相同的url之后,开始统计,直到搜索完所有的给定时间段内的所有的小的文件;
求ip的访问次数也是一样,按照给定的时间段,找到对应的小的文件,通过索引找到相同的ip后统计,直到搜索完了给定时间段内的所有的小的文件。


第17题:


 实现一个简化的搜索提示系统。给定一个包含了用户query的日志文件,对于输入的任意一个字符串s,输出以s为前缀的在日志中出现频率最高的前10条query。

由于是分布式系统,假设至少有26台机器,每个机器存储以26个字母开头的query日志文件(如机器1存的是a字母开头的,机器2存的是以b字母开头的……)

每个机器上维护着一张哈希表,对于每条query, 在哈希表表中存放其地址(哈希地址为链式的),并对其进行排序,按频率由高到低进行排序。

当用户进行搜索时,可以很快定位到某台机器,并根据哈希表,返回出现频率最高的前10条query。

提示:

1、可以预处理日志

2、假设query不超过10亿条,每个query不超过50字节。

3、考虑在大查询量的情况下如何实现分布式服务



  系统前台:

用JS监控input输入框的内容变化,用户输入或者删除字符(输入串的发生变化)就触发异步Javascript提交输入内容到后台,引发后台查询。然后再讲查询结果出现频率最高的前10条query展现给用户提示。


系统后台:

首先有26台服务器分别存储26个字母开头的query。所以首先要设计一个接收用户请求的服务器,这台服务器可以根据用户请求的首字母将查询请求分发给对应26台服务器中的一个(相当于查询请求的路由功能)。

然后就是这26台查询服务器如何设计的问题了。

假设query不超过10亿条,每个query不超过50字节。也就是query文件不超过50G,分在26台机器上也就是每台机器上的query文件不超过2G。

每个机器上维护着一张哈希表,对于每条query,   在哈希表表中存放其地址。收到每个query做hash运算可以找到query对应的地址。对应每个query存储两项信息,即query本身和被查询次数,也就是类似query:times这样的存储格式。

下面做预处理:26台机器都对自身存储的query进行遍历,分别找出a到z开头query出现频率最高的top10,这样的查询一次遍历就能找到,时间复杂度为O(N)。然后对找到的top10在内存中构建一个最小堆。其他非top10的query无需做排序处理。到这里预处理完成。

然后说查询过程,查询分为两类,

1,以给出搜索提示的异步Javascript提交的查询,这种查询直接返回最小堆中的10个query词条即可。

2,用户最终提交的查询(即用户输入完毕点击搜索按钮提交的查询),这种查询的query是用户最终查询的词条,这样的查询应该引起后台存储的对应query频率的变化。当一个query到达的时候,先用hash运算找到他的位置和对应的频率,hash操作时间复杂度是O(1),然后对应的次数+1,然后用这个+1的次数与最小堆中首个元素比较,如果大于最小堆首个元素,与最小堆中首个元素交换,然后最小堆做更新操作,保证最小堆的特性。否则不操作。这样最小堆中维护的10个query始终是这台机器上频率最高的,查询时返回这10个query词条即可。


第18题:


 小米公司内部每个员工都会有一个专属的工作邮箱,邮箱的前缀是员工姓名的拼音全拼,例如张强的邮箱是zhangqiang@xiaomi.com,但同时公司里有很多同名的人,为了避免大家相互之间发错邮件,工程师们想了个规则来解决这个问题,即在这些同命人中,入职最早的邮箱前缀为姓名的拼音全拼,第二个入职的邮箱前缀为姓名的拼音全拼后面加“_a”,第三个入职的为姓名的拼音全拼后面加“_b”,以次类推,请按这个规则,如果公司里同时有3位名叫张强的员工,则他们的邮箱分别是zhangqiang@xiaomi.com,zhangqiang_a@xiaomi.com,zhangqiang_b@xiaomi.com...邮箱前缀是员工在公司里的重要标识之一,问题来了:现在小米要举行一次全员野外拉练活动,要求所有员工必须排成一队出去,并且,有的员工要求他必须排在某人的前面或后面,作为组织者的你,收到这样的需求之后,如何给出一个让每个人都满意的排队方式呢?
Java:


class RequestItem

{

    public String member;

    public boolean standFront; //true表示要排在这个人的前面,false表示要排在这个人的后面

}

class Request

{

    public String owner;    //那个人提出的要求

    List<RequestItem> requestItems;    //他要排在哪些人的前面,哪些人的后面

}

List<String> getValidOrder(List<String>allMembers, List<Request> requests);

   

allMembers就是所有员工的邮箱前缀,requests是一些人的排队要求。小米公司现有几千名员工,每个人最多有10个排队要求(要排在一个人的前面或者后面算一个排队要求),也有人没有什么要求。现在你的任务是完成上面的getValidOrder函数,如果有合法的排队序列,那么返回其中任何一个。否则返回null。




 假设有n个员工。

选用数据结构,map[n][n]。

1、其中map[i][j]=1代表i在j的前面,=0代表前后位置,=-1带表在后面。若出现已经=-1的情况下,在后面又要求=1,会形成环,则返回null。。

2、这样就形成了一个图,然后进行拓扑排序即可。先找出所有入度为0的点,放在前面,然后去掉这些点和相应的边.如此得到最终结果。


关联标签: