欢迎来到2017网易前端开发实习题目的讨论组

今天下午14到16点网易进行了18届实习的第一次笔试，自我感觉心态有点小崩咧。
但是也并没有到完全不能做的地步，毕竟只是实习的笔试，也不会太过困难地，但感觉距离还是不小，好好努力吧。

一、题型总结

总结了一下大概有以下笔试题型：

###选择题部分（30分）

• 元素出栈可能性
• 排序方法的优缺点
• HTTP请求方法
• 关系型数据库种类
• 多线程（进程与线程共享）
• 计算机网络协议
• linux指令
• JQuery实现方法

###编程题（60分）

• 集合
• 奇怪的表达式求值
• 消除重复元素
  ###问答题（10分）
• JS实现Excel表格列项排序功能

二、重回战场（选择题）

1、

问题：元素1,2,3……7入栈，有多少种出栈的可能性？

考点：卡特兰数，折现法

解析：

真的是，这种题目总是想搞些大新闻，搞一点没人听过的东西，其实很简单，其实很自然，就是…没做出来。

和这个题目一共有三个类型：

1、饭后，姐姐洗碗，妹妹把姐姐洗过的碗一个一个地放进碗橱摞成一摞。一共有n个不同的碗，洗前也是摞成一摞的，也许因为小妹贪玩而使碗拿进碗橱不及时，姐姐则把洗过的碗摞在旁边，问：小妹摞起的碗有多少种可能的方式？

2、给定n个数，有多少种出栈序列？

3、一个有n个1和n个-1组成的字串，且前k个数的和均不小于0，那这种字串的总数为多少？

乍一看，一脸萌币，该洗的洗，该放的放，咋还能这么玩。
在查阅了资料以后整理了一下思路，特别是这两张神图，一定要看。

在 出栈入栈 的过程中，就好比一个人要从原点到达 （2n，0）这个点(入n出n)

入栈为右上方移动单位长度(记为操作1)，出栈为向右下方移动单位长度（记为操作2）。出栈时，栈内必须要有元素，所以，曲线在x轴上方时，是合法的。

但是！在合法条件下完成计算并不是一件简单的事情

我们可以尝试从反面来做：即 合法步骤 = 所有步骤 - 非法步骤

1> 合法步骤可能性为C（2n，n），即在2n个操作步骤中随机选取n个入栈过程即可

2> 接下来讨论非法步骤，是比较绕的

我们可以看到，图示所列的实线非法步骤越过了x轴，这是当然的。
但是当我们以y = -1为对称轴将图像对称后（即操作1和2互换），我们可以发现，所有的非法折现都到达了（2n,-2）这个点，经过研究后发现并不是巧合，也没能看出是为什么。

但是我们可以发现，对称后，非法步骤中，操作2 比 操作1多了来了两次。
即进行 n-1 次操作 1，n+1次操作2，即可完成非法操作。

所以答案为C（2n,n）-C(2n,n-1) = C(2n,n)/(n+1)

当n = 7时，次数为429次 （不会就蒙D…？）

2、

问题：在100 0000个数中选出最大的五个数字，那种排序方法最为快速？

考点： 堆排序，合并排序，快速排序，希尔排序（插入排序的一种，也称缩小增量排序）

（动画的话参考这个：http://www.atool.org/sort.php）

解析：

数据结构我真的没有好好学吗..

❤快速排序：真的，100 0000的数据量以内，见到快排，就选了吧。不跟你多..
原理：快速排序（Quicksort）是对冒泡排序的一种改进。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
优势：插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率。
缺点：不稳定，在序列有序或者逆序的情况下最不利于发挥其长处

希尔排序：我怎么就觉得这个快
原理：希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
优势：快，数据移动少
缺点：不稳定，d的取值是多少，应取多少个不同的值，都无法确切知道，只能凭经验来取，并且插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位。

❤堆排序：数据超过1000 0000的时候，他是老大
原理：堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆，是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值，即A[PARENT[i]] >= A[i]。在数组的非降序排序中，需要使用的就是大根堆，因为根据大根堆的要求可知，最大的值一定在堆顶。
优势：由于它在直接选择排序的基础上利用了比较结果形成。效率提高很大。它完成排序的总比较次数为O(nlog2n)，它是对数据的有序性不敏感的一种算法。
缺点：在小规模序列中使用它不合适（不要杀鸡用牛刀？）

归并排序：我怎么就觉得这个快
原理：归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
优势：使用它对两个己有序的序列归并，将有无比巨大的优势。其时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlog2n)，且对数据的有序性不敏感。
缺点：需要与待排序序列一样多的辅助空间，所以数据节点数据量大，则不适合使用

——————————

3、HTTP的请求方法

问题：以下不属于HTTP的请求方法的是？（答案为：SET）

考点：关于HTTP（Hypertext Transfer Protocol）的八种请求方法

