目录

文献总结

相关知识

代码环境搭建

文献总结

顶会文献

《Distilling Discrimination and Generalization Knowledge for Event Detection via ∆-Representation Learning》ACL2019

• 概述: 为解决事件检测系统在泛化知识上识别触发词学习方面较差的现象，提出一种通过有效解耦、逐步学习、自适应融合事件表示来在分化、泛化知识进行学习
• 优点: 提高了算法在泛化知识方面学习的能力，加强了以前事件检测难以识别出的隐藏的事件触发词的抽取能力
• 不足:技术路线较复杂，分化知识和泛化知识分别抽取特征表示会不会产生干扰
• 技术路线: 词预训练模型: 基于ELMo模型->△-特征表示学习->用自注意循环神经网络(attention-RNN)学习分化知识的特征表示->用DMCNN模型来学习泛化知识的特征表示

GPU tensor不能直接转为numpy数组，必须先转到CPU tensor

torch.cat()用于将多个张量在某维拼接

1
2
3
4
5
6
7
8
9
10
11
12
13

# C为A和B在0维拼接的张量
C=torch.cat((A,B),0)

即
A=torch.ones(2,3)
# A = [[ 1.,  1.,  1.],[ 1.,  1.,  1.]]

B=2*torch.ones(4,3)
# B = [[ 2.,  2.,  2.],[ 2.,  2.,  2.],[ 2.,  2.,  2.],[ 2.,  2.,  2.]]

C=torch.cat((A,B),0)
# C = [[ 1.,  1.,  1.],[ 1.,  1.,  1.],[ 2.,  2.,  2.],[ 2.,  2.,  2.],[ 2.,  2.,  2.],[ 2.,  2.,  2.]]

目录

一、安装Anaconda

二、安装Pytorch

一、安装Anaconda

进入
Anaconda官网
下载Anaconda

笔试

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

3.11 19:00 美团
3.12 19:00 拼多多
3.13 19:00 百度
3.23 19:00 腾讯音乐
3.26 20:00 腾讯
3.27 14:00 PayPal
3.28 19:00 蚂蚁
3.29 19:00 字节
3.31 19:00 恒生
4.02 19:00 吉比特游戏
4.06 19:00 shein笔试
4.18 14:00 字节
4.22 14:00 网易
4.26 14:00 Amazon
4.26 19:00 华为
5.13 19:00 字节
5.14 20:00 华泰证券

面试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

3.21 16:00 字节一面
3.22 15:00 美团一面
3.22 19:00 蚂蚁一面
3.23 14:00 携程一面
3.23 15:00 携程二面
3.31 9:30 PayPal一面
3.31 14:10 携程HR面
4.11 11:30 恒生一面
4.14 19:00 美团一面
4.20 11:00 美团二面
4.24 11:00 shein一面
4.27 14:30 腾讯一面
5.16 10:00 腾讯云一面
5.17 9:00 腾讯云二面
5.25 21:00 腾讯云HR面

24届暑期实习

1.美团

笔试3.11

• 1.给一个由数字组成的字符串，你可以任意将其中一个数字改成其他任意数字，目标是得到一个相邻数字不能相同的字符串，求最小修改次数
  • 开记忆数组dp[i]来记录dp[i]是否被修改，已AC
  • 思路为比较s[i]和s[i+1]是否相同，如果相同的话就要去改s[i+1]，res++
    • 但是如果i是之前已经被修改了，那说明这一次不用改(因为实际上i已经被改成与i-1和i+1都不同的一个理想数了)，res不用增加
• 2.在n*m的矩阵里走，每个点可能是红色或蓝色，同色不用花钱，走到不同色需要花固定k个金币，每走到一个点可以获得对应金币，求整个过程中能获得的最大金币数量
  • 动态规划，卡36%
• 3.给一个流星出现的数组和一个对应的消失的数组，求能看到最大数量流星的数量和时刻数
  • 同lc2251花期题，把出现和消失放一个数组，然后排序，最后再从头遍历一遍，维护一个当前流星的数量now，已AC
• 4.两个坦克在16*16上走，给两个256长度的字符串表示两个玩家的操作命令，可以操作它们移动转向、开火，不能走对方走过的路径，摧毁对方或者走的路比对方多就获得胜利，输出获得胜利的玩家和回合数
  • 常规字符串处理题，卡45%
• 5.一个二叉树，每个节点可能是红色或蓝色，如果某节点的子树红的和蓝的数量一样就称其平衡，求这颗树的平衡节点数
  • 用递归，没时间做了

技术面3.22

• 1.介绍一下自己
• 2.项目
  • tt核心链路
    • 这个日志事件处理的qps是多少
    • kafka处理的频率是什么，多久触发一次
  • 深挖秒杀系统的结构设计
