阿里钉钉

太紧张了没做好。

题目

// 评测题目: 无用多种方法来实现，编写一个数组去重函数
// 如输入数组[1,"a",{b:2},{c:3},{c:"3"},"1","a"]，返回[1,"a",{b: 2},{c: 3},{c:"3"}, "1"]

网易

2018笔试

空间复杂度

操作系统中，不同子线程会共享同一个父进程的?

线程共享的环境包括：进程代码段、进程的公有数据(利用这些共享的数据，线程很容易的实现相互之间的通讯)、进程打开的文件描述符、信号的处理器、进程的当前目录和进程用户ID与进程组ID。

进程拥有这许多共性的同时，还拥有自己的个性。有了这些个性，线程才能实现并发性。这些个性包括：

1.线程ID

2.寄存器组的值

3.线程的堆栈

4.错误返回码

5.线程的信号屏蔽码

6.线程的优先级

TCP和UDP

TCP/IP 是互联网相关的各类协议族的总称，比如：TCP，UDP，IP，FTP，HTTP，ICMP，SMTP 等都属于 TCP/IP 族内的协议。

TCP/IP模型是互联网的基础，它是一系列网络协议的总称。这些协议可以划分为四层，分别为链路层、网络层、传输层和应用层。

• 链路层：负责封装和解封装IP报文，发送和接受ARP/RARP报文等。
• 网络层：负责路由以及把分组报文发送给目标网络或主机。
• 传输层：负责对报文进行分组和重组，并以TCP或UDP协议格式封装报文。
• 应用层：负责向用户提供应用程序，比如HTTP、FTP、Telnet、DNS、SMTP等。
  

TCP/IP 中有两个具有代表性的传输层协议----TCP 和 UDP。

UDP

UDP协议全称是用户数据报协议，在网络中它与TCP协议一样用于处理数据包，是一种无连接的协议。在OSI模型中，在第四层——传输层，处于IP协议的上一层。UDP有不提供数据包分组、组装和不能对数据包进行排序的缺点，也就是说，当报文发送之后，是无法得知其是否安全完整到达的。

1. 面向无连接

首先 UDP 是不需要和 TCP一样在发送数据前进行三次握手建立连接的，想发数据就可以开始发送了。并且也只是数据报文的搬运工，不会对数据报文进行任何拆分和拼接操作。

• 在发送端，应用层将数据传递给传输层的 UDP 协议，UDP 只会给数据增加一个 UDP 头标识下是 UDP 协议，然后就传递给网络层了
• 在接收端，网络层将数据传递给传输层，UDP 只去除 IP 报文头就传递给应用层，不会任何拼接操作

2. 有单播，多播，广播的功能

3. UDP是面向报文的

发送方的UDP对应用程序交下来的报文，在添加首部后就向下交付IP层。UDP对应用层交下来的报文，既不合并，也不拆分，而是保留这些报文的边界。因此，应用程序必须选择合适大小的报文

4. 不可靠性

首先不可靠性体现在无连接上，通信都不需要建立连接，想发就发，这样的情况肯定不可靠。

并且收到什么数据就传递什么数据，并且也不会备份数据，发送数据也不会关心对方是否已经正确接收到数据了。

再者网络环境时好时坏，但是 UDP 因为没有拥塞控制，一直会以恒定的速度发送数据。即使网络条件不好，也不会对发送速率进行调整。这样实现的弊端就是在网络条件不好的情况下可能会导致丢包，但是优点也很明显，在某些实时性要求高的场景（比如电话会议）就需要使用 UDP 而不是 TCP。

5. 头部开销小，传输数据报文时是很高效的。

TCP

TCP协议全称是传输控制协议是一种面向连接的、可靠的、基于字节流的传输层通信协议，TCP 是面向连接的、可靠的流协议。

1. TCP连接过程

第一次握手

客户端向服务端发送连接请求报文段。该报文段中包含自身的数据通讯初始序号。请求发送后，客户端便进入 SYN-SENT 状态。

第二次握手

