笔试真题刷题平台
精选近几年名企笔试真题，笔试之前刷刷真题，有备无患
一、不定项选择
将一组无序的数据重新排列成有序序列,其方法有()
A 拓扑排序
B 快速排序
C 堆排序
D 基数排序
BCD
在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，称为该图的一个拓扑排序（英语：Topological sorting）。
每个顶点出现且只出现一次；
若A在序列中排在B的前面，则在图中不存在从B到A的路径。
也可以定义为：拓扑排序是对有向无环图的顶点的一种排序，它使得如果存在一条从顶点A到顶点B的路径，那么在排序中B出现在A的后面
某服务请求经负载均衡设备分配到集群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的概率最高。
答案：A、B
下列说法正确的有（ ）
A 环境变量可在编译source code时指定
B 在编译程序时，所能指定的环境变量不包括class path
C javac一次可同时编译数个Java源文件
D javac.exe能指定编译结果要置于哪个目录（directory）
A C D
下列说法错误的有（ ）
A 数组是一种对象
B 数组属于一种原生类
C int number=[]={31,23,33,43,35,63}
D 数组的大小可以任意改变
B C D
解答：Java把数组当作一个java类来处理
java是纯面向对象的语言，他的数组也是一个对象。
下列说法错误的有（ ）
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()方法
卡方分布的方差为2倍的自由度为？
A n
B 1
C 2n
D 4n
C
注解: 分布的均值为自由度 n，记为 E() = n。
分布的方差为2倍的自由度(2n)，记为 D() = 2n。
如何减少换页错误？
A 进程倾向于占用CPU
B 访问局部性（locality of reference）满足进程要求
C 进程倾向于占用I/O
D 使用基于最短剩余时间（shortest remaining time）的调度机制
B
换页错误又称缺页错误，当一个程序试图访问没有映射到物理内存的地方时，就会出现缺页错误， 这时操作系统就要去虚拟内存中加载这块内存页。
百度了一下，减少换页错误的方法，即降低缺页中断率：
1、内存页框数。增加作业分得的内存块数。
2、页面大小。页面划分越大，中断率越低。
3、替换算法的优劣影响缺页中断次数
4、程序局部性。程序局部性好可减少缺页中断（为什么？）。
那么B是对的，而对于D，最短剩余时间调度是CPU调度就绪进程的方式，与页面置换算法无关，不要搞混淆了。
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指针
下列定义语句中，错误的是
A int px*；
B char*acp[10]；
C char（*pac）[10]；
D int（*p）（）；
A
对类成员访问权限的控制，是通过设置成员的访问控制属性实现的，下列不是访问控制属性的是( )
A 公有类型
B 私有类型
C 保护类型
D 友元类型
D
C++中有三种权限控制类型，分别是共有类型public，私有类型private，保护类型protected.
友元是声明一个类外的方法具有类方法同样的访问权限，目的是让类外的方法可以访问类内部的属性，不是访问控制属性。
给出以下定义，下列哪些操作是合法的？
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都错误。
以下集合对象中哪几个是线程安全的？( )
A ArrayList
B Vector
C Hashtable
D Stack
BCD
在集合框架中，有些类是线程安全的，这些都是jdk1.1中的出现的。在jdk1.2之后，就出现许许多多非线程安全的类。 下面是这些线程安全的同步的类：
vector：就比arraylist多了个同步化机制（线程安全），因为效率较低，现在已经不太建议使用。在web应用中，特别是前台页面，往往效率（页面响应速度）是优先考虑的。
statck：堆栈类，先进后出
hashtable：就比hashmap多了个线程安全
enumeration：枚举，相当于迭代器
除了这些之外，其他的都是非线程安全的类和接口。
若下列所用变量均已经正确定义，一下表达式中不合法的是
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
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都识别为指针
不属于冯诺依曼体系结构必要组成部分是：
A CPU
B Cache
C RAM
D ROM
B
二、问答题
有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后统计，直到搜索完了给定时间段内的所有的小的文件。
实现一个简化的搜索提示系统。给定一个包含了用户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词条即可。
小米公司内部每个员工都会有一个专属的工作邮箱，邮箱的前缀是员工姓名的拼音全拼，例如张强的邮箱是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的点，放在前面，然后去掉这些点和相应的边.如此得到最终结果。