• 3.数据库
  • mysql的引擎有几种，这三种分别有什么区别，mysql默认的是哪种，行锁是哪个引擎默认加的
    • InnoDB：mysql默认引擎，用于事务，支持行锁，适合大规模数据
    • MyISAM：不支持事务，适合小规模
    • Memory：数据放到内存中
  • 索引的实现方式，B+树为什么好
  • 跳表为什么快，既然跳表和b+树这么像，为什么mysql要有b+树而不是跳表
    • b+树的深度浅，每次读一个节点要一次IO，减少了IO次数
    • b+树的IO次数少，b+树的节点可以存多个关键字，并且单个节点可以与磁盘页对齐(16kb)，这样一次IO就可以传输一个完整节点。而跳表可能出现跨页IO
    • b+支持范围查询和排序操作，跳表只支持单个关键字的查找
    • Innodb引擎出现的时候，跳表还没得到广泛应用
  • mysql一张表的qps
  • 事务的隔离级别、特性，会出现什么问题
  • Innodb是怎么解决幻读的
    • 用next-key lock机制解决，里面包含间隙锁和行锁，间隙锁会锁上记录之间的间隙，比如对5到10行的记录上next-key lock就是由(5, 10)之间的间隙锁和加在10上的行锁组成 lock间隙锁锁定的是两个索引之间的间隙，而next-key lock会锁定多个索引区间
  • 数据库的锁底层是怎么实现的，类似间隙锁，xx锁这种
    • InnoDB行锁是通过给索引上的索引项加锁来实现的，而不是给表的行记录加锁，通过索引检索数据才使用行级锁，否则将使用表锁
  • Redis为什么快，既然是串行的那应该慢呀
    • 因为Redis是单线程的，减去了CPU切换不同线程的开销，并且Redis是在内存运行的
  • Redis的数据类型是怎么实现的
  • Redis的多路复用模型怎么实现的
• 4.编程语言
  • 了解过java结构么，介绍一下jvm
• 5.算法题
  • 翻转链表
  • 给一个字符串，求最长不含重复字符的子串长度
    • 写了滑动窗口解法后，面试官要求不要用双层循环，改成用一个set存已经遍历的字符，对应right新遍历到的字符如果set里面已经有了，那么left就直接前进到set里存的下标后一个位置

一个小时。对基础八股问得少，都是变形和进阶。开始觉得没希望了，最后编程题秒解感觉面试官就又想捞了，最后说语言和基础不是最主要的，主要考察反应和逻辑能力

技术面4.14(直播)

• 1.介绍一下自己

技术面4.20

• 1.介绍一下自己
• 2.深挖tt生产链路
  • hive2es这一步是怎么做的，用什么语言实现的
  • 如何保证hive和es里的数据一致
  • 对实时性和准确性的要求是什么
• 3.算法题
  • 给一个n*n的数组，从左上角开始按对角线依次打印数组
    • 用队列撕出来了，每一次box()运行都会去打印队列里的全部元素，并且同时判断(j+1,i)、(i+1,j)合不合法，若合法则放入队列进行下一次打印

2.拼多多

笔试3.12

• 1.压缩字符串，给一个”1a3b2c”的压缩字符串，还原它本来的形式”abbbcc”
  • 遍历，维护一个count，然后遇到字符就加count个该字符，并把count置0，AC
• 2.有n个敌人，每个敌人有不同的血量，有两种操作(1)对当前敌人和后一个敌人造成1点伤害(2)直接秒杀当前敌人
  • 贪心，只有当当前敌人血量为1时才用(1)，否则(2)永远要更划算，AC
• 3.有三个活动(A,B,C)，每个活动分别有人数上限和每个人参加的费用，参加团建的有N个人，每个人有一个或多个想参加的活动，但每个人最多只能参加一个活动。请问如果能满足所有人都参加活动，请输出最少的团建活动的总费用，如果不能满足所有人都参加活动，请输出能满足最多参加活动的人数。
  • 网络流。没做出来，贪心骗了75%
    • 网络流是，有一个起点和一个终点，它们之间有很多其他点，这些点之间有流量大小不同的管道，输入起点的流量是无穷大，求最后终点能得到的最大流量
• 4.给一个每天营业额的数组，输出一个当前营业额平均数组和一个当前营业额中位数的数组
  • 大根堆和小根堆实现中位数，sum累加实现平均数，AC

3.百度

笔试3.13

15道单项选择、5道多项选择(错选不得分，少选得1/3)，涉及OS、计网、mysql、linux和C++语法(指针最爱考)，选择题共70分

• 选择题知识点：
  • slelect 1和select null会返回一个行数和原表一样的临时列，列值分别为1和null
    • select null不能用count()和sum()
  • const直接修饰的不能变，例如const *p则p指向的地址不能变，* const p则p的值不能变
• 1.给一个字符串，判断其能不能重新排列后生成”Baidu”
  • 将”Baidu”排序，然后再将字符串排序后比较是否相等即可，AC
• 2.给一个整数x，请你生成一个字符串使得该字符串的回文子串数量正好等于x，该字符串只能包含’r’’e’’d’
  • 暴力生成字符串，过了32%
  • 正确解法：
    • 首先记住，同一个字符构成的字符串，它的回文子串数量为n*(n+1) / 2，即和等差数列求和公式差不多
    • 因此先从1开始遍历，去找最大的n满足n*(n+1) / 2 <= x，然后就往字符串里填n个’r’
    • 然后还需要增加x-n*(n+1) / 2个回文子串才能满足要求，这时就依次填’e’’d’’r’进去，按这个顺序填每次多填一个数，只会新增一个回文子串
• 3.给一棵二叉树的每条边和节点颜色数组，每个节点是蓝色或红色，定义每条边的价值为删掉这条边后形成的两部分树，同色连通块的差值绝对值
  • 想用并查集来做，但是并查集保留信息不够，0%
  • 正确解法
    • 用dp[i]存以i为根节点时，同色连通块的数量
    • 断开某条边的会产生一个左节点、一个右节点
      • 左节点的同色连通块 = 总的同色连通块数量 - dp[右节点]
        • 如果左节点和右节点颜色一样， 左节点的同色连通块还得+1
      • 此时断开该边的价值 = abs(左节点的同色连通块 - dp[右节点])