服务端收到连接请求报文段后，如果同意连接，则会发送一个应答，该应答中也会包含自身的数据通讯初始序号，发送完成后便进入 SYN-RECEIVED 状态。

第三次握手

当客户端收到连接同意的应答后，还要向服务端发送一个确认报文。客户端发完这个报文段后便进入 ESTABLISHED 状态，服务端收到这个应答后也进入 ESTABLISHED 状态，此时连接建立成功。

2. 断开连接
   

TCP 是全双工的，在断开连接时两端都需要发送 FIN 和 ACK。

第一次握手

若客户端 A 认为数据发送完成，则它需要向服务端 B 发送连接释放请求。

第二次握手

B 收到连接释放请求后，会告诉应用层要释放 TCP 链接。然后会发送 ACK 包，并进入 CLOSE_WAIT 状态，此时表明 A 到 B 的连接已经释放，不再接收 A 发的数据了。但是因为 TCP 连接是双向的，所以 B 仍旧可以发送数据给 A。

第三次握手

B 如果此时还有没发完的数据会继续发送，完毕后会向 A 发送连接释放请求，然后 B 便进入 LAST-ACK 状态。

第四次握手

A 收到释放请求后，向 B 发送确认应答，此时 A 进入 TIME-WAIT 状态。该状态会持续 2MSL（最大段生存期，指报文段在网络中生存的时间，超时会被抛弃） 时间，若该时间段内没有 B 的重发请求的话，就进入 CLOSED 状态。当 B 收到确认应答后，也便进入 CLOSED 状态。

3. TCP连接的特点

• 面向连接

面向连接，是指发送数据之前必须在两端建立连接。建立连接的方法是“三次握手”，这样能建立可靠的连接。建立连接，是为数据的可靠传输打下了基础。

• 仅支持单播传输

每条TCP传输连接只能有两个端点，只能进行点对点的数据传输，不支持多播和广播传输方式。

• 面向字节流

• 可靠传输

对于可靠传输，判断丢包，误码靠的是TCP的段编号以及确认号。TCP为了保证报文传输的可靠，就给每个包一个序号，同时序号也保证了传送到接收端实体的包的按序接收。然后接收端实体对已成功收到的字节发回一个相应的确认(ACK)；如果发送端实体在合理的往返时延(RTT)内未收到确认，那么对应的数据（假设丢失了）将会被重传。

• 提供拥塞控制

当网络出现拥塞的时候，TCP能够减小向网络注入数据的速率和数量，缓解拥塞

• TCP提供全双工通信

TCP允许通信双方的应用程序在任何时候都能发送数据，因为TCP连接的两端都设有缓存，用来临时存放双向通信的数据。当然，TCP可以立即发送一个数据段，也可以缓存一段时间以便一次发送更多的数据段（最大的数据段大小取决于MSS）

TCP和UDP的对比

• 在TCP/UDP传输段中，源端口地址和目的端口地址是不能相同的，若源端口地址和目的端口地址相同，相当于是建立了一条自己通向自己的连接，会造成资源浪费

• 当客户端和服务器建立的是TCP连接的时候，服务器最后如果想要断开直接断开连接，要发送“断开请求”

• UDP是用户数据报协议，是一个简单的面向数据报的传输层协议

• UDP在传输数据报前不用在客户和服务器之间建立一个连接，没有超时重发的机制

• 丢包多的话udp比TCP慢

shell中，可以让一个变量变为全局变量的是？

export：Linux export 命令用于设置或显示环境变量。

alias：用户可利用alias，自定指令的别名。若仅输入alias，则可列出目前所有的别名设置。

let： let 命令是 BASH 中用于计算的工具，用于执行一个或多个表达式，变量计算中不需要加上 $ 来表示变量。如果表达式中包含了空格或其他特殊字符，则必须引起来。

有序无序标签显示

<ol>
<li>网易</li>
<li>http://www.163.com</li>
<ol>

1. 网易
2. http://www.163.com

ol:ordered list 有序表格
ul:unordered list 无序表格

