面试概率题大杂烩

从一副52张扑克牌中随机抽两种，颜色相等的概率

$\frac{C_{2}^{1} C_{13}^{2}}{C_{52}^2} = \frac{40}{221}$
54张牌，分成6份，每份9张牌，大小王在一起的概率

$\frac{C_6^1 C_2^2 C_{52}^{7} C_{45}^{9}C_{36}^{9}\cdots C_{9}^{9}}{C_{54}^{9}C_{45}^{9}\cdots C_{9}^{9}} = \frac{8}{53}$
52张牌去掉大小王，分成26*2两堆，从其中一堆取4张牌为4个a的概率

直觉告诉我分不分堆没有关系，这样想的话，答案是：

$\frac{C_4^4}{C_{52}^{4}}$

考虑分堆的话：

1 先求分两堆，4张A出现在同一堆的概率： $ \frac{C_2^1 C_4^4 C_{48}^{22} C_{26}^{26}}{C_{52}^{26}C_{26}^{26}}$

2 在这两堆中，选中4张A同时出现的那一堆：$ \frac{1}{2}\frac{C_2^1 C_4^4 C_{48}^{22} C_{26}^{26}}{C_{52}^{26}C_{26}^{26}}$

3 从选中的这堆中，选4张牌出来是A的概率：$ \frac{1}{2}\frac{C_2^1 C_4^4 C_{48}^{22} C_{26}^{26}}{C_{52}^{26}C_{26}^{26}} \frac{C_{4}^{4}}{C_{26}^{4}}$

一枚硬币，扔了一亿次都是正面朝上，再扔一次反面朝上的概率是多少？

当出现1亿次都是正面朝上的时，有理由怀疑这个硬币两面都是正面。

参考答案: https://www.zhihu.com/question/29683794

有8个箱子，现在有一封信，这封信放在这8个箱子中（任意一个）的概率为4/5,不放的概率为1/5（比如忘记了）,现在我打开1号箱子发现是空的，求下面7个箱子中含有这封信的概率为？

事件A：放信封事件

事件B：1号为空
$$
\begin{align}
p(A|B) &= \frac{p(AB)}{p(B)} \&= \frac{p(B|A)p(A)}{p(B|A)p(A) + p(B|\hat A)p(\hat A)}
\end{align}
$$

已知N枚真硬币，M枚假硬币（两面都是国徽），取一枚硬币抛R次重复都是国徽，问该硬币是真硬币的概率？
一对夫妻有2个孩子，求一个孩子是女孩的情况下，另一个孩子也是女孩的概率

有两个孩子，那么所有的组合情况为：

p(男，女) = 1/4