5.米哈游

笔试3.20

10道单项选择、10道多项选择

• 选择题知识点：
  • stat file能查看文件的信息，包括indoed
  • 进程从运行态变成就绪态是因为时间片用完了
  • TCP三次握手第一次的底层，是把TCP头的SYN标志位置1
• 1.一个矩阵每个位置只能是R、G、B三种颜色，小红是色盲她会把G当做B，请问小红眼中的同色连通块数量，比起实际的同色连通块数量少了多少
  • 并查集，AC
  • 实际的一个并查集，色盲的一个并查集，遍历每个位置然后判断往右下判断是否同色，若同色就连在一起
• 2.有两个字符串s和t，你可以无限次对s进行加”mhy”或者减”mhy”，请问s能不能变成t
  • 哈希表，AC
  • 记录s和t中每个字符出现的次数，然后mhy三个字符单独判断一次差是否相等，再对其他字符进行判断
• 3.给一个数组，求满足1.后一个数是前一个数的倍数 2.数组长度大于1的子数组数量
  • 用dfs做，20%
  • 正确做法：最长递增子序列的贪心法
    • 先sort()排序，dp[i]表示以nums[i]结尾的子序列的个数
    • 双层循环
      • 外层循环ans += dp[i]，表示以nums[i]结尾的子序列的个数
      • 内层循环遍历j = 1; j * j <= nums[i]
        • 如果nums[i] / j存在，dp[i] += dp[pos[nums[i] / j]
        • 如果j存在，dp[i] += dp[pos[j]]
      • pos表示值在nums[i]中的下标，即pos[nums[i]] = i，不存在的值pos置为-1
      • 注意base处理，外层循环的最后还要dp[i]++，但是ans要在这之前，因为ans只包含长度大于1的组合，但是长度=1的组合可以参与下一次的计算

6.字节跳动

技术面3.21

• 1.介绍一下自己
• 2.介绍一下tiktok实习主要参与的项目
  • 广告主查前六天的数据，是会分成查一天实时和五天离线的么
  • 广告主对广告的付费方式有哪几种，采用得最多的是哪一种
    • CPC（Cost Per Click）：按点击次数付费，用得最多
    • CPM（mille）：按展示次数付费，一般用千次展示费用
    • CPA（action）：按转化事件付费，比如下载、注册等
    • CPV（view）：按浏览次数付费，用于视频广告
    • CPS（sale）：按转化金额付费
  • es和mysql的索引有什么区别，为什么es更快
    • ES可以处理非结构化和半结构化的数据，支持一个文档里包含多种类型的数据，
    • ES更快是因为使用倒排索引，将每个词汇映射到包含该词汇的所有文档的ID，搜索时ES无需遍历整个文档集合，只需要在索引中查找包含关键字的文档即可
• 3.计网
  • TCP是在哪一层，IP在哪一层
    • TCP在传输层，IP在网络层
  • 是TCP包含IP包，还是IP包含TCP包
    • TCP里包含IP包
  • TCP报文头里包含什么
    • 源端口号
    • 目的端口号
    • 序列号：占4字节，表示当前报文的序列号，用于保证传输的有序性
    • 校验和
    • 窗口：占2字节，表示接收方所能处理的数据量
    • 标识位：ACK、SYN、FIN等
• 4.操作系统
  • 介绍一下进程和线程，线程独有的资源是什么
    • 栈空间
• 5.数据库
  • 索引的实现方式，B+树为什么好，B+数对比哈希表实现有哪些优点(3个以上)
    • B+树可以实现范围查询，B+树不会有哈希冲突导致效率降低的问题，B+树可以减少I/O开销
  • 跳表为什么快，查询、插入、删除复杂度是多少，为什么
    • 跳表原理是二分查找，所以快。查询、插入、删除的平均复杂度都是logn
• 6.编程语言
  • 介绍一下go的gmp模型，如果此时某个p的本地队列已经空了怎么办，如果此时中央队列也空了怎么办，它会到别的p的本地队列去取么
• 7.算法题
  • 给一个链表1-2-3…-n，返回1-n-2-n-1….这样的新链表，先说思路再动手敲，每种思路说明时间空间复杂度，递归的复杂度是多少
    • 第一个思路：用数组存，然后双指针遍历赋值
    • 第二个思路：找到中间节点，然后将后面的链表翻转，再双指针遍历赋值
      • 代码没调试好，最后一行一行讲了思路
    • 递归的时间复杂度=递归函数的时间复杂度 * 递归深度，空间复杂度同理
      一个小时。对基础八股问得少，都是变形和进阶。
• OSI七层模型每层的协议都要背
• 编程题调试困难，一定要及时提出可不可以用自己本地ide调

笔试3.29

• 1.给一个数组和一个k，只能进行两个元素交换位置的操作，求最少需要几次操作才可以让值为k的元素互相相邻
  • 贪心法过54.55%
• 2.
  • 77.78%
• 3.给一个整数k和n个长度为3的数组，每个数组{a,b,c}表示可以画一条ax+by+c=0的直线，其中(x,y)是二维平面的坐标，你可以画k条直线，求所有方案中直线交点的最大数量，注意若3条直线相交于同一点，则交点数量可记为3个
  • 骗14.81%
• 4.给三个数组和k，分别表示第i场比赛，正常比赛收益、作弊收益、作弊风险，如果作弊的话可以获得作弊收益，但要承担作弊风险，求作弊风险 < k的情况下，最大收益是多少
  • 贪心法过25%

笔试4.18

• 1.
  • AC
• 2.给一个信号塔的强度数组，每个信号塔的信号强度取别的信号塔辐射到该处的最大强度，f[i] = f[j] - abs(i-j)*c，求最终每个信号塔的强度数组
  • 暴力过75%
• 3.操作系统处理字符串题，给文件夹路径，然后再给文件夹移动命令，求最后每个文件夹包含的子文件夹数
  • AC
• 4.小红的新函数，实现一个函数f()，输入i，返回i的二进制的末尾最长连续1的个数，给一个n，要求返回小于n的f(i)之和
  • 备忘录过70%，内存超了

笔试5.13

• 1.矩阵旋转题，给一个字符矩阵，然后问左移n位后的第i行j列是哪个字符
  • AC，数学计算解法，一开始处理边界时间花太长，这种题应该写例子在一边来分析，不要纯抽象，并且一旦花时间长就先做后面的换一下思路，回来再做
• 2.和4.18一模一样的信号塔题
  • AC，通过计算两个辅助数组dp1,dp2来算
    • dp1[i]存i后面的最大f[j]-c*j
    • dp2[i]存i前面的最大f[j]+c*j
    • 最后的ans[i] = max(dp1[i] + c*i, dp2[i] - c*i)
• 3.池塘上有n片荷叶，荷叶有分值，每次可以跳x步，x是2或5的倍数，跳到荷叶可以获取荷叶的分值，求跳到岸边的最大分值和
  • 10%，题目有点问题，没解释题意
• 4.给一个书的高度数组和k，每层书的最大高度差不能超过k，求书架每层的最大宽度和满足这个最大宽度和的状态有几种，注意：这个宽度指的是如果一种放书方案里，放书最多的层放了3本书，那么这个书架的宽度就是3
  • 40%，值域二分法求出来了书架每层的宽度，但是具体状态没时间写了，用回溯法应该能AC

7.蚂蚁

HR面3.22

• 1.介绍一下自己
• 2.介绍一下两段实习都做了什么
  • 碰到的项目难点有什么，怎么解决的
• 3.学习模式
  • 平时是怎么学习的，会看文档和源代码么
  • 如果重新让你学一门编程语言OK么，你会怎么学
• 4.上线规范
  • 业务方提不合理的需求怎么处理
  • 会从技术架构上去帮业务方解决问题么

半个小时。基本都在问工作的事，没问技术，应该是非技术的HR

笔试3.28

9道单项选择、6道多项选择

• 选择题知识点：
  • cache-Control字段的常用值有：public、private、no-cache、max-age
  • 信号量A初值为10，若干进程对A进行25次P操作、9次CV操作后，此时有几个进程在等待A
    • P操作会对信号量+1，CV操作会对信号量-1，信号量负的值表示有几个操作正在等待，10-25+9 = -6，应该有6个进程在等待
  • Linux的文件权限操作chmod
    • 三位数字
      • 第一位表示文件所有者，第二位表示同组用户，第三位表示其他用户
      • 7表示可读可写可执行，6表示可读可写，0表示无任何权限
    • u+x表示给拥有者加执行权限，o-r表示给其他用户减读权限
  • DMA方式和I/O通道
    • DMA：有专门的硬件DMA控制器直接读取内存中的数据，CPU仅需要启动传输并在传输结束时进行中断处理即可，例如硬盘、光驱
    • I/O通道：专门的硬件设备控制外设与主存之间的数据传输，CPU仅需与I/O通道进行简单的指令交互，例如视频采集卡、音频处理卡
• 1.给一个n，你需要找出c = a + b的最大c，其中a、b、c都是质数
  • 最速求质数函数+备忘录，AC(这里要注意1不是质数)
• 2.给一个n，你需要构造一个不含重复元素的n行数组，第1行有1个元素，第2行有2个元素以此类推，其中需要满足A[i][j] ^ A[i+1][j] ^ A[i+1][j+1] = k，这个k可以你自己指定
  • 骗6%
  • 正确解法：队首固定为
• 3.给一堆零件的生产时间和生产条件，其中生产条件里会包含不定数量的其他零件，最终该零件的生产时间=它本身的生产时间+生产条件要花的时间，请输出每个零件的实际生产时间
  • 用vector套pair<int,int>的结构存储 + 拓补排序，AC

8.携程

技术面3.23

• 1.介绍一下自己
• 2.项目
  • 介绍一下在tiktok都做了什么
  • 深挖秒杀系统结构设计
    • 秒杀系统最重要的是什么，怎么实现的
      • 异步、削峰
• 3.数据结构
  • 介绍一下数组和链表，它们有什么区别
  • 介绍一下哈希表， 负载因子应该怎么设置
    • 负载因子=已保存节点空间/哈希表空间，一般设为0.75
  • 介绍一下快速排序和堆排序
• 4.计网
  • 介绍一下OSI七层模型，平时使用哪层比较多
  • 介绍一下http，介绍一下get和post请求，它们有什么区别
  • 如果我想http实现长连接应该怎么做
• 5.数据库
  • mysql用的引擎是什么，他有什么特点
    • Innodb，默认行级锁，支持事务，实现了事务的四大特性和隔离级别
• 算法：手撕快排(想出堆排的，考虑到拿纸写有点复杂就改成快排了)

一个小时线下面试。基础数据结构问得很细，http请求也问得很细，最后手写快排

技术面3.23

• 1.介绍一下自己
• 2.项目
  • 深挖河海大学校友平台
    • 用户状态是怎么保存的，token放在请求的哪里
  • 深挖tt核心链路
  • 深挖秒杀系统结构设计
    • 大流量打过来，怎么削峰，你这个拦截接口是怎么设置的
      • 拦截接口，相当于另起一个服务
• 3.数据结构
  • 介绍一下栈和队列
• 4.计网
  • 介绍一下get和post请求，它们有什么区别
  • 你理解的跨域问题是什么，怎么解决跨域问题的，不同服务之间调用会有跨域问题么
• 5.数据库
  • 之前的项目里你建过哪些库和表，怎么设计的
  • mysql的索引用的是什么，有什么特点
  • redis的哪种数据结构是有序的
    • zset
  • 了解MVCC么，介绍一下
    • 目的：MVCC通过保存数据的历史版本，根据比较版本号来处理数据是否显示，从而达到读取数据的时候不需要加锁就可以保证事务隔离性的效果
    • 实现：InnoDB中的MVCC实现是通过undolog日志实现的，执行更新操作时，会把更新前的数据放入undolog里面，并通过隐藏的回滚指针roll_pointer指向。其他的事务，如果需要查询该记录，就会去undolog里面找这个记录的最新历史版本
    • 好处：MVCC 最大的好处是读不加锁，读写不冲突，极大地增加了 MySQL 的并发性。通过 MVCC，保证了事务的隔离性
• 算法：手撕队列实现栈(一开始也问栈实现队列的思路)
  • 两个队列q1、q2
  • push正常压入q1
  • pop就q1一直出队列送给q2，然后只剩一个的时候就返回这最后一个元素

一个小时线下面试。校友平台和秒杀系统项目问得很细，包括结构，在写队列实现栈的时候有点卡逻辑了，忘了转移的时候保留最后一个数作为弹出

HR面3.31

• 介绍一下自己
• 什么契机让你想转专业
• 老家是哪的，对未来工作的城市有什么打算，在上海有亲戚吗
• 英语能力怎么样，如果让你现在来一个英语介绍可以么

30分钟。HR面主要考察性格职业规划等，第一次碰到女面试官。实习薪资大概4K，有房补和餐补。出勤日满50天可申请转正PPT答辩，会为每个实习生预留HC，实习生转正完后剩余HC才会外放。

5.06已Offer，5.22入职，感谢携程

9.腾讯娱乐音乐

笔试3.23

• 给一棵二叉树，它有n个节点，你可以用1-n的数字为每个节点赋值，不允许重复使用，如果满足奇数层和与偶数层之和的差的绝对值 < 1，那么就返回这棵树，否则返回空指针
  • 15%
• 给一个字符串，字符串的价值=长度*字符种类，现在要把它分为k个子串，设m为所以子串中价值最大的子串的价值，求最小的m
  • 用值域二分法，细节没处理好只过了25%
  • 先确定子串最小价值为1，最大价值为整个字符串的价值
  • 然后用二分查找去判断mid是否合法
  • 写一个bool isValid()来判断是否可以分割成子串最大价值不超过mid的情况
    • 用贪心法，一旦加上下一个字符价值超过mid，那么就在该处分割，后面属于新的字符串
    • 最后判断分割出来的子串如果小于等于k就返回true，否则返回false
• 求相邻的字符对数，例如”aaabb”，相邻字符对数为2+1=3
  • AC

10.腾讯

笔试3.26

• 给一个链表，要求两个链表为一组，然后两个组整体交换位置，例如1->2->3->4要变成3->4->1->2
  • 四个指针，AC
• 给n个字符串，要求从每个字符串里取一个字母构造成一个长度为n的新字符串，这个新字符串里不能有相同的字符，请问有几种构造方法
  • 回溯+备忘录，AC
• 给两个数组A，B，数组长度都为N，构造一个数组C满足以下条件1.长度为N 2.数组元素范围为[1,N]，且元素值不能重复 3.如果B[i]> B[j]，那么一定要保证C[i]> C[j]，注意这里的i<j 4.数组C与数组A每个元素之差的和的绝对值最小，并输出这个值
  • 骗14%
  • 正确解法：构造pair<int,int>分别存A、B的值，然后优先按B降序排序，B相同的就按A降序排序，然后再用贪心从N开始赋值
• 给一个数组，求他有几个子数组满足里面所有的元素之积==里面所有元素之异或
  • 用前缀数组双层遍历，只过了32%
  • 正确解法：满足要求的子数组，只有可能是若干个1和1个别的数字，下次碰到异或题要细想数学法
    • 先枚举所有连续1的区间，分奇偶求出奇数个1子串的数量，然后就是中间非1往两边扩展1,根据左右的数量算有偶数个1的数量
• 给一个数组和整数k，你可以删除它里面的任何数，让剩余数的最大公约数等于k，求删除的方案数
  • 骗5%
  • 正确解法：分解质因数

技术面4.26，wxg

• 1.自我介绍
• 2.算法题
  • 原地翻转字符串
    • 双指针交换
  • 求n!结尾连续0的数量
    • 统计2、5因子数，或者只需要统计5的，因为n!的2因子一定比5多
  • 判断二叉树是否平衡(左右高度差<=1)
    • 递归
  • 交换第k和倒数第k个链表节点的值
    • 维护两个指针，一次遍历解决
  • 思维题：有一群人，眼睛是棕色或蓝色的，所有蓝颜色眼睛的人必须离开
    • 1. 每个人都看得见别人眼睛的颜色，但不知道自己的。别人也不可以告知
    • 2. 每天白天，岛主会宣布岛上是否还存在蓝眼睛
    • 3. 蓝色眼睛的人如果「确定」自己是蓝眼睛，必须无条件乘坐当天晚上的渡船离开
    • 那么请问所有蓝眼睛的人，要花几天才能离开这个岛？
• 3.八股
  • TCP三次握手，改成两次行不行，如果按两次算建立连接，那么此时发数据会有什么错误
  • 那这个数据包在传输过程中被修改怎么办？ 那连校验和也修改了怎么办？
    • 校验和、https加密
  • https的加密方式，什么时候传私钥公钥，什么时候是对称加密
    • s端传证书的时候会把公钥传过去，然后c端用公钥加密了对称秘钥后再传回来，这时s端用私钥解密即可得到对称秘钥了
  • 项目里mysql的一张表大概是多少数据量，如果特别大，有什么办法去解决慢和被打崩的问题
  • 你使用redis的时候会设置过期时间吗，时间到了redis会怎么去删除？

11.PayPal

1
2
3
4
5
6
7
8

- 一面官方考点：
    - 数据结构：数组、字符串、链表、动态数组、哈希表、栈、队列、二叉树、平衡树、红黑树
        - 在无序数组里面找到最大/最小的第N个数：用优先队列做，要求实现就手撕堆排序
        - 在一个环状链表中交换首尾节点：新增pre指针来记录
        - 在二叉树中算出两个节点之间的距离：先找最近公共祖先，然后祖先往下分别去找它俩
    - 算法：搜索算法、排序算法、模式匹配、分而治之、动态规划
        - 给一个有序数组和目标值x，找到和为x的组合：dfs+回溯
        - 找到所有1(...00....)1的模式，在一个字符串中：kmp匹配算法

笔试3.27(HackerRank)

• 6道选择题，3道编程题，选择题考数据结构和读代码
  • 编程题1：数据库查表，查成绩大于平均成绩的学生的信息
    • AC
  • 编程题2：用Java实现3个有继承关系的类，打印出对应string，包含了类成员函数重载的使用
    • AC
  • 编程题3：n*m矩阵，为0的有地雷不可以走，求从(0,0)走到(n-1, m-1)有几种走法
    • 常规动态规划题，AC

面试3.31

• set和array的区别，set是怎么实现唯一的
  • 唯一性。set的底层是红黑树，但是保证唯一性用的是哈希表
    • 保证唯一性的底层实现是，先判断key得到的hashcode有一样的么，如果有，那么再调equals()去检查
• 如果发生哈希冲突应该怎么处理，哈希表的时间复杂度是多少
  • 链表法
• 二叉树插入元素的时间复杂度
• 动态数组删除元素的时间复杂度
• unordered和普通的数据结构有什么区别，比如unordered_map和map
  • 底层：unordered_map是hash_map，map是红黑树
    • hash_map是由vector和链表构成，每个vector的位置连一个链表，声明的时候就会自动初始化一个vector去占用空间(质数，不同编译器用不同的质数比如53)
  • 顺序：unordered_map是插入顺序，map是按key从小到大排列的
  • 插入、查询、判断key值开销：unordered_map是O(1)，map是O(logn)
• 算法：
  • 1.将两个有序数组合并成一个有序数组
  • 2.给一个数组，判断里面相同数字出现的次数是否唯一，例如[1,1,2,3,3,3]输出true，[1,2]输出false

开局就英语交流，然后让开hackerrank并共享屏幕作为待会代码测试的平台，然后英语介绍自己部门的业务，并要求做个自我介绍。两个面试官，一个负责八股，八股主问数据结构，一个负责算法。外企题目难度不高，但是英语需要增强，最后面试官也给建议如果要面外企的话口语得再练练

12.恒生电子

笔试3.31

• 不定项选择题+sql题+算法题
  • 非对称加密算法有RSA和DSA
• 1.一个N位数，他的每一位的N次方合起来等于他本身，那么就把他叫做超完全数字不变数，给你一个n，求小于n的所有超完全数字不变数
  • 暴力枚举+剪枝，AC
• 2.股票交易，可操作次数k次，初始资金为M，给一个每天股票的单价，求最大收益
  • 股票交易4变形题，改一下初始状态和转移方程即可，AC

13.吉比特游戏

笔试3.31

• 选择题20道+填空题6道+2道算法题
• 1.给两个字符串s1和s2，s1可以删除任意个字符，求s2与s1可以匹配的最大下标，例如s1=abcdacd，s2=ad，那么结果应该返回4
  • 枚举+剪枝，过80%，剩下20%应该是没处理不能匹配的情况
• 2.给m条无向边，从0点出发，每个点最多访问2次，求访问到所有点的最小花费
  • 骗10%
  • 正确做法：状态压缩dp，这是一个典型的求最短哈密顿路径
    • dp[S][i]，S是用二进制1001的形式表示经过哪几个点，i表示以i点结尾
    • s-t的最短哈密顿路径指的是，从s点出发到t点要过所有点的最短距离

14.Shein

笔试3.31

• 单选题10道+多选5道+1道sql+1道算法
  • 解决哈希冲突
    • 开放寻址法：从发生冲突的那个位置起，按照一定的次序，放到空闲的单元
      • 线性探测、平方探测、双重散列探测、伪随机数探测
    • 链表法：也叫拉链法
    • 再哈希法
    • 公共溢出区法
• 1.给一张回答问题表，求每一天的回答问题用户数/回答数，保留两位小数
  • 难点在于用CAST() AS DECIMAL(10，2)这个模板转保留两位小数，AC
  • slelect (CAST(COUNT(DISTINCT(user)) / COUNT(date)) AS DECIMAL(10, 2)) AS res from xx GROUP BY date
• 2.求一个字符串里，最长的不含重复字符的子串
  • 双指针，AC

面试4.24

• sql的having语句

  1 2 3 4

  select user_id, count(user_id) t from xx group by user_id having t >= 3

• 这个语句是一个慢查询，你分析可能是什么原因
  • 没有用到索引
  • 内存不足
  • 查询出的数据量过大
• 解决慢查询用explain关注哪些指标
  • type：用来表示该sql底层是怎么扫描的，值有：all全表扫描，index全索引扫描、null表示不用去表里查可以直接得到结果
  • possible_keys：可能用到的索引列
  • key：实际用到的索引列
  • Extra：底层用的是哪种检索方式，值有：Using where用where来处理结果，Using index condition表示用索引
• 如果sql没问题的话，从哪里可以解决
  • 系统架构上，比如用redis增加前置缓存、分库分表
• redis断电会丢失吗？
  • 可以采用持久化策略保证，但是不能保证完全不丢失，例如60分钟是记录时间，最多可能会丢失59分钟的数据
• rabbitmq如何保证消息不丢失，如果发送了多次相同的消息要怎么处理
  • 消息丢失有三种
    • 生产者发给mq途中丢失：开启confirm机制给每个消息分配一个id，生成者发送消息后mq收到返回ACK，没收到返回nack
    • mq因为断电等情况丢失：设置消息持久化和镜像集群
    • mq发给消费者途中丢失：开启AKC应答机制，即消费者收到后给mq回一个ACK
• java频繁触发GC可能是什么问题
  • 堆空间不足
• 三次握手改成二次行不行
  • 不行
• 四次挥手改成三次行不行，其实是有三次挥手的而且速度比四次快很多
  • 四次挥手是考虑到S端要关时，C端数据还没传输完成
  • 三次挥手是存在的，
• TCP是全双工的吗？ 为什么打电话只要两次握手，TCP要三次
  • 打电话是进程阻塞的，TCP是可以多进程的
• 有试过抓包吗，看看里面的东西

15.网易

雷火笔试4.23

• 单选题10道+多选5道+2道问答题+2道算法
  • HTTP是应用层协议，ICMP是网络层协议
  • 什么是负载均衡，负载均衡的算法有哪些，分别阐述优缺点
    • 轮询负载：轮流分配到后端服务器上，均衡地对待每台服务器，简单易懂，但可能出现负载不均衡
      • 可以加权改进
    • 随机负载：通过随机算法，随机将请求分配给后端服务器，易于实现，但可能出现负载不均衡
      • 可以加权改进
    • 源地址哈希法：和一致性哈希算法原理一样，负载均衡性提升，但需处理哈希冲突和保证hash环均匀分布
  • 什么是分布式系统的切片策略，切片策略有哪些
• 1.给一个数组和需要切分的块数k，切分策略的得分是每个块数k的起始值+终止值，求切分策略的得分最大值和最小值的差，例如(1,2,3,4)，k=2可以被切成(1)、(2,3,4)，它的得分是(1+1) + (2+4) = 8
  • dfs()+回溯，暴力模拟解决，AC
• 2.给一个矩阵和a、b两点的坐标，求a走到b需要的最短时间
  • bfs()，AC
  • 用队列模拟，每次把能走到的新坐标加入到队列里面进行下一次循环，出现b点时，返回答案

16.Amazon

笔试4.26

• 给一个表示包裹重量的数组，有两种运输方式，一是运送同等重量的包裹2个，二运送同等重量的包裹3个，求最少能把包裹运完的次数，如果不能运完返回-1
  • 贪心，AC
• 给一个数组和k，长度为k的子数组如果里面不含重复数字就可以算作合法，求合法子数组的最大和
  • 滑动窗口，AC

17.华为

笔试4.26

• 1.给相互依赖的模块关系，如果某模块的依赖模块在之前都已经初始化则该模块才可以初始化，求需要几轮初始化才可以完成所有模块(100分)
  • 拓补队列，AC
• 2.模拟一个资源池，要求实现1.分配n个资源，2.分配指定id资源，3.释放资源，最后返回资源池的第一个资源id(200分)
  • 链表+哈希表模拟，AC
• 3.给一个初始点长草坐标数组，每隔一天会向上、下、左、右、左上、左下、右上、右下扩张，求最少经历多少天会出现某个坐标拥有M种草(300分)
  • 骗6%
  • 正确解法：二分查找 + 离散化 + 差分数组
  • 自己思路：
    • 给每一个初始点确定一个长到target点的最短时间
    • 然后用二分值域法，去找这个最少天数能拥有M种草

18.腾讯云智

笔试5.16

• 25道单选59分 + 5道填空10分 + 2道编程40分
• 1.给一个字符串，求它里面的”CHN”子序列有多少
  • AC，遍历一遍，维护当前的遍历过的C数量和之前能组成的”CH”数量
    • 遇到C就++，遇到H就+=C，遇到N就+=H
• 2.给两个有序数组，你需要从每个数组里面挑一个数，求最大的k个这两数之和
  • AC，维护一个大根堆存(i,j)，每次从大根堆里压出的时候，把(i-1,j)和(i,j-1)压入堆，为避免重复，用备忘录记录已经压入过的组合

面试5.16

• 介绍一下你认为最有技术含量的项目，这个项目是做什么的，难点是什么
• unordered_map和map的区别和底层
• 如果让你设计一个应用层的协议你会考虑什么，怎么去识别包的长度，如果包里本身包含这个特殊字符怎么办
  • 用socket封装实现，基于TCP去实现，考虑首部包含资源的位置、请求的方式、协议版本
  • 1.首部加一个len字段 2.用特殊字符做分割，换一个少用的字符或者加转义符/
• C++的编译过程分几个阶段
  • 预编译->编译->汇编->链接->执行
• Linux下查找文件用什么命令
  • find “xx”表示在当前目录及其子目录查找xx
• Linux下用C++编程的步骤
  • 用vim编写.cpp文件
  • 用g++编译得到.out文件
  • 用./xx.out执行
• mysql怎么加索引，什么时候要去加索引
  • alter table 表名 add 索引类型 列名
  • alter table 表名 drop xx
• go的channel底层怎么实现的，如何用它来实现并发，如果channel满了会怎么办
  • ring buffer + 发送队列 + 接受队列

面试5.17

• 自我介绍一下
• 怎么理解不同的技术栈，你觉得后端是一个什么样的定位
• 介绍一下tt工作的背景，这个实时是多少时间，如果需要更实时一点比如秒级、分钟级应该怎么做
• Hive是怎么实现大数据查询的，mysql为什么不行
  • Hive用MapReduce去分布式查询
  • Hive是将结构化的文件映射成一张表，这个文件是在HDFS上的
• kafka的特性，怎么保证消息队列的下游接受处理到了消息，这个ACK具体是怎么实现的
  • kafka的ack有以下三种策略：
  • ACK = 0 时 发送一次 不论下游是否接收
  • ACK = 1 时，等待下游接收成功即可
  • ACK = -1 时 ，需等待下游将消息同步给消息队列
• C++在linux下怎么断点调试
  • 使用gdb，对某行打上断点
  • 然后在生成二进制程序的时候, 加上 -g 选项
• 了解HDFS么
  • 三大件中的分布式文件存储系统
• 秒杀系统用到了分布式，讲一讲怎么实现的
• 你提到未来可以横向扩展这一点很好，那么如果某一个节点挂掉它需要迁移多少数据？
  • 哈希环上，该节点到上一节点之间的数据
• 如果我想保证在挂掉之后到迁移完成之前，这部分数据用户无感知正常使用应该怎么办
  • 备份节点
• 未来考虑在哪工作
• 近几年大数据很火，需要加强大数据方面的知识，三大件

面试5.18

• 自我介绍一下
• 博客上的文章都是什么，都是自己写的吗，留一下地址
• 介绍一下tt工作的背景
• 介绍一下这个秒杀系统
• 解释一下一致性哈希算法，如果要新增、删除节点具体会怎么做，如何保证负载均衡
  • 迁移一部分数据，虚拟节点
• 超卖问题如何解决，如何保证10w个人抢10个商品
• rabbitmq和kafka的优缺点
  • kafka有ack机制可以保证消息的顺序处理
  • rabbitmq有消息存活时间和延迟/预定消息
  • rabbitmq消息一旦消费成功就会删除，反之处理失败则放回；但kafka会一直保留消息，根据超时时间来删除，可以反复消费消息
  • kafka使用分区的结构，在横向扩展上更有优势
• 系统出问题了怎样定位，用过压测工具么
  • 打断点，延伸到mysql响应过慢，延伸到慢查询
• 详细地介绍client端与server端通信的过程，http和tcp有什么区别，https和http有什么区别，https加密是为了保证什么
  • 应用层http，传输层TCP，三次握手，四次挥手
• 未来考虑在哪工作
• 大数据也属于后台开发的技术栈，需要学习相关的组件

以往经验

1.道远课堂-北京（Python后端）

技术面6.07

• 对简历上写的知识图谱项目感兴趣，询问了采用的图数据库和数据规模以及最后实现功能。

目录

程序设计要求

初期思路

抽象化进行设计

模拟场景

后续延伸

程序设计要求

• 1.仿真场景：划定区域或基于真实地图
• 2.仿真要求：
  • 1）传播过程的模拟（可视化或数字指标变化）；
  • 2）通过恰当指标说明不同场景下各类防疫措施的成效；
  • 3）给出整体防疫建议。