<ol></ol>是有序列表标签。
<li>标签会换行。

字符串操作

slice(start,end) 返回浅拷贝数组 不改变原数组
splice() 如果删除一个元素 返回只包含该元素的数组 原数组改变
concat() 返回拼接后的数组 不改变原数组

变量提升

var val = 100;
function wangyi(){
    console. log(val);
    var val = 200;
    console.log(val);
}
wangyi();

js允许提前使用随后才声明的变量，称为变量声明提升，但“被声明提升”的变量的值一律规定为 undefined 。

wangyi()函数的执行顺序：1.函数内部（AO），var val局部变量声明提升，并赋默认值为undefind,所以第一个打印的是undefined；2.执行val = 200;所以此时val的值是200，打印就是200。这里100是全局的（GO），而执行函数用的是函数自身的val，不必考虑全局变量。

哪个函数没有定时器作用？

• window.setTimeout
• window.setInterval
• window.requestAnimationFrame：告诉浏览器——你希望执行一个动画，并且要求浏览器在下次重绘之前调用指定的回调函数更新动画。该方法需要传入一个回调函数作为参数，该回调函数会在浏览器下一次重绘之前执行
• window.requestAsyncAfter：无此函数（是ios中的），无定时器作用

关于Webpack打包

• 不可以在开发阶段使用浏览器没实现的语法规范
• 可以提高代码的运行效率
• 可以直接用node编写配置文件
• 可以使用npm管理前端代码的模块依赖

localStorage

基本使用方法

localStorage.setItem("b","isaac");//设置b为"isaac"
var b = localStorage.getItem("b");//获取b的值,为"isaac"
var a = localStorage.key(0); // 获取第0个数据项的键名，此处即为“b”
localStorage.removeItem("b");//清除c的值
localStorage.clear();//清除当前域名下的所有localstorage数据

作用域

数据结构

localstorage为标准的键值对（Key-Value,简称KV）数据类型，简单但也易扩展，只要以某种编码方式把想要存储进localstorage的对象给转化成字符串，就能轻松支持。

生存期

localStorage理论上来说是永久有效的，即不主动清空的话就不会消失，即使保存的数据超出了浏览器所规定的大小，也不会把旧数据清空而只会报错。但需要注意的是，在移动设备上的浏览器或各Native App用到的WebView里，localStorage都是不可靠的，可能会因为各种原因（比如说退出App、网络切换、内存不足等原因）被清空。

过期时间

localstorage原生是不支持设置过期时间的，想要设置的话，就只能自己来封装一层逻辑来实现

容量限制、域名限制

目前业界基本上统一为5M。

由于浏览器的安全策略，localstorage是无法跨域的，也无法让子域名继承父域名的localstorage数据，这点跟cookies的差别还是蛮大的。

函数作用域

var name = 'window';
var obj = {
     name: 'netease',
     print1: () => {
         console.log(this.name);
     },
     print2 () {
         console.log(this.name);
     }
};
obj.print1();
obj.print2();
//=>window netease

箭头函数可以改变函数的作用域。箭头函数中的this在定义时确定，为父级作用域的this。
此时print1方法是obj的对象方法，obj外层为window，所以print1中的this指向window。

单选多选按钮

• radio 以name属性划分组，一组内有且仅有一个被选中。要实现 radio 的多选操作，除了默认情况以外，还可以通过设置其 name 属性的值不相同来实现
• checkbox 所谓的“单选”是不受其 name 属性的值的影响的

  margin塌陷问题

• 垂直并列盒子塌陷：垂直之间塌陷的原则是以两盒子最大的外边距为准。
• 父子盒子塌陷：设置子盒子margin-top = 10px; 子盒子和父盒子之间并没出现期望的10px间隙而是父盒子与子盒子一起与页面顶端产生了10px间隙（即父级盒子往下塌陷了10px）。

  中文排序问题

  题目

作为中文用户，我们总是希望页面上的列表项（比如商品名称）能按拼音排序，方便查找。已知 JavaScript 中的字符串有一个方法可以实现对中文按拼音排序，我们假设这个方法为 x，示例代码如下：