请求方法列表

4、关系数据库的种类

问题：以下不属于关系数据库的是?

考点：数据库基础知识

解析：

数据库类型主要可分为:网状数据库(Network Database)、关系数据库(Relational Database)、树状数据库(Hierarchical Database)、面向对象数据库(Object-oriented Database)等

❤关系数据库：（SQL）
原理：
1、关系型数据库，是指采用了关系模型来组织
数据的数据库；
2、关系型数据库的最大特点就是事务的一致性；
3、简单来说，关系模型指的就是二维表格模型，
而一个关系型数据库就是由二维表及其之间的联系所组成的一个数据组织。
优势：
1、容易理解：二维表结构是非常贴近逻辑世界一个概念，关系模型相对网状、层次等其他模型来说更容易理解；
2、使用方便：通用的SQL语言使得操作关系型数据库非常方便；
3、易于维护：丰富的完整性(实体完整性、参照完整性和用户定义的完整性)大大减低了数据冗余和数据不一致的概率；
4、支持SQL，可用于复杂的查询。
1、为了维护一致性所付出的巨大代价就是其读写性能比较差；
2、固定的表结构；
3、高并发读写需求；
4、海量数据的高效率读写；
主流数据库代表：
oracle、db2、sqlserver、sybase、mysql

非关系数据库（Not Only SQL）：（种类较多，也就不细分了）
定义：
1、使用键值对存储数据；
2、分布式；
3、一般不支持ACID特性；
4、非关系型数据库严格上不是一种数据库，应该是一种数据结构化存储方法的集合。
优势：
1、使用键值对存储数据；
2、分布式；
3、一般不支持ACID特性；
4、非关系型数据库严格上不是一种数据库，应该是一种数据结构化存储方法的集合。
1、不提供sql支持，学习和使用成本较高；
2、无事务处理，附加功能bi和报表等支持也不好；
主流数据库代表：
MongoDb、redis、HBase

5、多线程（进程与线程共享）

问题：以下属于同一个进程内线程共享的部分是？

考点：多线程（我能怎么办，我也很绝望系列）中线程共享的环境

解析：

1>线程共享的环境包括：

1、进程代码段
2、进程的公有数据(利用这些共享的数据，易于线程间实现相互之间的通讯)
3、进程打开的文件描述符
4、信号的处理器
5、进程的当前目录
6、进程用户ID与进程组ID。
7、线程的堆共有，栈私有

2>线程的非共享的个性包括：

1.线程ID
每个线程都有自己的线程ID，这个ID在本进程中是唯一的。进程用此来标识线程。
2.寄存器组的值
由于线程间是并发运行的，每个线程有自己不同的运行线索，当从一个线程切换到另一个线程上时，必须将原有的线程的寄存器集合的状态保存，以便将来该线程在被重新切换到时能得以恢复。
3.线程的栈
栈是保证线程独立运行所必须的。
线程函数可以调用函数，而被调用函数中又是可以层层嵌套的，所以线程必须拥有自己的函数栈，使得函数调用可以正常执行，不受其他线程的影响。
4.错误返回码
由于同一个进程中有很多个线程在同时运行，可能某个线程进行系统调用后设置了errno值，而在该线程还没有处理这个错误，另外一个线程就在此时被调度器投入运行，这样错误值就有可能被修改。 所以，不同的线程应该拥有自己的错误返回码变量。
5.线程的信号屏蔽码
由于每个线程所感兴趣的信号不同，所以线程的信号屏蔽码应该由线程自己管理。但所有的线程都共享同样的信号处理器。
6.线程的优先级
由于线程需要像进程那样能够被调度，那么就必须要有可供调度使用的参数，这个参数就是线程的优先级。

6、计算机网络

问题：以下说法正确的是：

考点：计算机网络

解析：

A: UDP是可靠服务（Wrong）
解析： UDP 是User Datagram Protocol的简称， 中文名是用户数据报协议，是OSI（Open System Interconnection，开放式系统互联） 参考模型中一种无连接的传输层协议，提供面向事务的简单不可靠信息传送服务，IETF RFC 768是UDP的正式规范。UDP在IP报文的协议号是17。

B: NAT是一种把内部私有网络地址（IP地址）翻译成合法网络IP地址的技术（Right）
解析： NAT（Network Address Translation，网络地址转换）是1994年提出的。当在专用网内部的一些主机本来已经分配到了本地IP地址（即仅在本专用网内使用的专用地址），但现在又想和因特网上的主机通信（并不需要加密）时，可使用NAT方法。

