lightGBM的优化

1.直方图算法
2.按叶子生长（leaf-wise）
3.直方图加速
4.直接支持类别特征
5.特征并行和数据并行

使用注意

1.设置提前停止
2.自动处理类别特征
3.缺失值处理

spark 重点相关
1.spark job 提交流程，及dag有向无环图生成流程
2.spark shuffle 原理（shuffle read，shuffle write）
3.spark 内存区域管理（2.0以前，2.0后）

col存储的特点（优势）
1.块遍历
2.压缩
3.延迟物化

二叉树锯齿形层次遍历

题目

Given a binary tree, return the zigzag level order traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between).

For example:
Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
return its zigzag level order traversal as:
[
[3],
[20,9],
[15,7]
]

OSI与TCP/IP各层的结构与功能，都有哪些协议

五层协议体系结构

应用层(重点)

运输层(重点)

网络层(重点)

数据链路层

物理层

TCP 三次握手和四次挥手(重点)

三次握手

四次挥手

TCP、UDP协议的区别

TCP协议如何保证可靠传输

应用数据被分割成TCP认为最合适发送的数据块，TCP给发送的每一个包进行编号，接收方对数据包进行排序，把有序数据传送给应用层。

校验和

滑动窗口

流量控制(和滑动窗口联合使用)

拥塞控制

拥塞窗口(cwnd)
慢开始 由小到大逐渐增大拥塞窗口数值
拥塞避免 让拥塞窗口cwnd缓慢增大
快重传与快恢复 如果接收机接收到一个不按顺序的数据段，它会立即给发送机发送一个重复确认。如果发送机接收到三个重复确认，它会假
定确认件指出的数据段丢失了，并立即重传这些丢失的数据段。

停止等待协议

停止等待协议是为了实现可靠传输的，它的基本原理就是每发完一个分组就停止发送，等待对方确认。在收到确认后再发下一个分组；
在停止等待协议中，若接收方收到重复分组，就丢弃该分组，但同时还要发送确认；
停止等待协议中超时重传是指只要超过一段时间仍然没有收到确认，就重传前面发送过的分组，这种自动重传方式常称为自动重传请求 ARQ 。
连续 ARQ 协议 可提高信道利用率。发送维持一个发送窗口，凡位于发送窗口内的分组可连续发送出去，而不需要等待对方确认。

在浏览器中输入url地址 ->> 显示主页的过程

总体来说分为以下几个过程:
DNS解析
TCP连接
发送HTTP请求
服务器处理请求并返回HTTP报文
浏览器解析渲染页面
连接结束

状态码

1xx
2xx
3xx
4xx
5xx

各种协议与HTTP协议之间的关系

HTTP长连接、短连接

HTTP协议的长连接和短连接，实质上是TCP协议的长连接和短连接。

数据仓库概念

数据仓库发展历程

数据库与数据仓库的区别

数据仓库架构分层

元数据介绍

星型模型和雪花模型

什么是GBDT