let name = `网易杭州`;
let sortedName = name.split('').sort((a, b) => {
    // 利用字符串的 x 方法进行拼音排序
    return a.x(b);
}).join('');
console.log(sortedName); // 输出 `杭网易州`

问：
1. x 方法的真实名称是什么？
2. 汉字转拼音，常见的做法是准备一个庞大的字典库，所以放到前端来转换是不现实的。利用题目中的这个方法，可以很方便地将汉字转换成拼音，请简述实现思路。要求字典库体积尽可能小，转换效率尽可能高。

• x的名称为：localeCompare
• 思路可见这：https://github.com/creeperyang/blog/issues/31

  编程题1

  小易准备去魔法王国采购魔法神器,购买魔法神器需要使用魔法币,但是小易现在一枚魔法币都没有,但是小易有两台魔法机器可以通过投入x(x可以为0)个魔法币产生更多的魔法币。
  魔法机器1:如果投入x个魔法币,魔法机器会将其变为2x+1个魔法币
  魔法机器2:如果投入x个魔法币,魔法机器会将其变为2x+2个魔法币
  小易采购魔法神器总共需要n个魔法币,所以小易只能通过两台魔法机器产生恰好n个魔法币,小易需要你帮他设计一个投入方案使他最后恰好拥有n个魔法币。

function createCoins() {
    var n = parseInt(readline().split(" ")[0]);
    if (n === 1) return "1";
    if (n === 2) return "2";
    var order = [];
    while (n > 0) {
        if ((n - 2) % 2 === 0) {
            n = (n - 2) / 2;
            order = order.concat([2]);
        } else {
            n = (n - 1) / 2;
            order = order.concat([1]);
        }
    }
    order.reverse();
    return order.join("");
}

编程题2

一个由小写字母组成的字符串可以看成一些同一字母的最大碎片组成的。例如,"aaabbaaac"是由下面碎片组成的:'aaa','bb','c'。牛牛现在给定一个字符串,请你帮助计算这个字符串的所有碎片的平均长度是多少。

var input
while (input = readline()) {
    var arr = input.match(/(\w)\1*/g);
    var total = 0;
    for(var i = 0; i < arr.length; i ++) {
        total += arr[i].length;
    }
    print((total/arr.length).toFixed(2));//四舍五入至小数点后2位
}

2020笔试

链表查找

现在假设对N个元素的链表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为（ ）？

• 第一个数的比较次数为1，第二个数的比较次数为2。。。以此类推第N个数的比较次数为N，所以总的比较次数为1+2+...+N=N(N+1)/2,平均比较次数为(N+1)/2,也即平均查找长度。

Promise运行结果

下列程序的运行结果是什么？
console.log(1);
new Promise(function (resolve, reject){
reject();
resolve();
}).then(function(){
console.log(2);
}, function(){
console.log(3);
});
console.log(4);

这题考查异步，Promise.then是微任务属于异步，而console.log(1)、console.log(4)都是同步，所以先打印1、4。最后看Promise对象。

Promise对象只有三种结果：Pending(进行中)、Fulfilled(已成功)、Rejected(已失败)。对象的状态变化只有两种：从Pending —— Fulfilled(Resolved)；从Pending —— Rejected。
构造函数Promise接受一个函数作为参数，并且该函数有两个参数resolve 和 reject。resolve是异步操作成功时调用，reject是异步操作失败时调用。Promise实例对象的then方法中的两个函数分别指定Resolved状态（成功）和Rejected状态（失败）的回调函数。

回到本题：在Promise构造函数中reject()比resolve()先执行，会执行Rejected状态的回调，即console.log(3)，打印3。前面说了Promise对象状态改变只有两种情况，执行reject()后，Promise对象状态变为了Rejected。所以后面的resolve()不会执行。最终结果为：1、4、3。

this指向问题

var a = 1
function fn1() {
console.log(this.a)
}
const fn2 = ()=> {
console.log(this.a)
}