C: TCP建立和关闭链接都只需要四次握手（Shake hands?先mark）（Wrong）
解析： 三次握手建立链接，四次挥手关闭连接
所谓三次握手(Three-way Handshake)，是指建立一个TCP连接时，需要客户端和服务器总共发送3个包。三次握手的目的是连接服务器指定端口，建立TCP连接,并同步连接双方的序列号和确认号并交换 TCP 窗口大小信息.在socket编程中，客户端执行connect()时。将触发三次握手。
第一次握手:客户端发送一个TCP的SYN标志位置1的包指明客户打算连接的服务器的端口，以及初始序号X,保存在包头的序列号(Sequence Number)字段里。
第二次握手:服务器发回确认包(ACK)应答。即SYN标志位和ACK标志位均为1同时，将确认序号(Acknowledgement Number)设置为客户的I S N加1以.即X+1。
第三次握手:客户端再次发送确认包(ACK) SYN标志位为0,ACK标志位为1.并且把服务器发来ACK的序号字段+1,放在确定字段中发送给对方.并且在数据段放写ISN的+1

D: HTTP返回码302表示永久重定向，需要重新URL（Uniform resource locator）(Wrong)
解析：
301，302 都是HTTP状态的编码，都代表着某个URL发生了转移，不同之处在于：
301 redirect: 301 代表永久性转移(Permanently Moved)。
302 redirect: 302 代表暂时性转移(Temporarily Moved )。

7、Linux指令

问题：下面Linux命令，不能打印该目录下所有的文件和文件夹的是？

考点：操作系统（网易不限门槛的实习意思就这么明显？）

解析：

ls命令是Linux下最常用的命令。ls命令就是list的缩写。
缺省下ls用来打印当前目录的清单，如果ls指定其他目录，那么就会显式指定目录里的文件及文件夹清单，通过ls命令不仅可以查看linux文件夹包含的文件，而且可以查看文件权限等等。

echo*: echo命令用于在shell中打印shell变量的值，或者直接输出指定的字符串。linux的echo命令，在shell编程中极为常用, 在终端下打印变量value的时候也是常常用到的，因此有必要了解下echo的用法echo命令的功能是在显示器上显示一段文字，一般起到一个提示的作用。

dir: dir命令是ls命令的一个别名，也是directory的缩写。通常列出的文件会以不同的颜色进行显示，不同的颜色代表不同的文件类型，下表列出了文件类型与颜色的对应关系。

三、重回战场（编程题）

1、

问题：

小易有一个长度为n序列，小易想移除掉里面的重复元素，但是小易想是对于每种元素保留最后出现的那个。小易遇到了困难,希望你来帮助他。
输入描述:

输入包括两行：
第一行为序列长度n(1 ≤ n ≤ 50)
第二行为n个数sequencei，以空格分隔

输出描述:

输出消除重复元素之后的序列，以空格分隔，行末无空格

输入例子:

9
100 100 100 99 99 99 100 100 100

输出例子:

99 100

我只想说牛客网，对js一点都不！友！好！

加个node.js readline接收模块对于我这种小白简直就

无发渴说

解析：

题目还是比较简单的，题目的意思理解起来大概就是。

1. 你把题目给你的数据存进数组
2. 反过来将没有重复的元素放进新数组
3. 再讲最后的新数组反转输出即可

感觉这种用flag分两段接收数据的JS接收方法真的是亮点！！

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

//引入node.js readline接收模块
var readline = require('readline');
//创建readline接口实例
const rl = readline.createInterface({
        input: process.stdin,
        output: process.stdout
});
//定义需要使用的变量
var sum = 0;//接收数组长度
var bool = 0;//表示还未接收数据数据一，用于控制接收数据一后接收数据二
var sequence = [] ;//作为数组元素
var check = [] ;//作为存储满足条件的元素数组
//注意给变量定义一个类型，要不然报错没商量
//开始接收数据
rl.on('line', function(line){
    if(bool == 0){//接受数据一
        sum = parseInt(line.trim());
        bool = 1;
    }else{//接收数据2
        sequence = line.split(" ").map(function(index){
           return parseInt(index); 
        });//以空格为单位接收数据进数组
        
        sequence.reverse();//反转数组，舒服
        
        for(var i = 0;i<sum;i++){//从后往前加入新元素
  		if(check.indexOf(sequence[i]) == -1)
    		check.push(sequence[i]);
		}
        check.reverse();//反转2333
        console.log(check.join(" "));//连接成字符串
        bool = 2;//表示接收了第二行数据，方便进行下一次循环检测
    }
    if(bool == 2)//对bool进行初始化，当成flag用
        bool = 0;
    
   
});

2、

问题：

常规的表达式求值，我们都会根据计算的优先级来计算。比如/的优先级就高于+-。但是小易所生活的世界的表达式规则很简单，从左往右依次计算即可，而且小易所在的世界没有除法，意味着表达式中没有/，只有(+, - 和 )。现在给出一个表达式，需要你帮忙计算出小易所在的世界这个表达式的值为多少
输入描述:

输入为一行字符串，即一个表达式。其中运算符只有-,+,*。参与计算的数字只有0~9.
保证表达式都是合法的，排列规则如样例所示。

输出描述:

输出一个数，即表达式的值

输入例子:

3+5*7

输出例子:

56

解析：

一个半小时才做完这个题，我跟你说我就是这!表!情!

1. 五分钟理清思路，10分钟编程，一个小时找错误（编程五分钟，Debug2小时）
2. 题目的意思很简单，将数据分成两个数组进行运算即可，用正则表达式，则更为方便，但是不熟练，我还是选择放弃用这个方法
3. 血泪教训：一定要严格化输出输入数据的格式和精度（parseInt and parseFloat是好朋友），否则可能就是在研究0+2为什么等于02的路上越走越远

   代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

var readline = require("readline");
const r1 = readline.createInterface({
    input:process.stdin,
    output:process.stdout
});
//定义需要使用的变量
var number = [];//数字数组
var symbol = [];//符号数组
var input = [];//输入数据
var a = 0;//存储计算结果的变量
//计算子函数
function operate(numa,sym,numb){//不要忘记括号！！
    switch (sym){
        case '+': return parseFloat(numa) + parseFloat(numb);
        case '-': return parseFloat(numa) - parseFloat(numb);
        case '*': return parseFloat(numa) * parseFloat(numb);
    }
}
r1.on('line',function(line){
    //接收所有输入数据
    input = line.split("");
    
    //按照顺序分割成数字和符号数组
    for(var i = 0; i < input.length;i++){//var not int 
        if(i % 2 == 0)
            number.push(input[i]);
        else
            symbol.push(input[i]);
    }
             
    //将存储变量赋初值，为了方便后面的循环复制存储
    a = number[0];            
    for(var j = 1;j < symbol.length + 1;j++){
        a = operate(a,symbol[j-1],number[j]);
    }
    console.log(a);
})

3、

问题：

小易最近在数学课上学习到了集合的概念,集合有三个特征：1.确定性 2.互异性 3.无序性.
小易的老师给了小易这样一个集合：
S = { p/q | w ≤ p ≤ x, y ≤ q ≤ z }
需要根据给定的w，x，y，z,求出集合中一共有多少个元素。小易才学习了集合还解决不了这个复杂的问题,需要你来帮助他。
输入描述:

输入包括一行：
一共4个整数分别是w(1 ≤ w ≤ x)，x(1 ≤ x ≤ 100)，y(1 ≤ y ≤ z)，z(1 ≤ z ≤ 100).以空格分隔

输出描述:

输出集合中元素的个数

输入例子:

1 10 1 1

输出例子:

10

解析：

因为这个是第一题编程题，还是比较简单的，当时JS不会写，就用Java写的，所见难度并不是很大，大家可以参考下代码就行啦

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

var readline = require("readline");
const r1 = readline.createInterface({
    input:process.stdin,
    output:process.stdout
});
var a = 0;
var c = [];
var b = [];
r1.on('line',function(line){
    c = line.split(" ").map(function(index){
        return parseInt(index);
    })
    for(var i = c[0];i < c[1] + 1;i++)
    	for(var j = c[2];j < c[3] + 1;j++){
            a = i / j;
            if(b.indexOf(a) == -1)
        		b.push(a);
    }
    console.log(b.length);    
})

三、重回战场（问答题）

题目：

在页面上有如下表格，当点击成绩的时候，所有行数据根据成绩从低到高排序，再点击成绩则变为从高到低排序，请用JavaScript实现以上功能，可以使用jQuery
名字 | 性别 | 成绩
——– | — | —
张三 | 男|77
李四 | 女|87
王五 | 未知（这个6）|50

解析：

这个坑先留着，等到实力够了再来补上

四、总结

经过这么一天半的折腾感觉自己还是学到了不少知识，在之后的学习路径规划上：

首先要注意对大三相关专业课的学习的记忆，也要有随时随地用到数据结构和数据库的觉悟，虽然猪场说的是无门槛投简历，大范围的传播内推码，但是从这次笔试的题目内容可以看出猪场的套路还是不少，像选择题虽然占分不高，但是非科班出身的面试者可能并没有那么多的计算机方面的储备知识，从而科班和非科班出身的差距就会在笔试成绩上体现出来。

其次是对js编程中例如jQuery等能够提升编程效率的重视和掌握，在看jQuery的过程中一直没有动力，看看最后的问答题，无从下手的感觉可能会给自己点压力吧嘿嘿

最后是对算法能力的要求跟想象中的差距不大，刚刚好在努把力就能懂的边边上，感觉自己还是需要不断的学习，跟前端群友讨论的过程中，都表示目前还只是大二，学习时间还很充足，但是，时间 这个东西，说慢也慢说快也快，马上就是个大三狗了，还是要给自己定个小目标，比如明年进猪场实习？