p(男，男）= 1/4

p(男，男) = 1/4

p(女，女) = 1/4

1/3
有种癌症，早期的治愈率为0.8，中期的治愈率为0.5，晚期的治愈率为0.2.若早期没治好就会转为中期，中期没治好就会变成晚期。现在有一个人被诊断为癌症早期，然后被治愈了，问他被误诊为癌症的概率是多少？

p(cur|早) = 0.8

p(cur|中) = 0.2 * 0.5 = 0.1

p(cur|晚) = 0.2 * 0.5 * 0.2 = 0.02

某城市发生了一起汽车撞人逃跑事件，该城市只有两种颜色的车，蓝20%绿80%，事发时现场有一个目击者，他指证是蓝车，但是根据专家在现场分析，当时那种条件能看正确的可能性是80%，那么，肇事的车是蓝车的概率是多少？ https://www.nowcoder.com/discuss/65344

100人坐飞机，第一个乘客在座位中随便选一个坐下，第100人正确坐到自己坐位的概率是？

1/2

一个国家重男轻女，只要生了女孩就继续生，直到生出男孩为止，问这个国家的男女比例？

1/2

有50个红球，50个蓝球，如何放入两个盒子中使得拿到红球的概率最大

一个盒子中放一个红球，剩下的都放在另一个盒子中

某个一直函数返回0/1，0的概率为p，写一函数返回两数概率相等。

生成两次，当生成的数为01时返回第一个数，10时返回第二个数，11和00时不滚
给你一个函数，这个函数是能得出1-5之间的随机数的，概率相同。现在求1-7之间随机函数，你如何做

1 < x < 5

1 < ax+b < 7

a + b = 1

5a + b = 7

a = 3/2

b = - 1/2

y = (3x-1)/2
X是一个以p的概率产生1,1-p的概率产生0的随机变量，利用X等概率生成1~n的数 https://www.nowcoder.com/discuss/75360 https://www.nowcoder.com/discuss/53916 https://www.nowcoder.com/discuss/47341 https://www.nowcoder.com/discuss/12393

$pr(X=1) = p$

$pr(X = 0) = 1-p$

$C_{2n}^{n} <= n$，求出n，然后依次编码

给你一个硬币，你如何获得2/3的概率

这个其实还是比较容易想到的，把这枚硬币扔两次，以下情况出现的概率相等：

正正

正反

反正

反反

所以如果出现第4种情况则相当于采样失败，继续实验，如果在1~~3种情况中出现1~~2的情况则是一个2323的概率

扔硬币期望掷出‘正反正反……’的序列出来，倘若抛掷硬币没有任何技巧，每次是正是反的概率相同，那么无限地抛掷下去，第一次出错更有可能出在什么地方？

A．该掷正面的时候掷出了反面
B．该掷反面的时候掷出了正面
C．上述两种情况的出现概率相同

这个题目的答案是 A 。下面我们证明，因为该掷反面的时候掷出了正面而挂掉的概率，也就是在第偶数次抛掷时挂掉的概率，精确地等于 1/3 。容易得出，第 2 次就挂了的概率就是前 2 次精确地掷出“正正”序列的概率，它等于 1 / 22 。类似地，到第 4 次才挂的概率就是前 4 次精确地掷出“正反正正”序列的概率，它等于 1 / 24 ；而到第 6 次才挂的概率则是前 6 次精确地掷出“正反正反正正”序列的概率，它等于 1 / 26……所以，在第偶数次挂掉的概率是：
$$
\begin{align}
& 1 / 2^2 + 1 / 2^4 + 1 / 2^6 + 1 / 2^8 + … + 1/2^n \
= & 1 / 4 + 1 / 4^2 + 1 / 4^3 + 1 / 4^4 + … + 1/4^{(n-1)} \
= & (1 + 1 / 4 + 1 / 4^2 + 1 / 4^3 + 1 / 4^4 + … + 1/4^{(n-1)}) – 1 \
= & 1 / (1 – 1 / 4) – 1 \
= & 1 / 3 \
\end{align}
$$

给定一个函数，它完全随机地产生[1,3]范围内的整数（即每个数的产生机率都是1/3）。用给定的函数去求一个完全随机产生[1,89]范围内的整数函数。注意，要求每个数的出现的概率都相同。

已知一个函数random()，可以返回1到n是随机值，设法利用它他构造一个random2()，使得random2()可以返回1到m的随机值。使用笛卡尔积，构造$(n\times n)$个随机元素，所以这些元素产生的概率都是1/$(n\times n)$。

当 m<=$(n\times n)$时，只需要略去($(n\times n)$ % m)个元素，其余的元素总个数可以整除m，就构造了符合要求的random2()了；

当 m > $(n\times n)$ 时，可以考虑$(n\times n \times n)$来构造元素，然后略去($(n\times n\times n)$ % m)个元素，其余的元素总个数就可以整除m，那就构造了random2()了。

例如，假设n=2，笛卡尔积就是 (1, 1)、(1, 2)、(2, 1)、(2, 2)，就得到$(2\times 2)$个元素，并且出现这$(2\times 2)$个元素出现的概率是相等的，都是1/4 。

假设此时m=3， $(2\times2)$ 不能整除3，所以随便略去((2*2) % 3) (也就是 1 个) 个元素即可构造一个random2()函数。

依此类推…
随机数的生成算法，比如0~~0.6的生成概率是0.7,0.6~~1的生成概率是0.3，问怎么实现。 https://www.nowcoder.com/discuss/13322 https://www.nowcoder.com/discuss/36424

随机的生成0-1的数，设这个数为x。

当0<x<0.7时，输出 $\frac{6x}{7}$

当0.7<x<1时，输出 $\frac{4x-1}{3}$
网游中有个抽奖活动，抽中各星座的概率为10/200，20/200，。。。120/200.如何实现？ https://www.nowcoder.com/discuss/1658
给一个概率分布均匀的随机数发生器，给一串float型的数，希望通过这个随机数发生器实现对这串数进行随机采样，要求是如果其中的某个数值越大，那么它被采样到的概率也越大 https://www.nowcoder.com/discuss/80837

随机数生成算法，一个float数组相同元素的和除以整个数组的和做为抽取该元素的概率，实现按这种概率随机抽取数组中的元素的算法。 https://www.nowcoder.com/discuss/13857

一本无数个字的书从前往后读，某个时间点突然暂停并返回之前读过的某个字，要求每个字返回的概率是一样的。 https://www.nowcoder.com/discuss/80218

一个有n*n个方格的棋盘，在里面放m个地雷，如何放保证在每个方格上放雷的概率相等。 https://www.nowcoder.com/discuss/47399
一根棍子折三段能组成三角形的概率

设折成的三段长分别为x,y和L-x-y,
根据三角形中任意两边的和大于第三边的性质，可得
x+y > L-x-y①
x+(L-x-y) > y②
y+(L-x-y)> x③
x>0,y>0④
0<x+y<L⑤
题目所示的概率就是在④⑤围成的三角形区域S中由①②③围成的三角形区域所占的概率
由：s=Ll/2=L^2/2， S’=(L/2)(L/2)/2=L^2/8，得所求的概率为p=S’/S=1/4.

一个圆上三个点形成钝角的概率是多少？假如两个点和圆心形成的圆心角已经是直角，那么第三个和这两个点形成钝角的概率是多少？ https://www.nowcoder.com/discuss/91505
1. 3/4
2. 3/4
X，Y独立均服从（0,1）上的均匀分布，P{X^2+Y^2≤1}等于

一个圆，在圆上随机取3个点，这3个点组成锐角三角形的概率。
一个袋子里有100个黑球和100个白球，每次随机拿出两个球丢掉，如果丢掉的是不同颜色的球，则从其他地方补充一个黑球到袋子里，如果颜色相同，则补充一个白球到袋子里。问：最后一个球是黑球和白球的概率分别为多大？

抽到黑白：-> 取一个白球

抽到白黑：-> 取一个白球

抽到黑黑：-> 取两个黑球，放一个白球

抽到白白：-> 去一个白球

意味着每次取黑球的时候都是偶数个的取，那么当取到最后是两个黑球的时候，会放进来一个白球，所以最后肯定还剩一个白球。
扔骰子，最多扔两次，第一次扔完可以自行决定要不要扔第二次，取最后一次扔色子的结果为准，求：尽可能得到最大点数的数学期望 https://www.nowcoder.com/discuss/74234

对一扔一次骰子，他的期望是$\frac{1}{6} (1 + 2 ,\cdots, + 6) = 3.5$ ，那么此时的扔骰子的策略为，当我扔到1-3时，继续抛，当我扔到4-6时，停止。在选择继续抛的时候，之前的结果作废，此时相当于抛一次骰子。他的期望为3.5。当只投一次的时候，只会在[4, 5, 6]之间，他的期望是5，所以最终的期望是，（5+3.5）/2 = 4.25

两人轮流扔硬币，扔出正面获胜，求：先扔者获胜的概率 https://www.nowcoder.com/discuss/74234

设第一个人赢的概率为$p(A)$, 第二个人赢的概率为$p(B)$,

$p(A) = \frac{1}{2} + \frac{1}{2} ^ 3 + \frac{1}{2} ^ 5 + \cdots + \frac{1}{2} ^ {2n+1} = \frac{2(1-\frac{1}{4} ^ {n})}{3} $

$p(B) = \frac{1}{2} ^2 + \frac{1}{2} ^ 4 + \frac{1}{2} ^ 6 + \cdots + \frac{1}{2} ^ {2n} = \frac{1-(\frac{1}{4} ^ {n})}{3}$

$\frac{2}{3}, \frac{1}{3}$

a b c 分别循环投掷硬币，直到正面出现胜利，求a b c获胜的概率 https://www.nowcoder.com/discuss/52700

$\frac{4}{7}, \frac{2}{7}, \frac{1}{7}$

硬币正反概率是1/2,一直抛硬币,直到连续两次正面停止，问期望次数。

设期望为E，

当开局抛到两次正面时，$0.5\times0.5\times2$

当开局抛到了反面时，需要重新抛，此时的期望分量时：$0.5\times (E+1)$

当开局抛到了正面，但是紧接着抛到了反面，此时有需要重新抛，期望分量为：$0.5\times0.5\times(E+2)$

所以有：
$$
E = 0.5 \times 0.5 \times 2 + 0.5 \times(E + 1) + 0.5\times 0.5 \times(E+2)
$$
求解E=6

某大公司有这么一个规定：只要有一个员工过生日，当天所有员工全部放假一天。但在其余时候，所有员工都没有假期，必须正常上班。这个公司需要雇用多少员工，才能让公司一年内所有员工的总工作时间期望值最大？

一个人，对于任意一天，过生日的概率是 1 / 365, 不过生日的概率是 364 / 365
n个人，对于任意一天，没任何人过生日的概率是(364 / 365)^n
n个人，对于任意一天，有人过生日的概率是 1 - (364 / 365)^n
那么365天里有人过生日的期望天数是 365（1 - (364 / 365)^n）天，
则n个人，365天，每个人工作的期望天数是365 - 365（1 - (364 / 365)^n）= 365(364 / 365)^n
从而所有人的期望工作天数的和为：365n(364 / 365)^n，求导数，导数不小于0，递增。
所以是365
不存储数据流的前提下,从输入流中获得这 n 个等概率的随机数据。
开辟一个长度为n的数组，对与数据流的第i个数据，以$\frac{n}{i}$的概率将其留下。（i>n）
设数据流中已经流过了m个数据，一共有n个数据被留下来了，每个数据流下来的概率为n/m
- 那么在i=n+1时，n中的数据被留下来的概率为：
$$
\frac{n}{m} [(1-(\frac{n}{m+1})) + (\frac{n}{m+1}*\frac{n-1}{n})]
= \frac{n}{m}\frac{m}{m+1} = \frac{n}{m+1}
$$
- 第i个被选中留下的概率为：$\frac{n}{m+1}$
某段公路上1小时有车通过的概率是0.96，半小时有车通过的概率是多少

反过来想，设半个小时有车经过的概率是p，那么一个小时内没有车经过的概率为$(1-p)^2$,那么一个小时内有车经过的概率为$1-(1-p)^2 = 0.96$， p=0.8
一个公交站在1分钟内有车经过概率是p，问3分钟内有车经过概率

$1-(1-p)^3$
6位数字的8位数码管显示的数字，倒过来看和以前相同的概率是多少。 https://www.nowcoder.com/discuss/89390 https://www.nowcoder.com/discuss/19487

$\frac{6^4}{6^8}$
8支球队循环赛，前四名晋级。求晋级可能性

![image-20190807172622469](/Users/xiongz/Library/Application Support/typora-user-images/image-20190807172622469.png)
一个活动，女生们手里都拿着长短不一的玫瑰花，无序地排成一排，一个男生从队头走到队尾，试图拿到尽可能长的玫瑰花，规则是:一旦他拿了一朵，后面就不能再拿了，如果错过了某朵花，就不能再回头，问最好的策略是什么? https://www.nowcoder.com/discuss/75715

参考答案: https://www.guokr.com/article/6768/

三个范围在0-1的数，和也在0-1的概率

画个图就出来了

1/4
100张牌，每次只能抽一张，抽过的牌会丢掉，怎么选出最大的牌
36匹马，6条跑道，选出最快3匹，最少赛多少场？
先进行6场比赛，选出最快的6匹马

这6匹马，再比赛一次，得到排序排序：
1
2
3
4
5
6
7
A1 A2 A3 A4 ... A6

B1 B2 B3 B4 ... B6

C1 C2 C3 C4 ... C6

...
第一名肯定是A1，第二名可能是A2，B1，第三名可能是A2， A3，B1， B2， C1

所以吧A2， A3， B1，B2， C1再进行一次比赛即可。

总共6+1+1场
5个海盗抢到了100颗宝石，每一颗都一样的大小和价值连城。他们决定：抽签决定自己的号码（1，2，3，4，5）。首先，由1号提出分配方案（你抽到1号），然后大家5人进行表决，当且仅当超过半数的人同意时，按照他的提案进行分配，否则将被扔入大海喂鲨鱼。如果1号死后，再由2号提出分配方案，依此类推。条件：每颗宝石都是一样的价值。海盗都想保命，尽量多得宝石，尽量多杀人。问题：你会提出怎样的分配方案才能够使自己的收益最大化？
1. D来分配，一定不会得到E的同意，因为只要E不同意，同意的票数就不会超过50%，然后D喂鲨鱼，E独享100颗，所以D一定不希望自己来分。D分配意味着喂鲨鱼的结局。
2. C来分配，D一定会同意，所以不用分给D和E。因为D如果不同意，E一定不同意，C被喂给鲨鱼，这样又出现第一种情况了。保命要紧，D宁可不要钻石了。故C分配时可以得到全部100颗。
3. B来分配，C不会同意，因为把B喂鲨鱼后回到第二种情况C会独占，所以B必须得到D、E的同意，只要分给D一个，E一个，D和E就会同意，若D和E不同意，则由C分配时一个也得不到。所以B分配时可以得到98颗，D得到一颗，E得到一颗，C0颗。
4. A来进行分配，B一定不会同意，因为不可能给B98颗以上，所以要得到C、D或者C、E的同意，可以给C一个，D两个，让C、E同意；也可以给C一个E两个,来让C、E同意
故最终A的分配结果是
A97 C1 D2
或 A97 C1 E2
一个人要过一座80米的桥，每走一米需要吃一颗豆子，他最多可以装60颗豆子，问最少需要吃多少颗豆子才能走完桥？证明一下为什么你给的答案是最少的？桥长81米呢？当桥长n米，最多装m颗的时候结果用公式怎么表示？

先拿60颗，走到20米处，放下20颗，返回。

再拿60颗，走到20米处，消耗20颗，取之前放下的20颗，总共60颗，过桥。

一共消耗80+40 = 120颗
一个绳子烧完需要1个小时，假设所有绳子的材质都不一样，也不均匀，怎么取出1小时加 15分钟。

把一根两端点燃，同时把另一根的一端点燃。这样，第一根烧完的时候是过了半个小时。

半个小时后，把第二根的另一端点燃，这样在第二根烧完的时候，就是15分钟了。
把1~9这9个数填入九格宫里,使每一横、竖、斜相等。
有100个黑球，100个白球。两个桶，桶的容量无限，每个球都可以任意放在任何一个桶中，没有限制，请设计一种分配方法，使得白黑球分配到两个桶之后, 某个人从某个桶中取出的球是白球的概率最大化。（这个人去第一个桶取球的概率是1/2,第二个桶也是1/2）

第一个放一个白球，剩下的都放在另一个箱子
有1亿个货物，不能单个单个检测，只能通过两两对比来找出其中的次品，请设计一个算法来找出次品。
有3盏灯，房间外有3个开关，你只有1次机会进入房间，怎么判断哪个开关对应哪盏灯？
给你一堆螺母和螺栓，每个螺母都有一个相对应的螺栓，但是他们之间的对应关系已经打乱。你可以比较螺母和螺栓的大小关系，但是你无法比较螺母和螺母的大小关系，你也无法比较螺栓和螺栓的大小关系。设计一个算法，找出螺母和螺栓的对应关系。

大数据

100亿数字，怎么统计前100大的？

10亿个url，每个url大小小于56B，要求去重，内存4G。

1KW句子算相似度（还是那套分块+hash/建索引，但是因为本人不是做这个的，文本处理根本说一片空白，所以就不误导大家了），之后就是一直围绕大数据的题目不断深化。

Q1：给定一个1T的单词文件，文件中每一行为一个单词，单词无序且有重复，当前有5台计算机。请问如何统计词频？

通过对文件进行划分，将分解切分成小文件，每个计算机单独进行处理。

Q2：每台计算机需要计算200G左右的文件，内存无法存放200G内容，那么如何统计这些文件的词频？

维护一个dic，用于保存词-cnt，分段对文件进行处理，然后并归这些dic

Q3：如何将1T的文件均匀地分配给5台机器，且每台机器统计完词频生成的文件只需要拼接起来即可（即每台机器统计的单词不出现在其他机器中）

划分文件的时候，用哈希函数，将文件进行划分，这样以来，同一个词肯定会被映射到同一个文件。

一个大文件A和一个小文件B，里面存的是单词，要求出在文件B中但不在文件A中的单词。然后大文件A是无法直接存到内存中的。

Booming Filter. 使用若干个哈希函数，对大文件中的每一个单词进行映射，映射得到的位数指1. 对小文件中的每一个单词，用同样的哈希函数进行映射。如果有一个函数映射得到的位为就说明它不在这个大文件中。

扔硬币，连续出现两次正面即结束，问扔的次数期望

E = 0.5*0.5 + 0.5(E+1) + 0.5 * 0.5 * (E + 2)

E = 6

有100W个集合，每个集合中的word是同义词，同义词具有传递性，比如集合1中有word a, 集合2中也有word a, 则集合1，2中所有词都是同义词，对这100W个集合进行归并，同义词都在一个集合当中。

Union Find

对每一个集合中的每一对word，组成一个pair。<word1, word2>

def find(p, id):
    t = p
    while p != id[p]:
        p = id[p]
    while p != t:
        x = id[t]
        id[t] = p
        t = x
    return p

def union(p, q):
    pid = find(p, id)
    qid = find(q, id)
    if sz[pid] < sz[qid]:
        sz[qid] += sz[pid]
        id[pid] = id[qid]
    else:
        sz[pid] += sz[qid]
        id[qid] = id[pid]

if __name__ == '__main__':
    test = [(2, 3), (1, 0), (0, 4), (5, 7), (6, 2)]
    id = [i for i in range(8)]
    sz = [1 for i in range(8)]
    for (p, q) in test:
        union(p, q)
    print(id)

有几个 G 的文本，每行记录了访问 ip 的 log ，如何快速统计 ip 出现次数最高的 10 个 ip，如果只用 linux 指令又该怎么解决？

海量数据的topk问题

计算机基础

Linux下的一些指令，$$（进程id），$?（上一条命令退出时状态），怎么查看进程，按照内存大小，CPU占用排序等等。

Linux的命令：pwd、ln、which

Linux线程通信

hash表是怎么实现的？有冲突的时候怎么处理？

linux 文件词频统计

介绍一下hash，怎么解决冲突。

你说一下hashmap的原理

内存泄露出现原因。

悲观锁乐观锁

把两个表按id合并怎么搞？

数据库transaction

浅拷贝深拷贝

第二题是两题 sql ，涉及 join,group by,max,min,sum,count 等操作的结合，以及同个题目多种写法。

线程安全是什么意思？新线程什么情况下会影响原有线程？

网络基础TCP三次握手

计算机网络：描述他发一句hello world到我这边显示，中间经历了哪些过程，我从应用层开始一层层往下分析答的，主要说http和tcp，网络层和链路层有些忘，但主要的几个协议和子网划分什么的也答了，面试官比较满意

词向量的推导，混合高斯，linux硬链接，三次握手，linux inode

进程线程的区别

概率题

100人坐飞机，第一个乘客在座位中随便选一个坐下，第100人正确坐到自己坐位的概率是？

X是一个以p的概率产生1,1-p的概率产生0的随机变量，利用X产生1/2概率是0,1/2概率是1的随机变量。

X，Y均服存于 [0,1] 的均匀分布，求X+Y。

一个国家重男轻女，只要生了女孩就继续生，直到生出男孩为止，问这个国家的男女比例？

一个有7个格子的环，三种颜色染色，相邻不能颜色重复，问多少种方案

一个袋子里有很多种颜色的球，其中抽红球的概率为1/4，现在有放回地抽10个球，其中7个球为红球的概率是多少？

一枚硬币，扔了一亿次都是正面朝上，再扔一次反面朝上的概率是多少？

一道概率题，54张牌，平均分成三堆，大小王在同一堆的概率？

一道概率题，一个六位的密码，由0~9组成，问你正过来看和倒过来看密码是一样的概率。

一道组合数学题。10盏灯，灭三盏，两头的必须亮着，不能灭掉相邻的两盏灯，问组合数？

有三枚硬币,其中一枚的两面都是正面图像,另一枚的两面都是反面图像,第三枚是正常的，一反一正。现从中随机的抽取一枚硬币进行抛掷，得到正面朝上，问这枚硬币的另一面是反面图像的概率是多大？

个人玩游戏，100个球，每次挑5个，如何保证必胜。

52张牌，四个人抽，黑桃A和红桃A同时在一个人手里的概率。

好像是问有70%的人喜欢玩游戏，30%的人不喜欢玩游戏，现在推送的资源必须是50%游戏，50%非游戏。问怎么分配比较合理。

有n个elements和1个Compare(A, B)函数，用Compare函数作为排序算法中的比较算子给elements排序.Compare函数有p的可能比较错。排序完取Top m个元素，本来就在Top m并被正确分在Top m的元素个数是x。问x的数学期望。

有两个随机数产生器，R1以0.7的概率产生1，以0.3的概率产生0，而R2以0.3的概率产生1，0.7的概率产生0.问如何组合这两种产生器，使新得到的随机数产生器以0.5的概率产生1，0.5的概率产生0。随机数产生器可复用

用R1和R2同时生成两个随机数：
$$
p(1, 1) = 0.7 \times 0.3 \
p(1, 0) = 0.7 \times 0.7 \
p(0, 1) = 0.3 \times 0.3 \
p(0, 0) = 0.3 \times 0.7 \
$$
可以看到同事产生1，1 和同时产生0，0的概率是相等的。所以可以随机的用R1和R2产生数组

如果生成的事[1, 1] 则返回1

如果是生成的[0，0]则返回0

如果生成 [1, 0]或者[0，1]则放弃这次的结果，继续生成。

有两枚硬币A和B，A正面的概率为0.6，B正面的概率为0.5.现在扔了一枚硬币显示为正面，问：该枚硬币是A的概率是多少？

p(p|A) = 0.6
p(p|B) = 0.5

$p(A|p) = \frac{p(A,P)}{p(P)} = \frac{p(P|A)p(A)}{p(P|A)p(A) + p(P|B)p(B)} = \frac{0.6\times0.5}{0.6\times0.5+0.5\times0.5}$

概率题：有种癌症，早期的治愈率为0.8，中期的治愈率为0.5，晚期的治愈率为0.2.若早期没治好就会转为中期，中期没治好就会变成晚期。现在有一个人被诊断为癌症早期，然后被治愈了，问他被误诊为癌症的概率是多少？

给定一个分类器p，它有0.5的概率输出1，0.5的概率输出0。

Q1：如何生成一个分类器使该分类器输出1的概率为0.25，输出0的概率为0.75？

Q2：如何生成一个分类器使该分类器输出1的概率为0.3，输出0的概率为0.7？

问了一个概率题 54张牌，分成6份，每份9张牌，大小王在一起的概率

HR常问问题

为什么不读博、对读博报以什么态度。

为什么选择百度，谷歌百度都给你offer你选哪个。

为什么选择跨专业学计算机？

为什么选择阿里

以后可能要学习很多新技术，你怎么看。

你平时喜欢做什么？看过哪些书？最近在看什么书？

你觉得最有挑战的项目是什么。

你觉得最难忘的事情是什么？

你认为你的优（缺）点是什么。

你还有什么想问的？

加班怎么看。

印象最深刻的事？

压力最大的情况是什么时候。

在面试过程中觉得自己那些当面有进步

场景分析题，有一个任务给你，要求一个月完成，但是以目前的能力一个月完成不了，现在你知道有一个同事擅长这部分工作，但是他有自己的活，帮助你就可能耽误他的进度，问你咋办。

大学令你觉得最不爽的事情是什么

如何学习的？

如何看待加班。

实习期间项目，在组内担任的角色，是否熟悉其他组员的工作。

家庭教育观念？

家里什么情况？独生子女？

将来的职业规划？

工作地点

工作地点的问题

平时有什么兴趣爱好。

我觉得我会先去专心钻研技术，到达一定的

最后问了一下我兴趣爱好

有什么问题问我。

有没其他offer

有没有想过去创业公司

现在在哪里实习？实习主要做些什么？

简单介绍一下自己

聊聊offer情况，有什么考虑之类的。

聊聊实验室生活。

能不能来北京

自己有什么优点缺点？

自己本科生和研究生相比有哪些进步

要求用两个字评价大学生涯。

讲一下你觉得你突出的地方，有亮点的地方。

评价一下你自己的优点缺点？

详细介绍项目。

说下你的优缺点

说说你的经历。

说说你自己的性格。

说说研究生阶段最有成就的事，遇到问题具体怎么解决的。

请你说一下你对应聘该岗位的优势。

遇到的最大挫折是什么。

问你的职业规划，遇到挑战怎么处理，有没有之前和同事发生过较大分歧。

开放题

2016年每个项目有个上线和下线时间段，统计每天在线的项目数量

一堆问题和答案的pair，算它们的相关性

一面现场面，自我介绍加挑一个项目细讲，还有场景题，第一题是QQ添加好友按名称搜索时，怎么区别广告号，诈骗号；

为什么之前没有深度网络出现（数据量不够+机器性能）

为今日头条设计一个热门评论系统，支持实时更新。

从项目中在哪一方面体会最深。

假设一个文档，连续的K个词，认为是一个时间窗口，一个时间窗口的词有关系，如何得到所有的时间窗口。

假设你拥有一切搜索数据，问怎么在不同场景下进行推荐，具体场景忘了（核心点：共线性、语义相似度、主题聚类等等）

假设有100W个单词，如何存储（我答的是trie树，面试官问每个节点会有很多子节点，每个子节点是一个指针，占用8个字节，如何节省空间，我说不知道，面试官提示双数组trie树）

假设要对一场nba球赛进行自动解说，会遇到哪些困难，又该怎么解决呢？

做过哪些项目？项目中遇到哪些难点，你是怎样解决的？

关于集群调度的一些经验 trick 掌握多少；

分词时，为了提高效率，怎么存储词典？（键树）如何压缩存储？

在微信的场景下，如何判断用户的职业？开放问题

场景题如何鉴别淘宝上卖假货的商家，价格维度可以用什么策略等

如何做一个新闻推荐

如何在语料中寻找频繁出现的字串，分析复杂度。

如何用尽可能少的样本训练模型同时又保证模型的性能；

如何预测双十一支付宝的负载峰值。

对推荐算法的未来看法。

平面上有n个点，让你设计一个数据结构，能够返回这个这n个点中距离某特定点最近的一个点。一开始讲了下kd树，然而太复杂面试官不满意，就讲了一个类似GeoHash的方案。

建立一个数据结构，基于此写一段程序用于存储sparse vector，同时编写一个函数实现两个sparse vector的相加运算

很多单词，如何计算单词之间的相似度（或者对单词进行分类）

怎么预测降雨量。

我只有一大批实体词，如何对他们进行聚类（无监督聚类），如何找出这些词中，哪些词之间有关系，是强关系还是弱关系，具体是什么关系，（如刘德华和朱丽倩属于娱乐分类，是强关系，关系为夫妻）

拼车软件是如何定价的以及如何优化。

推荐算法（基于用户的协同过滤，基于内容的协同过滤）

推荐系统的冷启动问题如何解决

文本挖掘中，分词算法？如何选取特征？如何进行相似度计算，文本聚类结果如何评估？

无给定条件，预测蔬菜价格。

有100W个集合，每个集合中有一些词，对于每个集合，找出他是哪些集合的真子集。

有一堆已经分好的词，如何去发现新的词？

比赛相关问题提特征特征选择等

海量的 item 算文本相似度的优化方法；

特征工程经验。

用两分钟介绍自己的项目，创新点在哪里。

用户给三个item（query），如何给出查询网页。

第三题是如何鉴别实施诈骗的QQ用户；

第二题是微信朋友圈内容的安全鉴别；

第四题是如何做反作弊，例如公众号的刷阅读量。

系统设计题，给一个query，如何快速从10亿个query中找出和它最相似的（面试官说可以对每个query找1000个最相似的，存起来，每天离线更新）

线性代数：特征线性依赖，出现冗余，会导致什么问题？

给一堆数据找找到最佳拟合的直线，数据有较多噪声

给你一个系统（面试官好像是无人车部门的），后台的逻辑已经实现了，但是前端加载很慢，怎么检测。

给你两个文件a和b，大小大概100M，两个文件每行一个整数，要求找到两个文件中相同的整数，存到文件c里，问我怎样尽快的完成这项工作？

给出一个算法实现如何确定快递邮件上的地址，要求从国家到省市到县到乡镇的一个识别，要求效率高（有陷阱，比如有的人把县写到市的前面，有人喜欢写地域名称的省略词比如安徽省写成安徽或者皖）。

给定淘宝上同类目同价格范围的两个商品A和B，如何利用淘宝已有的用户、商品数据、搜索数据、评论数据、用户行为数据等所有能拿到的数据进行建模，判断A和B统计平均性价比高低。统计平均性价比的衡量标准是大量曝光，购买者多则高。

给很多单词，统计某个子串出现次数，我给的方法还是用Trie，只不过一个单词要分成多个插入到Trie数中就行了。

给很多单词，要求统计出现某个前缀出现次数。

统计全球会弹钢琴的人数，我用机器学习的思路答的，面试官还比较满意

自己项目中有哪些可以迁移到其他领域的东西。

讲了讲自己在深度学习的认识，问的问题是几个具体场景的设计，包括怎么从海量数据中提取热点问题。

设计 LRU 系统

设计一个合理的电梯调度策略，调度两个电梯，考虑满足基本的接送需求，满足能耗最小，满足用户等待时间最短

设计一个系统可以实时统计任意ip在过去一个小时的访问量；

设计一个结构存取稀疏矩阵（面试官最后告诉我了一个极度压缩的存法，相同行或列存偏差，我当时没听懂，还不懂装懂，最后还是没记住）

设计实现一个git diff

说一下最能代表你技术水平的项目吧？

项目：具体问了特征怎么做的。

（难到我了，我想的方法不好，面试告诉我了他的想法，类似于一个进程调度问题，每一时刻只可能有一个用户按按钮，把这条指令接收，判断当前电梯能否满足，能满足就执行，不能满足则放入一个队列里，实际情况还要细化）

机器学习

Boost算法

CART（回归树用平方误差最小化准则，分类树用基尼指数最小化准则）

GBDT与随机森林比较。

GBDT（利用损失函数的负梯度在当前模型的值作为回归问题提升树算法中的残差的近似值，拟合一个回归树）

KKT条件用哪些，完整描述

KNN（分类与回归）

L1 与 L2 的区别以及如何解决 L1 求导困难。

L1和L2函数。

L1和L2正则相关问题。

L1和L2正则项，它们间的比较

L1正则为什么可以把系数压缩成0，坐标下降法的具体实现细节

LR为什么用sigmoid函数。这个函数有什么优点和缺点？为什么不用其他函数？

LR和SVM有什么区别，libsvm和liblinear有什么区别。

Logistics与随机森林比较

Logistics（推导）

Logistic回归的推导，怎么得到objective function。

SVM与随机森林比较

SVM为什么要引入拉格朗日的优化方法。

SVM原问题和对偶问题关系？

SVM在哪个地方引入的核函数, 如果用高斯核可以升到多少维。

SVM怎么防止过拟合

SVM的目标函数。常用的核函数。

SVM的过程，讲了推导过程，可能表达不清晰，都是泪

bagging、adaboost、boosting

em与kmeans的关系；

k-means的k怎么取等等

k-means算法初始点怎么选择？你的项目里面推荐算法是怎么实现的？

kmeans的原理，优缺点以及改进。

k折交叉验证中k取值多少有什么关系

l2惩罚项是怎么减小Overfitting的？l1，l2等范数的通式是什么？他们之间的区别是什么？在什么场景下用什么范数？l1在0处不可导，怎么处理？

randomforest,GBDT

rf, gbdt, xgboost的区别。

softmax公式

为什么要做数据归一化？

主要问最优化方面的知识，梯度下降法的原理以及各个变种（批量梯度下降，随机梯度下降法，mini 梯度下降法），以及这几个方法会不会有局部最优问题，牛顿法原理和适用场景，有什么缺点，如何改进（拟牛顿法）

什么情况下一定会发生过拟合？

什么是贝叶斯估计

介绍LR、RF、GBDT ，分析它们的优缺点，是否写过它们的分布式代码

介绍SVD、SVD++

会哪些机器学习算法

信息熵公式

假设面试官什么都不懂，详细解释 CNN 的原理；

决策树原理

决策树处理连续值的方法。

决策树如何防止过拟合

决策树过拟合哪些方法，前后剪枝

分类模型可以做回归分析吗？反过来可以吗？

分类模型和回归模型的区别

判别模型，生成模型

各个模型的Loss function，牛顿学习法、SGD如何训练。

在平面内有坐标已知的若干个点P0…Pn，再给出一个点P，找到离P点最近的点。

在模型的训练迭代中，怎么评估效果。

如何减少参数（权值共享、VGG的感受野、GoogLeNet的inception）

如何防止过拟合（增加数据，减少模型复杂度->正则化）

对于同分布的弱分类器，求分类器均值化之后的分布的均值跟方差。

对于机器学习你都学了哪些？讲一个印象深的。

常见分类模型（ svm，决策树，贝叶斯等）的优缺点，适用场景以及如何选型

归一化方式

两种常用的归一化方法：
（1）min-max标准化
（2）Z-score标准化方法
min-max标准化（Min-Max Normalization）（线性函数归一化）
定义：也称为离差标准化，是对原始数据的线性变换，使得结果映射到0-1之间。
本质：把数变为【0,1】之间的小数。
转换函数：（X-Min）/(Max-Min)
如果想要将数据映射到-1,1，则将公式换成：（X-Mean）/(Max-Min)
其中：max为样本数据的最大值，min为样本数据的最小值，Mean表示数据的均值。
缺陷：当有新数据加入时，可导致max和min的变化，需要重新定义。

0均值标准化（Z-score standardization）
定义：这种方法给与原始数据的均值（mean）和标准差（standard deviation）进行数据的标准化。经过处理的数据符合标准正态分布，即均值为0，标准差为1.
本质：把有量纲表达式变成无量纲表达式。
转换函数：（X-Mean）/(Standard deviation) 其中，Mean为所有样本数据的均值。Standard deviation为所有样本数据的标准差。

应用场景

（1）在分类、聚类算法中，需要使用距离来度量相似性的时候、或者使用PCA技术进行降维的时候，第二种方法(Z-score standardization)表现更好。
因为：第一种方法(线性变换后)，其协方差产生了倍数值的缩放，因此这种方式无法消除量纲对方差、协方差的影响，对PCA分析影响巨大；同时，由于量纲的存在，使用不同的量纲、距离的计算结果会不同。
（2）在不涉及距离度量、协方差计算、数据不符合正太分布的时候，可以使用第一种方法或其他归一化方法。比如图像处理中，将RGB图像转换为灰度图像后将其值限定在0 255的范围。
因为：第二种归一化方式中，新的数据由于对方差进行了归一化，这时候每个维度的量纲其实已经等价了，每个维度都服从均值为0、方差1的正态分布，在计算距离的时候，每个维度都是去量纲化的，避免了不同量纲的选取对距离计算产生的巨大影响。

手写k-means的伪代码。

手写k-means的伪代码和代码。（Code）

手撕svm硬软间隔对偶的推导

手撕逻辑回归（损失函数及更新方式推导）

接着写一下信息增益的公式。

推一下bp算法等等

改变随机森林的训练样本数据量，是否会影响到随机森林学习到的模型的复杂度。

数据挖掘各种算法，以及各种场景下的解决方案

是否了解mutual infomation、chi-square、LR前后向、树模型等特征选择方式。

是否了解线性加权、bagging、boosting、cascade等模型融合方式

有哪些常见的分类器，简单介绍下原理

机器学习与深度学习的区别

机器学习基础（线性回归与逻辑回归区别等）

机器学习：几种树模型的原理和对比，朴素贝叶斯分类器原理以及公式，出现估计概率值为 0 怎么处理（拉普拉斯平滑），缺点； k-means 聚类的原理以及缺点及对应的改进；

梯度下降牛顿拟牛顿原理

梯度下降的优缺点。

深度学习和普通机器学习有什么不同？

深度学习有很大部分是CNN，给他用通俗的语言解释下卷积的概念，解释下CNN中的优势及原因

激活函数的选择（sigmoid->ReLu->LReLU->PReLU）

然后20分钟内手写k-means

牛顿法、随机梯度下降算法和直接梯度下降算法的区别？

牛顿法推导

特征选择的方法

由数据引申到数据不平衡怎么处理（10W正例，1W负例，牛客上有原题）

聊聊SVM，这段说了好久，从基本的线性可分到不可分，相关升维，各种核函数，每个是如何实现升。以及出现了XX问题，分析是样本的原因还是其他原因。针对不同情况，采取什么解决方案较好。

自己实现过什么机器学习算法

解释 word2vec 的原理以及哈夫曼树的改进。

解释一下过拟合和欠拟合，有哪些方法防止过拟合。

让我一步一步地构造决策树，怎么计算信息熵、信息增益、然后C4.5 ID3 CART的区别，还说了一下优缺点

详细讨论了样本采样和bagging的问题

说一下Adaboost，权值更新公式。当弱分类器是LR时，每个样本的的权重是w1，w2…,写出最终的决策公式。

说了一下bagging跟boosting。

说明L1L2正则的效果与为什么形成这种情况（L1正则稀疏，L2正则平滑，之后说明就是画图说明正则化）

过拟合的解决方法

数据方面：数据增强，具体体现在在原图上使用patch、反转、小的角度变换

模型方面：使用小的网络结构、添加dropout、添加BN

损失方面：添加正则项，l1、l2正则

逻辑回归估计参数时的目标函数，如果加上一个先验的服从高斯分布的假设，会是什么样。

逻辑回归估计参数时的目标函数

逻辑回归的值表示概率吗？

问了很多数据挖掘的基础知识，包括SVM,逻辑回归、EM、K-means等，然后给我很多场景问我遇到这些情况我要怎么来处理数据，怎么进行建模等等，问得很细

随机梯度下降，标准梯度

随机森林和GBDT的区别？LR的参数怎么求解？有没有最优解？

随机森林（Bagging+CART）

编程题

1~n这n个数现在去掉两个，如何找到去掉的两个数。假设去掉的两个数是a和b，那么通过求和，平方和可以知道a+b和a^2+b^2，然后解方程就行了。

一个字符数组中，每个字符都出现了3次，只有一个出现了2次，如果快速找出这个出现2次的？

def ffff(nums):
    l = []
    for i in range(32):
        mask = 1 << i
        cnt = 0
        for n in nums:
            if mask & n:
                  cnt += 1
        l.append(cnt)
    l = l[::-1]
    ans = 0
    for i in l:
        ans = ans << 1
        t = 1 if i%3 else 0
        ans += t
    return ans

一个数组存着负数与正数，将正数放在前面，负数放在后面

def fff(nums):
    if not nums:
        return
    head = 0
    tail = len(nums) - 1
    p = 0
    while p != tail+1:
        if nums[p] < 0:
            if p == tail:
                p += 1
                continue
            nums[p], nums[tail] = nums[tail], nums[p]
            tail -= 1
        elif nums[p] > 0:
            if p == head:
                p += 1
                continue
            nums[p], nums[head] = nums[head], nums[p]
            head += 1
        else:
            p += 1
    return nums

# 一个运算序列只有+、*、数字，计算运算序列的结果

def cal(s):
 num = 0
 items = s.split('+')
 for i in items:
     if '*' in i:
         t = i.split('*')
         mul = 1
         for j in t:
             mul *= float(j) # 有可能有小数
         num += mul

     else:
         num += float(i)
 return num
``### ##  一维数组，swap 其中的几对数字（每个数字只属于一次 swap 操作），实现查找###

一维有序数组，经过循环位移后，最小的数出现在数列中间，如果原数组严格递增或递减，如何找这个最小数

一维有序数组，经过循环位移后，最小的数出现在数列中间，如果原数组严格递增，如何找这个最小数。

一维有序数组，经过循环位移后，最小的数出现在数列中间，如果原数组非严格递增或递减，如何找这个最小数；

一维有序数组，经过循环位移后，最小的数出现在数列中间，数组可能是递增、递减、递减后递增、递增后递减四种情况，递增递减都是非严格的，如果有转折点，返回转折点的值，否则返回-1；

一道题：给定一个整数数组，里面有两个数相同，其他数都是不同的，如何尽快找到这两个数（答，用hash表，O（N），有更好的方法么？）

一题是多位数用链表存储（ e.g. 123 用 1->2->3 存储），实现相加功能函数 ### ## 不创建临时产量换两个数

a = a ^ b

b = a ^ b

a = a ^ ### ## 两个同样大小有序数组求中位数

def medium(nums1, nums2):
 n = len(nums1) - 1
 left = 0
 right = n
 while left < right:
     i = left + ((right - left + 1) >> 1)
     j = (2 * n + 1)//2 - i
     if i < n and nums2[j - 1] > nums1[i]:
         left = i + 1
     elif i > 0 and nums1[i - 1] > nums2[j]:
         right = i - 1

 if i - 1 == 0:
     leftmax = nums2[j - 1]
 elif j - 1 == 0:
     leftmax = nums1[i - 1]
 else:
     leftmax = max(nums1[i - 1], nums2[j - 1])
 if i == n:
     rightmin = nums2[j]
 elif j == n:
     rightmin = nums1[i]
 else:
     rightmin = min(nums1[i], nums2[j])

 return (leftmax + rightmin) / 2

``

两个大整数相乘

def bigmul(nums1, nums2):
 l1, l2 = list(map(int, list(str(nums1)))), list(map(int, list(str(nums2))))
 ans = [0] * (len(l1)+len(l2)-1)
 for i, n1 in enumerate(l1):
     for j, n2 in enumerate(l2):
         t = n1 * n2
         ans[i+j] += t
 carry = 0
 for i in range(len(ans)-1, -1, -1):
     t = (ans[i]+carry)%10
     carry = (ans[i]+carry)//10
     ans[i] = t
 while carry:
     ans.insert(0, carry%10)
     carry = carry//10
 return ''.join(list(map(str, ans)))### ```

两棵树相加——对应位置两棵树都有值则相加，对应位置只有一棵树有值则取该值

def treeadd(root1, root2):
if not root1:
 return root2
if not root2:
 return root1
root = TreeNode(root1.val + root2.val)
root.left = TreeNode(root1.left, root2.left)
root.right = TreeNode(root1.right, root2.right)
return root### ```

中序遍历二叉树，利用O(1)空间统计遍历的每个节点的层次

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        stack = []
        cur = root
        ans = []
        while stack or cur:
            if cur:
                stack.append(cur)
                cur = cur.left
            else:
                t = stack.pop()
                ans.append(t.val)
                cur = t.right
        return ans

def preorder(root):
stack = []
cur = root
ans = []
while stack or cur:
if cur:
ans.append(cur.val)
stack.append(cur.right)
cur = cur.left
else:
cur = stack.pop()

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def postorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        ans = []
        stack = []
        cur = root
        while stack or cur:
            if cur:
                ans.append(cur.val)
                stack.append(cur.left) # 这里是往右走
                cur = cur.right
            else:
                cur = stack.pop()
        return ans[::-1]

为分析用户行为

系统常需存储用户的一些 query ，但因 query 非常多，故系统不能全存，设系统每天只存 m 个 query ，现设计一个算法，对用户请求的 query 进行随机选择 m 个，请给一个方案，使得每个 query 被抽中的概率相等，并分析之，注意：不到最后一刻，并不知用户的总请求量

在第i个数据来的时候，以m/i的概率将它保留，保留的时候，在m个数据中随机选取一### ，然后加入。

二叉树序列化

# 先序遍历的方式保存
def serilize(root):
 cur = root
 stack = []
 ans = []
 while stack or cur:
     if cur:
         ans.append(cur.val)
         stack.append(cur.right)
         cur = cur.left
     else:
         ans.append("#")
         cur = stack.pop()
 return ans


def deserilize(s):
 stack = []
 ans = None
 for i in s:
     if i == '#':
         while stack[-1] == '#':
             stack.pop()
             stack.pop()
         stack.append('#')
     else:
         t = TreeNode(int(i))
         if not stack:
             ans = t
             stack.append(t)
         elif stack[-1] == '#':
             stack[-2].right = t
             stack.append(t)
         else:
             stack[-1].left = t
             stack.append(t)
 return ans

``

二叉树遍历，描述下层序遍历

import copy
def leveltravel(root):
  stack = [root]
  while stack:
    l = []
    for i in range(len(stack)):
      t = stack.pop()
      print(t.val, end=' ')
      if t.right:
        l.append(t.right)
      if t.left:
        l.append(t.left)
    print('')
    stack = copy.copy(l)

二维数组，每行递增，每列递增，任意交换其中的两### 现并恢复。

二维数组，每行递增，每列递增，实现查找

def find(matrix, target):
 if not matrix or not matrix[0]:
     return None
 row, col = len(matrix), len(matrix[0])
 i, j = row-1, 0
 while i>=0 and j < col:
     if matrix[i][j] == target:
         return i, j
     elif matrix[i][j] < target:
         j += 1
     else:
         i -= 1
 return Non###  ```

二维数组，每行递增，每列递增，求第k大的数

def kthsmallestinrotatedmatrix(matrix, k):
    if not matrix:
        return None

    row, col = len(matrix), len(matrix[0])
    if k > row * col:
        return None

    smallest_idx_in_rows = [0] * len(matrix)
    for _ in range(k):
        min_ = float('inf')
        tag = None
        for i in range(len(matrix)):
            if smallest_idx_in_rows[i] < len(matrix[0]):
                if matrix[i][smallest_idx_in_rows[i]] < min_:
                    min_ = matrix[i][smallest_idx_in_rows[i]]
                    tag = i
        smallest_idx_in_rows[tag] += 1
        ans = min_

    return ans

介绍大顶堆和小顶堆

从一组数中找出和为sum的三个数（leetcode原题，先sort再找，并且剪枝），写代码，四个### 说思路。

允许两个元素交换一次的最大连续子序列和

def maxsequence(nums):
    if not nums:
        return None
    sum_ = 0
    max_ = -float('inf')
    start, end = 0, 0
    for i, n in enumerate(nums):
        sum_ += n
        if sum_ < n:
            sum_ = n
            start = i
        else:
            if sum_ > max_:
                max_= sum_
                end = i
    sub = nums[start: end+1]
    left = nums[:start-1] + nums[end+1:]
    a = min(sub)
    if left:
        b = max(left)
    if a > 0 and b>0:
        if b > 0:
            sub.append(b)
    if a < 0 and  b > a:
        sub.remove(a)
        sub.append(b)

    print(sub)

全排列

冒泡排序

def bubbleSort(nums):
    for i in range(len(nums)):
        for j in range(1, len(nums)-i):
            if nums[j] < nums[j-1]:
                nums[j], nums[j-1] = nums[j-1], nums[j]
    return nums

写一个二叉树的非递归的后续遍历

def postOrder(root):
    stack = []
    ans = []
    cur = root
    while stack or cur:
        if cur:
            ans.append(cur.val)
            stack.append(cur.right)
            cur = cur.left
        else:
            cur = stack.pop()
    ans = ans[::-1]
    return ans

最长公共子序列

子序列是不相连的

def lcs(s1, s2):
    if not s1 or not s2:
        return ""
    n1, n2 = len(s1), len(s2)
    dp = [[0]*(n2+1) for _ in range(n1+1)]
    for i in range(1, n1+1):
        for j in range(1, n2+1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1]+1
            else:
                if dp[i-1][j] > dp[i][j-1]:
                    dp[i][j] = dp[i-1][j]
                else:
                    dp[i][j] = dp[i][j-1]
    ans = []
    i, j = len(dp)-1, len(dp[0])-1
    while dp[i][j]:
        if dp[i][j] == dp[i-1][j]:
            i -= 1
        elif dp[i][j] == dp[i][j-1]:
            j -= 1
        else:
            ans.append(s1[i-1])
            i -= 1
            j -= 1
    for i in dp:
        print(i)
    return ans[::-1]

判断一个字符串是否为另外一个字符串旋转之后的字符串

def isreversed(s1, s2):
    if len(s1) != len(s2):
        return False
    return s1 in s2+s2[::-1]

前k大的数

def kthLargest(nums, k):
    q = []
    if len(nums) < k:
        return None
    for i in nums:
        if len(q) < k:
            q.append(i)
        else:
            if i > min(q):
                q.remove(min(q))
                q.append(i)
    return min(q)

单链表的翻转

def reverselinkedlist(head):
    if not head or not head.next:
        return head
    p = reverselinkedlist(head.next)
    head.next.next, head.next = head, None
    return p

def reverseLinkedList(head):
    if not head or not head.next:
        return head
    pre = head
    p = pre.next
    pre.next = None
    while p:
        q = p.next
        p.next = pre
        pre = p
        p = q
    return pre

去掉连续的重复数字，输出新数组，例如：1，2，2，2，1，3，5——> 3，5

def removeDuplicate(nums):
    nums.sort()
    i, j = 0, 0
    ans = []
    while j < len(nums) and i < len(nums):
        while j < len(nums) and nums[i] == nums[j]:
            j += 1
        if i == j-1:
            ans.append(nums[i])
        i = j
        j = i
    return ans

去除字符串S1中的字符使得最终的字符串S2不包含’ab’和’c’

def remove(s1):
    s1 = list(s1)
    item = {'ab', 'c'}
    stack = []
    for i in s1:
        stack.append(i)
        while stack and stack[-1] == 'c':
            stack.pop()
        while len(stack)>=2 and stack[-1] == 'b' and stack[-2] == 'a':
            stack.pop()
    return ''.join(list(map(str, stack)))

合法括号匹配

def match(s):
    stack = []
    dic = {')': '(', ']': '[', '}': '{' }
    for i in s:
        if i in {'(', '[', '{'}:
            stack.append(i)
        elif i in dic:
            if not stack:
                return False
            if stack.pop() != dic[i]:
                return False
    if stack:
        return False
    return True

在一个字符串中，找出最长的无重复字符的子串

def lnr(s):
    cnt = {}
    start, end = 0, 0
    tag = -float('inf')
    ans = ''
    while end < len(s):
        cnt[s[end]] = cnt.get(s[end], 0) + 1
        end += 1
        if all(i in {0, 1} for i in cnt.values()):
            if end - start > tag:
                tag = end - start
                ans = s[start: end]
        else:
            while not all(i in {0, 1} for i in cnt.values()):
                cnt[s[start]] -= 1
                start += 1
    return ans

在二叉树结点结构中加一个指针域，使其指向层次遍历的下一个结点

class Solution(object):
    def connect(self, root):
        cur = root
        while cur:
            nextlevel = None
            nextcur = None
            while cur:
                if nextlevel == None:
                    if cur.left:
                        nextlevel = cur.left
                    elif cur.right:
                        nextlevel = cur.right
                    p = nextlevel
                    nextcur = nextlevel
                if p and cur.left and p is not cur.left:
                    p.next = cur.left
                    p = p.next
                if p and cur.right and p is not cur.right:
                    p.next = cur.right
                    p = p.next
                cur = cur.next
            cur = nextcur
        return root

堆排序

def heapsort(nums):
    if not nums:
        return nums
    def add(nums, start, end):
        root = start
        while True:
            child = root * 2 + 1 # left child
            if child > end:
                break
            if child + 1 <= end and nums[child + 1] > nums[child]: # right child is biger
                child = child + 1
            if nums[child] > nums[root]:
                nums[root], nums[child] = nums[child], nums[root]
                root = child
            else: # if father larger than both child break
                break

    for i in range((len(nums) // 2) - 1, -1, -1): # adjust from the last father node
        add(nums, i, len(nums) - 1)
    for i in range(len(nums) - 1, -1, -1): # put the largetst number in the last of num 
        nums[0], nums[i] = nums[i], nums[0]
        add(nums, 0, i - 1) # adjust the nums execpt the last numbet
    print(nums)

字符串移位，给出字符串abc##dfg##gh，实现将所有#移至字符串串头。输出####abcdfggh

def move(s):
    ans = list(s)
    end = len(s)-1
    for i in range(len(s)-1, -1, -1):
        if s[i] != '#':
            ans[end] = s[i]
            end -= 1
    for i in range(end, -1, -1):
        ans[i] = '#'
    return ''.join(ans)

定义满足$n=x^a+y^b$（$x，y，a，b$是非负整数）的n是神奇数。如$4 = 2^0 + 3^1,17 = 2^3 + 3^2$。输入l和r，请求出闭区间$[l,r]$里，最长的一段不含有神奇数的连续区间长度。$x,y,l,r<=10^{18},x>=2,y>=2$，如$3\ 5\ 10\ 22$，在$[10,22]$区间内，$x=3,y=5$的条件下，区间内[14]是神奇数，所以最长的区间是$[15,22]$长度为$8$，如$2，3，1，10$，在$[1,10]$区间内，$x=2，y=3$的条件下，$2，3，4，5，7，9$都是神奇数，所以最长的区间只有长度$1$

实现栈，使得添加、删除、max 操作的复杂度为 O(1)

class ms():
    def __init__():
        self.stack = []
        self.max_ = []
    def add(num):
        self.stack.append(num)
		if not self.max_:
            self.max_.append(num)
        elif self.max_[-1] > num:
            self.max_.append(self.max_[-1])
        else:
            self.max_.append(num)
    def pop():
        self.max_.pop()
        return self.stack.pop()
   	def max():
        if not self.max_:
            return None
        return self.max_[-1]

给定一个字符串，按空格翻转每一个单词，但是单词内的字符顺序保持不变

I am a student. -> student. a am I

def r(s):
    def reverse(s, i, j):
        while i < j:
            s[i], s[j] = s[j], s[i]
         	i += 1
            j -= 1
        
    s = list(s)
    s = reverse(s, 0, len(s)-1)
    left = 0
    for right in range(len(s)):
        if s[right] == ' ' or right == len(s):
            reverse(s, start, end-1)
            start = end + 1
            end = end + 1
        else:
            end += 1
    return ''.join(s)

对于一个字符串，请设计一个算法，将字符串的长度为len的前缀平移到字符串的最后

def move(s, k):
    s = list(s)
    if k < 0 or k > len(s):
        return None
    head = s[:k][::-1]
    tail = s[k:][::-1]
    s = head + tail
    return ''.join(s[::-1])

寻找字符串中第一个只出现一次的字符

from collections import Counter
def firstchr(s):
    c = Counter(s)
    for i in s:
        if c[i] == 1:
            return i

将字符串连续重复出现的字符删到只剩一个

def removeduplicate(s):
    ans = []
    start, end = 0, 0
    while end < len(s):
        while s[end] == s[start]:
            end += 1
        ans.append(s[start])
        start = end
        end = end+1
    return ''.join(ans)

常用排序算法的时间和空间复杂度

冒泡排序

插入排序

选择排序

并归排序

快速排序

堆排序

归并排序

def mergsort(nums):
    def merge(left, right):
        ans = []
        i, j = 0, 0
        while i < len(left) and j < len(right):
            if left[i] < right[j]:
                ans.append(left[i])
                i += 1
            else:
                ans.append(right[j])
                j += 1
        while i < len(left):
            ans.append(left[i])
            i += 1
        while j < len(right):
            ans.append(right[j])
            j += 1
        return ans

    if not nums or len(nums)==1:
        return nums
    left = mergsort(nums[:len(nums) // 2])
    right = mergsort(nums[len(nums) // 2:])
    return merge(left, right)

快速排序

def quicksort(nums):
    def swap(nums, i, j):
        nums[i], nums[j] = nums[j], nums[i]

    def partition(nums, i, j):
        start, end = i, j
        swap(nums, start, end)
        pivot = end
        end = end - 1
        i = start
        while i <= end:
            if nums[i] < nums[pivot] and start != i:
                nums[i], nums[start] = nums[start], nums[i]
                i -= 1
                start += 1
            elif nums[i] >= nums[pivot] and i != end:
                nums[i], nums[end] = nums[end], nums[i]
                i -= 1
                end -= 1
            i += 1
        swap(nums, i, pivot)
        return i

    def qs(nums, i, j):
        if i < j:
            pivot = partition(nums, i, j)
            qs(nums, i, pivot-1)
            qs(nums, pivot+1, j)
            return nums


    return qs(nums, 0, len(nums)-1)   手写快排(easy)

打印数组的组合数

def combination(nums):
    import copy
    ans = []
    visited = [False]*len(nums)
    def bfs(ans, t, level, visited):
        if level > len(nums):
            return
        if t not in ans:
            ans.append(copy.copy(t))
        for i in range(level, len(nums)):
            if not visited[i]:
                visited[i] = True
                t.append(nums[i])
                bfs(ans, t, level+1, visited)
                t.pop()
                visited[i] = False
    bfs(ans, [], 0, visited)
    return ans

把一个bst转化成一个双向链表

def trans(root):
    tail = None
    tail = f(root, tail)
    while tail and tail.left:
		tail = tail.left
	return tail

def f(root, tail):
    if not root:
        return None
    if root.left:
   		tail = f(root.left, tail)
        root.left = tail
    if tail:
    	tail.right = root
    tail = root
    if root.right:
		last = f(root.right, tail)
     return last

把一个字符串的大写字母放到字符串的后面，各个字符的相对位置不变，不能申请额外的空间

例如AbcDeFGhi ->bceiADFG

def cmp(a, b):
    if a.islower() and b.isupper():
        return 1
    if a.islower() and b.islower():
        return 0
    if a.isupper() and b.isupper():
        return 0
    else:
        return -1


import functools
def moves(s):
    s = list(s)
    s.sort(key=functools.cmp_to_key(cmp))
    return s

描述Dijkstra最短路径算法

def dijkstra(l, from_, to_):
    dic = {}
    for (u, v, c) in l:
        dic[u] = dic.get(u, {})
        dic[u][v] = c
	import heapq
    l = []
    path = []
    l.append([0, from_, path])
    visited = set()
    while l:
        [cost, t, path] = heapq.heappop(l)
        visited.add(t)
        path += [t]
        if t == to_:
            return path
        else:
            for v, c in dic.get(t, {}).items():
                if v not in visited:
                    heapq.heappush(l, [cost+c, v, path])
                    visited.add(v)
	return float('inf')

插入排序

数列中找第 k 大的数字

数据解压缩，3(a4(ab)) -> aababababaababababaabababab

def unzip(s):
    stack = []
    nums = []
    i = 0
    while i < len(s):

最少时间复杂度求数组中第k大的数

最短路径代码

最长公共子串（动态规划有关）

最长公共子序列

有一堆无向好友列表 1-2， 3-4, 2-3 之类的，问能不能把这些用户划分两组，组内都不互为好友。

有序数组寻找和为某数的一对数字；

正数数组，找三个数使积最小，问有多少种选择。

母鸡、公鸡和小鸡问题：公鸡五块一只，母鸡三块一只，小鸡一块三只，用100元买100只鸡的所有方法。

求double类型的二进制1的个数。

求二叉树最近公共祖先(leetcode原题)

求连续子数组最大乘积，还让考虑边界问题（最后问了：连乘有可能导致溢出，存不下了）

用一个队列，将每个二叉树的root先放入队列。

用数组实现队列，各操作的复杂度分析。

用速度不同的指针可以判断链表中是否有环，问两速度满足怎样的关系可以保证发现环。

直接插入排序写代码

矩阵求最长连续递增的路径长度。

第一题是链表倒数第 k 节点；第二题是二叉树打印路径，第三题是矩阵中将 0 元素所在行列全置 0 的最优空间解法

存在一个数组，大小98，里面的元素均为在[1,100]，且无重复，不申请额外空间的情况下，在时间复杂度为O(N)情况下，找出缺失的两个元素值。

给一个n*n的矩阵，矩阵中满足每行每列都是递增的，要查找矩阵是否存在某个数.(leetcode原题)

给一个数组，只有一个元素出现了一次，其他都出现了两次，找出出现一次的数。

给一个数组，数组种存在一种数，它的左边都比它小，右边都比它大，找出所有这些数的位置。

给一个股票，n天的价格，只能两次买入卖出，而且只能只能先卖再买，问最多赚多少钱？

给一个股票，n天的价格，只能进行一次买入和卖出，问最多赚多少钱？

给一个股票，n天的价格，可以买入卖出k次，而且只能只能先卖再买，问最多赚多少钱？

给一个股票，n天的价格，可以无限次买入卖出，问最多赚多少钱？

给了一个链表，第1个结点标号为1，把链表中标号在M到N区间的部分反转

def f(head, m, n):
  if m > n:
    return -1
  cnt = 1
  dump = Node(-1)
  dump.next = head
  p = head
  pre = dump
  Pre, M, N = None, None, None
  while p.next:
    if cnt == m:
      M = p
      Pre = pre
    if cnt == n:
      N = p
    pre = p
    p = p.next
    cnt += 1
  if not M or not N:
    return -1
  tail = N
  while Pre.next != tail:
    Pre.next = Pre.next.next
    M.next = N.next
    N.next = M
    N = N.next
    M = Pre.next
 return dump.next

给你一个无重复的数组输出全排列

def f(nums):
    if not nums:
        return
    if len(nums) == 1:
        return [nums]
    ans = []
    for i in range(len(nums)):
        for j in f(nums[:i] + nums[i + 1:]):
            if not j:
                continue
            ans.append([nums[i]] + j)
    return ans

给你一颗二叉树按层输出每一层输出后都换行

def travel(root):
	if not root:
    return 
	stack = [root]
  while stack:
    l = len(stack)
    ans = []
    for i in range(l):
      t = stack.pop()
      print(t.val, end=' ')
      ans.append(t)
      if t.right:
        ans.append(t.right)
      if t.left:
        ans.append(t.left)
    stack = copy.copy(ans)
    print("")

给出一颗二叉树，两个叶节点，找到这两个叶节点互连通的一条最短路径

def f(root, p, q， level):
  if not root:
    return -1
  if root == p or root == q:
    return level
  left = f(root.left, p, q, level+1)
  right = f(root.right, p, q, level+1)
  if left == -1:
    return right
  if right == -1:
    return left
  return left+right-2*level

给定一个数组，只有一个元素出现了一次，其他都出现了3次，找出出现一次的数。

def f(nums):
  l = []
	for i in range(32):
    mask = 1 << i
    cnt = 0
    for n in nums:
      if mask & n:
        cnt += 1
    l.append(cnt)
  l = l[::-1]
  ans = 0
  for i in l:
    ans = ans << 1
    t = 1 if i%3 else 0
    ans += t
  return ans

给定一个数组，有两个元素出现了一次，其他都出现了两次，找出两个出现一次的数

def f(nums):
  xor = 0
  for i in nums:
    xor ^= i
  mask = 1
  while mask & xor:
    mask <<= 1
  l, r = [], []
  for i in nums:
    if i ^ mask:
      l.append(i)
    else:
      r.append(i)
  a, b = 0, 0
  for i in l:
    a ^= i
  for i in r:
    b ^= i
  return a, b

给定一个数组，判断是否存在一个片段，使得反转这个片段后能够使该向量升序排列。如：[1, 2, 4, 3]，就可以通过反转[4, 3]使得向量变为[1, 2, 3, 4]

def f(nums):
  n = len(nums)
  i, start, end = 1, 0, 0
  while i < n and nums[i] > nums[i-1]:
    start += 1
    i += 1
    if i == n:
      return False
    end = i
    i += 1
    while i < n and nums[i] < nums[j-1]:
      end += 1
      i += 1
    if i == n:
      if nums[start-1] < nums[end]:
        return True
      else:
        return False
    else:
      while i < n and nums[i] > nums[i-1]:
        i += 1
      if i != n:
        return False
      if nums[start-1] < nums[end] and nums[start] < nums[end+1]:
        return True
			return False

给定二叉树的先序跟后序遍历，能不能将二叉树重建

不能，因为先序：父节点-左节点-右节点，后序：左节点-右节点-父节点，两者的拓扑序列是一样的，所以无法建立）

给定循环递增数组 $a=[7,8,9,1,2,3]$和一个值$k=2$,返回该值得再数组中的下标

def find(A, k):
  if not A:
    return -1
  left, right = 0, len(A)-1
  while left <= right:
    mid = left + ((right-left)>>1)
    if A[mid] == k:
      return mid
    elif A[mid] < A[right]:
      if A[mid] < target <= A[right]:
        left = mid + 1
      else:
        right = mid - 1
    else:
      if A[left] <= target < A[mid]:
        right = mid - 1
      else:
        left = mid + 1
  return -1

给定数组A和一个数T，A中的数可复用，求和为T的A中的数最少的个数

def f(A, T):
  dp = [float('inf')]*(T+1)
  dp[0] = 0
  for i in A:
    for j in range(T+1):
      if j-i >= 0:
        dp[j] = min(dp[j], dp[j-i]+1)
  return dp[-1] if dp[-1] < float('inf') else 0

给定数组，寻找 next big

［1，2，5，10，20，50，100］，可以从里面取若干个数，要求得出和为100的不同取法有多少？

数列中的逆序对

# -*- coding:utf-8 -*-
class Solution:
    def InversePairs(self, nums):
        # write code here
        self.cnt = 0

        def mergeSortCount(nums, left, right, temp):
            if left >= right:
                return 0
            mid = left + ((right - left) >> 1)
            mergeSortCount(nums, left, mid, temp)
            mergeSortCount(nums, mid + 1, right, temp)
            merge(nums, left, mid, mid + 1, right, temp)

        def merge(nums, l_left, l_right, r_left, r_right, temp):
            i = l_left
            j = r_left
            k = l_left
            while i <= l_right and j <= r_right:
                if nums[i] < nums[j]:
                    temp[k] = nums[i]
                    k += 1
                    i += 1
                else:
                    temp[k] = nums[j]
                    k += 1
                    j += 1
                    self.cnt += l_right - i + 1

            while i <= l_right:
                temp[k] = nums[i]
                k += 1
                i += 1
            while j <= r_right:
                temp[k] = nums[j]
                k += 1
                j += 1
            for i in range(l_left, r_right+1):
                nums[i] = temp[i]

        if not nums or len(nums) == 1:
            return 0
        temp = [0] * len(nums)
        mergeSortCount(nums, 0, len(nums) - 1, temp)
        return self.cnt

正整数平方根整数部分

binary search

翻转二叉树（Code）

若干个二叉树，如何按照层序遍历

设 rand （ s ， t ）返回 [s,t] 之间的随机小数，利用该函数在一个半径为 R 的圆内找随机 n 个点，并给出时间复杂度分析。

输入一个大长方形，长宽ab，和一堆小长方形。选择两个小长方形，它能放进大长方形，而这个小长方形面积和最大

输入一个宿舍楼亮灯描述图，计算把所有灯关掉的最短时间，管理员起点在左下角，只能在最左或最右的楼梯往上一层，不可往下一层。每次往上一层花费1分钟，每次往左或往右一间宿舍花费1分钟，关灯不花时间。输入的高<=15，宽<=100。

如图:

0010

0100

从左下角开始，最短花费时间是先往右（关灯），再往左，再上一层，再往右两次（关灯）完成：5

再如：

001000

000010

000010

最短时间是先往右四次（关灯），往右一次，上一层，往左一次（关灯），往右一次，上一层，往左三次（关灯），完成，12

python的动态数组是如何实现的

How are lists implemented?

Python’s lists are really variable-length arrays, not Lisp-style linked lists. The implementation uses a contiguous array of references to other objects, and keeps a pointer to this array and the array’s length in a list head structure.

This makes indexing a list a[i] an operation whose cost is independent of the size of the list or the value of the index.

When items are appended or inserted, the array of references is resized. Some cleverness is applied to improve the performance of appending items repeatedly; when the array must be grown, some extra space is allocated so the next few times don’t require an actual resize.

输入两个正数数组，在两个数组分别选一个数，要求第一个数组选的数的下标小于第二个数组选的数的下标。使得两个数的乘积最大。

def getmax(a, b):
    t = 0
    ans = -float('inf')
    for i, j in enumerate(b):
        ans = max(ans, j*t)
        t = max(t, a[i])
    print(ans)

输出字符串中的所有重复子串，例如：abcab，输出: a, b, ab

连续子数组最大和

def maxSum(nums):
  if not nums:
    return 0
  s = 0
  ans = -float('inf')
	for i in nums:
    if s+i < i:
      s = i
    else:
      s += i
    ans = max(ans, s)
    return ans

选择排序

def selectSort(nums):
   if not nums:
      return nums
    idx = cur
    for cur in range(len(nums)):
      idx = cur
	    for i in range(cur, len(nums)):
        	if nums[i] < nums[idx]:
            idx = i
      nums[cur], nums[idx] = nums[idx], nums[cur]

链表快速排序

def swap(p, q):
    p.val, q.val = q.val, p.val


def partition(head, tail):
    pivot = head
    p = head
    while p != tail:
        if p.val <= tail.val:
            swap(p, pivot)
            pivot = pivot.next
        p = p.next
    swap(pivot, tail)
    return pivot


def qs(head, tail):
    if head == tail or head.next == tail:
        return
    pivot = partition(head, tail)
    qs(head, pivot)
    qs(pivot.next, tail)


def sort(head):
    if not head or not head.next:
        return
    tail = head
    while tail.next:
        tail = tail.next
    qs(head, tail)

长度为N的序列有多少种不同的二叉树形态的中序遍历

1的平方加到100的平方结果

n(n+1)(2n+1)/6

Spark 和mapreduce 的不同

而MapReduce计算模型的架构导致上述两类应用先天缓慢，用户迫切需要一种更快的计算模型，来补充MapReduce的先天不足。Spark的出现就弥补了这些不足，我们来了解一些Spark的优势：

1.每一个作业独立调度，可以把所有的作业做一个图进行调度，各个作业之间相互依赖，在调度过程中一起调度，速度快。

2.所有过程都基于内存，所以通常也将Spark称作是基于内存的迭代式运算框架。

3.spark提供了更丰富的算子，让操作更方便

TCP为啥是三次握手

TCP链接之所以可靠，是因为其链接是面向字节的。

在通信的过程中，协议会给每个字节一个序分配一个序号。三步握手的过程，主要是为了互相确认双方的起始序列号。

如果只进行两次握手，客户端发送链接请求及起始序列号seq = x, 收到服务器端的起始序列号seq = y及对客户端序列号seq= x 的确认。此时，双方就客户端的起始序列号达成了共识。

此时，并没有对服务器的起始序列号达成共识，所以就需要进行第三次握手。对B的起始序列号达成共识，不能保证通信的可靠。

如果进行四次握手，在四次握手的过程中，可以把第二、三步合并，这样可以提高连接的速度与效率。

余弦距离和欧式距离

余弦相似度：$\cos(A, B) = \frac{AB}{||A||_2||B||_2}$

余弦距离： $1-\cos(A, B)$

欧式距离：$\begin{equation}
d=\sqrt{\sum_{i=1}^{N}\left(A_{i}-B_{i}\right)^{2}}
\end{equation}$
$$
\begin{equation}
|A-B|_{2}=\sqrt{2(1-\cos (A, B))}
\end{equation}
$$
总体来说，欧氏距离体现数值上的绝对差异，而余弦距离体现方向上的相对差异。

统计两部剧的用户观看行为，用户A的观看向量为(0,1)，用户B为(1,0)；此时二者的余弦距很大，而欧氏距离很小；我们分析两个用户对于不同视频的偏好，更关注相对差异，显然应当使用余弦距离。

而当我们分析用户活跃度，以登陆次数(单位：次)和平均观看时长(单：分钟)作为特征时，余弦距离会认为(1,10)、(10,100)两个用户距离很近；但显然这两个用户活跃度是有着极大差异的，此时我们更关注数值绝对差异，应当使用欧氏距离。

LBP算子

原始的LBP算子定义为在$3\times3$的窗口内，以窗口中心像素为阈值，将相邻的8个像素的灰度值与其进行比较，若周围像素值大于等于中心像素值，则该像素点的位置被标记为1，否则为0。这样，$3\times3$邻域内的8个点经比较可产生8位二进制数（通常转换为十进制数即LBP码，共256种），即得到该窗口中心像素点的LBP值，并用这个值来反映该区域的纹理信息。需要注意的是，LBP值是按照顺时针方向组成的二进制数。

基本的 LBP算子的最大缺陷在于它只覆盖了一个固定半径范围内的小区域，这显然不能满足不同尺寸和频率纹理的需要。为了适应不同尺度的纹理特征，并达到灰度和旋转不变性的要求，Ojala等对 LBP 算子进行了改进，将 3×3邻域扩展到任意邻域，并用圆形邻域代替了正方形邻域，改进后的 LBP 算子允许在半径为 R 的圆形邻域内有任意多个像素点。从而得到了诸如半径为R的圆形区域内含有P个采样点的LBP算子，称为Extended LBP，也叫Circular LBP。

优点:

一定程度上消除了光照变化的问题

具有旋转不变性

纹理特征维度低，计算速度快

缺点:

当光照变化不均匀时,各像素间的大小关系被破坏,对应的LBP算子也就发生了变化。

通过引入旋转不变的定义,使LBP算子更具鲁棒性。但这也使得LBP算子丢失了方向信息。

原始LBP代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import cv2
import numpy as np

def origin_LBP(img):
 dst = np.zeros(img.shape,dtype=img.dtype)
 h,w=img.shape
 for i in range(1,h-1):
     for j in range(1,w-1):
         center = img[i][j]
         code = 0
          
         code |= (img[i-1][j-1] >= center) << (np.uint8)(7)  
         code |= (img[i-1][j  ] >= center) << (np.uint8)(6)  
         code |= (img[i-1][j+1] >= center) << (np.uint8)(5)  
         code |= (img[i  ][j+1] >= center) << (np.uint8)(4)  
         code |= (img[i+1][j+1] >= center) << (np.uint8)(3)  
         code |= (img[i+1][j  ] >= center) << (np.uint8)(2)  
         code |= (img[i+1][j-1] >= center) << (np.uint8)(1)  
         code |= (img[i  ][j-1] >= center) << (np.uint8)(0)  

         dst[i-1][j-1]= code
 return dst

mobilnetv2和v1

参数量和计算量

如何解决目标检测中的物体尺度大小不一的问题

多尺度的特征融合

FPN SSD

python 复制文件

shutil.copyfile(old_name, new_name)shutil.copyfile(old_name, new_name)

pooling的反向传播

在看卷积神经网络的时候，突然想起来池化是会改变特征图的尺寸的，那反向传播是怎么实现的呢。于是搜了一些博客，感觉上面这个博客写得最清晰直观，就从这个博客里面搬了点东西过来作为笔记。

Pooling 池化操作的反向梯度传播

CNN 网络中另外一个不可导的环节就是 Pooling 池化操作，因为 Pooling 操作使得 feature map 的尺寸变化，假如做 2×2 的池化，假设那么第 l+1 层的 feature map 有 16 个梯度，那么第 l 层就会有 64 个梯度，这使得梯度无法对位的进行传播下去。其实解决这个问题的思想也很简单，就是把 1 个像素的梯度传递给 4 个像素，但是需要保证传递的 loss（或者梯度）总和不变。根据这条原则，mean pooling 和 max pooling 的反向传播也是不同的。

1、mean pooling

mean pooling 的前向传播就是把一个 patch 中的值求取平均来做 pooling，那么反向传播的过程也就是把某个元素的梯度等分为 n 份分配给前一层，这样就保证池化前后的梯度（残差）之和保持不变，还是比较理解的，图示如下：

mean pooling 比较容易让人理解错的地方就是会简单的认为直接把梯度复制 N 遍之后直接反向传播回去，但是这样会造成 loss 之和变为原来的 N 倍，网络是会产生梯度爆炸的。

2、max pooling

max pooling 也要满足梯度之和不变的原则，max pooling 的前向传播是把 patch 中最大的值传递给后一层，而其他像素的值直接被舍弃掉。那么反向传播也就是把梯度直接传给前一层某一个像素，而其他像素不接受梯度，也就是为 0。所以 max pooling 操作和 mean pooling 操作不同点在于需要记录下池化操作时到底哪个像素的值是最大，也就是 max id，这个变量就是记录最大值所在位置的，因为在反向传播中要用到，那么假设前向传播和反向传播的过程就如下图所示：

网格最短距离

给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

示例:

输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。

def minPath(matrix):
  if not matrix or not matrix[0]:
    return 0
  dp = [[0]*len(matrix[0]) for i in range(len(matrix))]
  for i in range(len(dp)):
    for j in range(len(dp[0])):
      if i == j == 0:
        dp[i][j] = matrix[0][0]
      elif i == 0:
        dp[i][j] = matrix[i][j-1] + matrix[i][j]
      elif j == 0:
        dp[i][j] = matrix[i-1][j] + matrix[i][j]
      else:
        dp[i][j] = min(matrix[i-1][j], matrix[i][j-1]) + matrix[i][j]
  return dp[len(matrix)-1][len(matrix[0])-1]

numpy实现CNN

给一组数字添加正负号使他们的和为0

https://leetcode.com/problems/target-sum/

class Solution:
    def findTargetSumWays(self, nums: List[int], S: int) -> int:
        self.ans = 0
        self.helper(nums, 0, 0, S)
        return self.ans
    
    def helper(self, nums, total, start, S):
        if start == len(nums) and total == S:
            self.ans += 1
        elif start < len(nums):
            self.helper(nums, total+nums[start], start+1, S)
            self.helper(nums, total-nums[start], start+1, S)™2

class Solution(object):
    def findTargetSumWays(self, nums, S):
        """
        :type nums: List[int]
        :type S: int
        :rtype: int
        """
        if not nums or sum(nums) < S or (sum(nums)+S) % 2 == 1:
            return 0
        target = (sum(nums)+S)//2
        dp = [0]*(target+1)
        dp[0] = 1
        for n in nums:
            for i in range(target, n-1, -1):
                dp[i] = dp[i] + dp[i-n]
        return dp[-1]

GAN的损失函数

BN的数学形式

主流的网络

python实现判断回文（找最优做法）

a == a[::-1]

python扩展维度

导数和偏导的区别

导数和偏导没有本质区别,都是当自变量的变化量趋于0时，函数值的变化量与自变量变化量比值的极限。

一元函数，一个y对应一个x，导数只有一个

二元函数，一个z对应一个x和一个y，那就有两个导数了，一个是z对x的导数，一个是z对y的导数,称之为偏导。

一、导数第一定义

设函数 $y = f(x)$ 在点 $x_0$ 的某个邻域内有定义当自变量$x$在$ x_0$ 处有增量$\Delta x$ ($ x0 + △x$ 也在该邻域内 ) 时相应地函数取得增量 $△y = f(x0 + △x) - f(x0)$ 如果 $△y 与 △x 之比当 △x→0 时极限存在则称函数 y = f(x) 在点 x0 处可导并称这个极限值为函数 y = f(x) 在点 x0 处的导数记为 f’(x0) ,即导数第一定义

二、导数第二定义

设函数 y = f(x) 在点 x0 的某个邻域内有定义当自变量x 在 x0 处有变化 △x ( x - x0 也在该邻域内 ) 时相应地函数变化 △y = f(x) - f(x0) 如果 △y 与 △x 之比当 △x→0 时极限存在则称函数 y = f(x) 在点 x0 处可导并称这个极限值为函数 y = f(x) 在点 x0 处的导数记为 f’(x0) ,即导数第二定义

pytorch定义标量，向量，矩阵以及张量

激活函数的作用

防止过拟合

如何处理大小不同的图片输入（全卷积网络）

常用的损失函数

常见的GAN

如何检测小物体等

python深拷贝和浅拷贝的区别

pytorch实现CNN

pytorch中类的构造

Pytorch 显存控制

降低计算的精度，比如float32 变为float16。这个是一个大杀器，基本上有减少内存尤其是显存消耗的模型，都可以这么做，我个人的经验是在CNN图像处理领域，这么做不会带来显著的模型质量的下降。

分清楚eval 和 requires_grad = False。

对于不需要bp的forward，如validation 请使用 torch.no_grad , 注意model.eval() 不等于 torch.no_grad()

使用torch.cuda.empty_cache()

在确定的地方释放显存

linux中找到正在运行的某个进程，查看显存，杀死进程等

查看进程：ps

查看现存：nvidia-smi

杀死进程：kill

旷视数学题：x，y服从0-1之间的均匀分布，求z=max(x,y)的数学期望

 字节跳动一面只有代码题：将数组分成m段求各段和的最大值最小是多少（动态规划或者二分）

假设数组分为一段，此时的最大值为t = sum(nums)，得到新的t，此时，按个个分组和小于t进行划分，看一共能够分多少个组，如果分的组数小于m，则说明肯定可以。

一张图片多个类别怎么设计损失函数，多标签分类问题

\5. SVM、决策树优缺点，非线性回归用什么方法，L1、L2 正则化区别

\6. 链表归并快排 LeetCode 148——排序链表

\7. 反转链表 LeetCode 206——反转链表

骰子掷出 1-7 的均匀分布

第一次掷骰子的点数为 $X1 X_1 X1$，第二次掷骰子的点数为 X2X_2X2，如果X1=X2=6X_1=X_2=6X1=X2=6，则重掷，令
$$
X=((X1−1)∗6+X2)X =((X_1-1)*6 + X_2) % 7X=((X1−1)∗6+X2)
$$

，则 XXX 即为取值范围为 1-7 的均匀分布

ResNet 的特点

引入跳跃连接，有效地解决了网络过深时候梯度消失的问题，使得设计更深层次的网络变得可行。

用 BN 没有，BN 有啥优点，这里问各种细节

详见论文阅读笔记 Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift

怎么求一个三角形外接圆，

三条边垂直平分线的交点即为圆心，圆心到顶点的距离为半径

什么是 one-shot、zero-shot，区别

zero-shot 就是说测试集中的类别都是训练集中没有见到的；

one-shot 就是说测试集中的类别在训练集中很少或者只能见到一次

梯度下降法和牛顿法区别

梯度下降法：利用一阶导数
牛顿法：利用二阶导数，收敛速度快；但对目标函数有严格要求，必须有连续的一、二阶偏导数，计算量大

Adam 和 SGD 区别，RMSProp 优化算法

RNN 怎么反向传播`
SVM 的损失函数，特点，对偶问题求解，用朗格朗日乘子法将有约束优化转化为无约束优化，直观解释一下拉格朗日乘子法

给定一个 [0, 1] 的均匀分布，求圆周率

用这个分布产生一个坐标 (x,y)(x, y)(x,y)，则这些点均匀分布在一个边长为 1 的正方形内，如下图所示。由几何概率可知，落在四分之一圆内的概率为 P=π4P = \frac{\pi}{4}P=4π，因此我们只需统计出所有点里面落在圆内的点数即可估计出圆周率。

\12. 编程求数组中的 Top K 大的数 LeetCode 215——数组中的第 K 个最大元素

1、目标检测项目

阀值是怎么选取的？取多少？答：０.75
阀值的实际意义是什么？答：IOU 值，然后仔细解释
如果预测出的框过多了怎么办？答：调整 IOU 阀值，然后解释
FPN 在网络中是怎么加的
ResNet-50 的选用，因为背景比较单一，没有必要选取更深的网络

２、常规深度学习问题

BN 和 L2 正则化
哪些原因会导致梯度消失。答：网络深度、激活函数

３、编程题：

判断两个链表是否相交。
求一个数列中两个元素的最大和，找到这个两个元素。（Top K 问题）

二面

为什么项目中用 Faster R-CNN+FPN，Faster 和 YOLO 对比；为什么叫单步法，两步法？
R-CNN系列：R-CNN，Fast R-CNN，Fast R-CNN。大概说了一下每代改进。又问了RPN网络。
C++，问了 map 等是用什么实现的。答：红黑树。（面试官：好了，我也不问你红黑树了），那你在想想还有其他实现的方法吗？平衡二叉树，差不多说了一下。可能是跳表？数据结构和算法之——跳表
STL 中 vector 是怎么实现的？我答了用数组实现，然后常数时间访问，内存分配。内存不够在原有基础上扩大一倍分配。又问内存减小的时候是怎么做的，我懵逼了。
问堆和栈。我不太会堆，忘记了。然后说了说栈的特点，怎么用的。又问了一下，在计算机系统中，栈有哪些用处，具体解释了一下。我说了线程和进程。堆和堆排序、堆的应用、数据结构之——栈
Linux的一些常用命令：我说了几个。他又问怎么按时间顺序打印出文件列表，按文件大小打印文件列表
编程：两个字符串序列的最长公共子序列。动态规划经典题目
开放问题：让我设计神经网络模型（由于硬件限制，Faster 这种网络不让用）
数据：许多图片，这些图片是由很多网络分割的，就像棋盘一样。每一个格子中可能存在一条小斜线（因为是直线，所以实际由两个端点就可以确定）。要求设计一个网络来检测出这张图片中的这些小短线。
要求：自己定义图片的尺寸，网络的模型，loss，评价指标。问的比较细，每一步的实现细节，整得我一愣一愣的。
caffe 实现一种新的自定义网络

大数据

计算机基础

概率题

HR常问问题

开放题

机器学习

编程题

一个字符数组中，每个字符都出现了3次，只有一个出现了2次，如果快速找出这个出现2次的？

一个数组存着负数与正数，将正数放在前面，负数放在后面

# 一个运算序列只有+、*、数字，计算运算序列的结果

一维有序数组，经过循环位移后，最小的数出现在数列中间，如果原数组严格递增或递减，如何找这个最小数

``

两个大整数相乘

两棵树相加——对应位置两棵树都有值则相加，对应位置只有一棵树有值则取该值

中序遍历二叉树，利用O(1)空间统计遍历的每个节点的层次

为分析用户行为

二叉树序列化

``

二叉树遍历，描述下层序遍历

二维数组，每行递增，每列递增，实现查找

二维数组，每行递增，每列递增，求第k大的数

允许两个元素交换一次的最大连续子序列和

全排列

冒泡排序

写一个二叉树的非递归的后续遍历

最长公共子序列

判断一个字符串是否为另外一个字符串旋转之后的字符串

前k大的数

单链表的翻转

去掉连续的重复数字，输出新数组，例如：1，2，2，2，1，3，5——> 3，5

去除字符串S1中的字符使得最终的字符串S2不包含’ab’和’c’

合法括号匹配

在一个字符串中，找出最长的无重复字符的子串

在二叉树结点结构中加一个指针域，使其指向层次遍历的下一个结点

堆排序

字符串移位，给出字符串abc##dfg##gh，实现将所有#移至字符串串头。输出####abcdfggh

实现栈，使得 添加、删除、max 操作的复杂度为 O(1)

给定一个字符串，按空格翻转每一个单词，但是单词内的字符顺序保持不变

对于一个字符串，请设计一个算法，将字符串的长度为len的前缀平移到字符串的最后

寻找字符串中第一个只出现一次的字符

将字符串连续重复出现的字符删到只剩一个

常用排序算法的时间和空间复杂度

归并排序

快速排序

打印数组的组合数

把一个bst转化成一个双向链表

把一个字符串的大写字母放到字符串的后面，各个字符的相对位置不变，不能申请额外的空间

描述Dijkstra最短路径算法

插入排序

数列中找第 k 大的数字

数据解压缩，3(a4(ab)) -> aababababaababababaabababab

给了一个链表，第1个结点标号为1，把链表中标号在M到N区间的部分反转

给你一个无重复的数组输出全排列

给你一颗二叉树按层输出每一层输出后都换行

给出一颗二叉树，两个叶节点，找到这两个叶节点互连通的一条最短路径

给定一个数组，只有一个元素出现了一次，其他都出现了3次，找出出现一次的数。

给定一个数组，有两个元素出现了一次，其他都出现了两次，找出两个出现一次的数

给定一个数组，判断是否存在一个片段，使得反转这个片段后能够使该向量升序排列。如：[1, 2, 4, 3]，就可以通过反转[4, 3]使得向量变为[1, 2, 3, 4]

给定二叉树的先序跟后序遍历，能不能将二叉树重建

给定循环递增数组 $a=[7,8,9,1,2,3]$和一个值$k=2$,返回该值得再数组中的下标

给定数组A和一个数T，A中的数可复用，求和为T的A中的数最少的个数

给定数组，寻找 next big

数列中的逆序对

正整数平方根整数部分

python的动态数组是如何实现的

输入两个正数数组，在两个数组分别选一个数，要求第一个数组选的数的下标小于第二个数组选的数的下标。使得两个数的乘积最大。

输出字符串中的所有重复子串，例如：abcab，输出: a, b, ab

连续子数组最大和

选择排序

链表快速排序

长度为N的序列有多少种不同的二叉树形态的中序遍历

1的平方加到100的平方结果

Spark 和mapreduce 的不同

TCP为啥是三次握手

余弦距离和欧式距离

LBP算子

mobilnetv2和v1

参数量和计算量

如何解决目标检测中的物体尺度大小不一的问题

python 复制文件

实现栈，使得添加、删除、max 操作的复杂度为 O(1)