const obj = {
a: 10,
fn1: fn1,
fn2: fn2
}

fn1()
fn2()
obj.fn1()
obj.fn2()

本题考查this指向问题，以及箭头函数中this指向。

箭头函数中的this始终指向其父级作用域中的this。换句话说，箭头函数会捕获其所在的上下文的this值，作为自己的this值。在箭头函数中调用 this 时，仅仅是简单的沿着作用域链向上寻找，找到最近的一个 this 拿来使用，它与调用时的上下文无关。

• fn1()中，this指向window，所以打印1
• fn2()中，fn2是一个箭头函数，this指向作用域链上最近的this，这里为window,所以打印1.
• obj.fn1()中，fn1是一个普通函数，this指向obj,即obj.a。所以打印10。
• obj.fn2()中，fn2是一个箭头函数，this会继承父级作用域中的this，为window。所以打印1.
  本题最终结果：1 、1、10、1

  valueOf与toString

  const a = {
  valueOf() {
  return 'valueOf'
  },
  toString() {
  return 'toString'
  },
  get() {
  return 'get'
  }
  }
  alert(a)

在数值运算中，优先调用了valueOf，字符串运算中，优先调用了toString。而’ '+bbb是字符串操作，为啥也是调用valueOf，那是因为，存在操作符，valueOf的优先级高于toString。

回到本题: alert(obj)不存在数值运算，和其他操作符，所以默认调用toString方法。

this指向问题2

function fun () {
    return () => {
        return () => {
            return () => {
            console.log(this.name)
                    }
                }
        }
}
var f = fun.call({name: 'foo'})
var t1 = f.call({name: 'bar'})()()
var t2 = f().call({name: 'baz'})()
var t3 = f()().call({name: 'qux'})

前面说过箭头函数的this是继承父级作用域的this,而不是指向调用者。

var f = fun.call({name: ‘foo’})这一句 会将this指向{name: ‘foo’}。

var t1 = f.call({name: ‘bar’})()()，执行f(),之后返回的都是箭头函数,所以直到最后，父级作用域上的this还是指向{name: ‘foo’}。打印：foo。

下面两个同样，因为t1、t2、t3都是箭头函数，使用call()方法不能改变this指向，作用域链上最近的this还是指向{name:‘foo’}。

本题结果：foo foo foo

CSS块级元素和行内元素

1. 块级元素会独占一行,默认情况下,其宽度自动填满其父元素宽度。

行内元素不会独占一行,相邻的行内元素会排列在同一行里,直到一行排不下,才会换行,其宽度随元素的内容而变化。

2. 块级元素的padding和margin值的设置都是有效的。行内元素和块级元素都是盒子模型。

   行内元素的padding-top、padding-bottom、margin-top、margin-bottom属性设置是无效的（top bottom）

   行内元素的padding-left、padding-right、margin-left、margin-right属性设置是有效的（left right）

   行内元素的 line-height 属性设置是有效的。

   行内元素的 width、height 属性设置是无效的。

   行内元素的padding-top、padding-bottom从显示的效果上是增加的，但其实设置的是无效的，并不会对他周围的元素产生任何影响

3. strong是行内元素，它的width、height属性设置无效（没错啊？？？）

4. textarea是行内元素 - 多行文本输入框，input也是行内元素

行内inline 块级block 行内块级line-block(拥有内在尺寸，可设置高宽，不会自动换行 )😎

有哪些常见的服务端推送的通信解决方案？它们的优劣分别是什么？

1. 基于轮询：

• 优点：开发简单，客户端实现即可，不需要服务端配合
• 缺点：大多数情况下无用请求，占用服务端资源
• 实现方式：客户端每隔一段时间调用接口，无论有没有数据，接口立即返回.
• 使用场景：不想折腾的开发者，消息及时性要求没那么高，服务器资源资源足。

2. 基于长轮询