GBDT是集成学习Boosting家族的成员。每一轮都依赖于前一轮迭代学习器的误差来更新权重。假设，前一轮得到的学习器是ft−1(x), 损失函数
是L(y,ft−1(x)), 我们本轮迭代的目标是找到一个CART回归树模型的弱学习器ht(x)，让本轮的损失函数L(y,ft(x)=L(y,ft−1(x)+ht(x))最小。

GBDT的负梯度拟合

接雨水

题目

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

Example:

Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

解析重点

1.两种思路。第一种，什么样的地方可以蓄水，两个极值点之间，也就是我们循环数组，不断找出极值点，然后计算他们之间的蓄水面积即可。蓄水面积
怎么求呢，等于sum((min(a[i],a[j])-a[k])>0?(min(a[i],a[j])-a[k]):0).
2.第二种，一个位置可以蓄的水，依赖于他两边的极大值中极小值，那我们可以从数组两边向中间循环，极小值属于哪边，那我们就可以计算哪边的蓄水
量，trapWater=min(left,right)-a[i],当trapWater>0时，代表可以蓄水，累加即可。

java代码

这里实现的是第二种

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

class Solution {
    public int trap(int[] A){
        int a=0;
        int b=A.length-1;
        int max=0;
        int leftmax=0;
        int rightmax=0;
        while(a<=b){//左右两边循环，计算两边的最大值
            leftmax=Math.max(leftmax,A[a]);//左边的最大值
            rightmax=Math.max(rightmax,A[b]);//右边的最大值
            if(leftmax<rightmax){//如果左边比右边小
                max+=(leftmax-A[a]);//那么，左边当前的点的蓄水量可以计算
                a++;
            }
            else{
                max+=(rightmax-A[b]);//同左边
                b--;
            }
        }
        return max;
    }
}

什么是题目画像

题目画像是我们对题目打上各种各样的标签，让我们对题目有更精准的认识。但是，这对我们进行挖掘没有什么用，因为我们要给机器看，而不是给人看。所以我们要对题目进行向量化，最后得到的就是题目画像。题目画像不是我们的目的，而是在各种算法模型和业务功能中产生的一个关键的副产品。

题目画像的关键因素

第一个是维度，第二个是量化。

题目画像的构建方法

1.直接使用原始数据。
直接使用原始数据作为题目画像的内容，像录入资料，学科、题干、答案、题干图片数、学段等，除了清洗工作本身并没有任何抽象和归纳。但是对于初期非常比较有用。
2.堆积历史数据。
从历史数据中，做统计工作，像根据历史做题记录计算难度、区分度等。再或者根据统计为题目打上各种标签，然后用统计结果作为量化结果。不过我们现在历史数据并不充分，可以暂时不考虑这一部分。
3.使用机器学习方法。
使用各种机器学习的方法，学习出人类无法直接理解的稠密向量，这一部分是我们最重要的，因为题目很多都是非结构化的信息，知识图谱、文字、公式、图片等，这都需要我们结构化，然后向量化。

结构化文本

成熟NLP算法分析得到的信息种类
1.关键词提取
2.实体识别
3.内容分类
4.主题模型
5.嵌入(我们当前模型主要使用的方式，也是我们初期工作部分)

文本如何提取用户画像内容

从物品端的文本信息，我们可以利用成熟的NLP算法分析得到的信息有下面几种。
1.关键词提取
2.实体识别
3.内容分类
4.文本
5.主题模型
6.嵌入

常见的文本结构化算法

1.TF-IDF算法 tf词频 idf逆文档频率
2.

最大岛屿面积

题目

Given a non-empty 2D array grid of 0’s and 1’s, an island is a group of 1’s (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.

Find the maximum area of an island in the given 2D array. (If there is no island, the maximum area is 0.)

Example 1:

[[0,0,1,0,0,0,0,1,0,0,0,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,1,1,0,1,0,0,0,0,0,0,0,0],
[0,1,0,0,1,1,0,0,1,0,1,0,0],
[0,1,0,0,1,1,0,0,1,1,1,0,0],
[0,0,0,0,0,0,0,0,0,0,1,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,0,0,0,0,0,0,1,1,0,0,0,0]]
Given the above grid, return 6. Note the answer is not 11, because the island must be connected 4-directionally.
Example 2:

[[0,0,0,0,0,0,0,0]]
Given the above grid, return 0.
Note: The length of each dimension in the given grid does not exceed 50.

解析重点

1.当遇到岛屿时我们要怎么计算岛屿面积呢？递归从四个方向计算面积，当遇到0时终止递归。注意，当递归到地图边界时也需要终止递归计算。
2.当一个岛屿我们从不同位置开始计算时，会出现重复计算的情况，我们可以把搜索过的位置置为0，后续就不会再计算了。
3.多个岛屿求最大面积，我们只需要保存最大值，然后每次碰到岛屿与之比较即可。

java代码

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

class Solution {
    public int maxAreaOfIsland(int[][] grid) {
        int max = 0;
        int rows = grid.length;
        int cols = grid[0].length;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                int maxAera = maxAera(i, j, rows, cols, grid);//计算岛屿面积
                max = Math.max(maxAera, max);//计算最大岛屿
            }
        }
        return max;
    }

    private int maxAera(int i, int j, int rows, int cols, int[][] grid) {
        if (i < 0 || i >= rows || j < 0 || j >= cols||grid[i][j] == 0) return 0;//当当前点等于0或者到达边界时，直接返回0
        grid[i][j] = 0;//搜索过的点置为0
        return 1 + maxAera(i - 1, j, rows, cols, grid) + maxAera(i + 1, j, rows, cols, grid) + maxAera(i, j - 1, rows, cols, grid) + maxAera(i, j + 1, rows, cols, grid);//当前点是陆地时，从四个方向开始搜索
    }
}

翻转字符串里的单词

题目

Given an input string, reverse the string word by word.

Example:

Input: “the sky is blue”,
Output: “blue is sky the”.
Note:

A word is defined as a sequence of non-space characters.
Input string may contain leading or trailing spaces. However, your reversed string should not contain leading or trailing spaces.
You need to reduce multiple spaces between two words to a single space in the reversed string.
Follow up: For C programmers, try to solve it in-place in O(1) space.

解析重点

1.先出除多余的空格，然后根据空格切分字符串，将切分后的字符串数组翻转，然后连接即可。

java代码

1
2
3
4
5
6
7

public class Solution {
    public String reverseWords(String s) {
    String[] words = s.trim().split(" +");
    Collections.reverse(Arrays.asList(words));
    return String.join(" ", words);
}
}