• 优点：消息及时，命中率高，消耗服务端资源少
• 缺点：服务端和客户端需要同时改造，消息会有部分延迟（发生在请求交替之时）
• 实现方式：客户端在上次请求返回后，在发送下次请求，服务端当有数据或者超时后返回，没有数据时hang住链接（超时时间需要综合考虑服务器性能和及时性做出平衡，有代理的话需要考虑代理对于链接的超时机制）。
• 使用场景：扫码登录，微信网页端获取消息等。

3. 长链接

• 优点：通信及时，通信模式采用双工，类似于打电话
• 缺点：服务端和客户端需要同时改造，当链接过多时，消耗服务端资源比较大。
• 实现方式：客户端和服务端建立长链接，基于http1.1 ,keepalive ,websocket,comet，iframe等，基于socket的需要维持心跳
• 使用场景：实时性要求很高，银行系统，股票系统等

从输入url到页面展现发生了什么？其中在页面渲染以及网络请求响应的性能优化方面，我们分别可以做哪些优化工作？

请求页面

1、dns解析
- 先在本地host查找
- 到浏览器dns缓存查找
- 到根域名服务器查找
- 找主域名服务器查找
- 返回ip地址
2、浏览器缓存
- 强缓存maxAge未过时直接读取本地磁盘缓存，无需建立连接
- 协商缓存if-modify-since --> etag （优先级高）
3、没有缓存，建立tcp连接
- 三次握手 syn -> syn+ack -> fin
- 建立SSL通信，客户端携带随机数，支持的加密算法列表请求443端口 -> 服务端返回数字证书+公钥+随机数b -> 客户端验证证书有效性生成随机数c，用某种加密算法根据abc生成对称密钥，并返回给服务端 -> 服务端私钥解密，得到对称密钥，然后双方使用对称密钥通信
// - 复杂请求，先发起option请求检验服务可用性
- 接收数据包（请求头，请求行，请求体）根据content-type进行解码，根据不同资源类型进行不同的加载策略
- 四次挥手 syn -> syn + ack -> fin -> ack + fin
4、浏览器渲染
- 浏览器主进程通知渲染进程可以开始渲染了
- 渲染进程接收到垂直同步信号，通知主线程
- 主线程先进行渲染的前置操作，清空当前的所有微任务，之后触发requestAnimationFrame，进入渲染阶段
- 构建dom树 + css renderer -> 得到layout树
-根据图层生成规则，并计算节点位置，生成layer树
- 通知合成线程，layer树准备完毕
- 合成线程进行分块和光栅化的操作
- 通知gpu可以开始进行绘制了
- gpu调用显示器提供的DirectX api，ldp，aldp不同策略进行得到色彩页面显示
- （中间会穿插css的加载，js的执行，defer，async等不同策略）
总结：输入url按下回车之后，浏览器会去浏览器缓存中寻找该url的ip；没有的话去系统缓存中找，还是没有的话去路由器缓存中寻找；再没有就去系统host文件中找，还是没有最后只能去请求dns服务器，然后dns给一个ip给浏览器；浏览器根据这个ip地址，将请求信息，请求说明和请求参数等封成一个tcp包，由传输层，到网络层，到数据链路层到物理层，传送给服务器，服务器解析这个tcp包将对应的页面文件返回。浏览器根据html文件生成dom树，根据css文件生成cssom树，然后合并这两棵树生成渲染树，然后渲染页面并且展示。要注意的是，当浏览器解析html文件时候如果遇到了内联或者外联的js代码，会暂停dom树的生成，等js代码执行完成之后，才能继续生成树并渲染。

其中在页面渲染以及网络请求响应的性能优化方面，我们可以做的优化工作有：

1. js代码写在页面渲染完成之后避免阻塞渲染
2. cdn并发，资源压缩，减少请求次数
3. 预加载或者懒加载

function test (a, b, p, q) {
    returnMath.ceil(Math.log(((b - a) / p)) / Math.log(q)) + 1
}
let linenum = parseInt(readline())
for(let i = 0; i < linenum; i++){
    let cur = readline().split(' ').map(Number)
    print(test(cur[0], cur[1], cur[2], cur[3]))
}