Interview：算法岗位面试—BAT公司问题面试之计算机基础(进程与线程的区别)、经典概率问题等集锦

计算机基础问题

1、进程与线程的区别

进程：进程（Process）是计算机中的程序关于某数据集合上的一次运行活动，是系统进行资源分配和调度的基本单位，是操作系统结构的基础。

线程：线程（thread）是操作系统能够进行运算调度的最小单位。它被包含在进程之中，是进程中的实际运作单位。

一、进程与线程五大区别——进程是线程的boss

1、根本区别—进程管资源、线程管执行：进程是操作系统资源分配的基本单位，而线程是任务调度和执行的基本单位。进程是资源分配最小单位；线程是程序执行的最小单位。

2、内存分配—进程拥有独立的地址空间——进程是线程的上司，进程拥有独立办公室：进程有自己独立的地址空间，每启动一个进程，系统都会为其分配地址空间，建立数据表来维护代码段、堆栈段和数据段；线程没有独立的地址空间，它使用相同的地址空间共享数据。

(1)、系统在运行的时候会为每个进程分配不同的内存空间；而对线程而言，除了CPU外，系统不会为线程分配内存（线程所使用的资源来自其所属进程的资源），线程组之间只能共享资源。

(2)、多进程程序更安全，生命力更强，一个进程死掉不会对另一个进程造成影响（源于有独立的地址空间）；多线程程序更不易维护，一个线程死掉，整个进程就死掉了（因为共享地址空间）。

3、资源开销—进程比线程开销大、线程可频繁切换——进程能住希尔顿而线程只能住如家：线程花费小、开销小、效率高，CPU切换一个线程比切换进程花费小；创建一个线程比进程开销小；线程占用的资源要⽐进程少很多。进程对资源保护要求高，开销大，效率相对较低，线程资源保护要求不高，但开销小，效率高，可频繁切换。

4、内部通信—线程通信更方便、进程间通信需IPC——进程住高楼大厦通信需要电话：线程之间通信更方便，但多线程程序处理好同步与互斥是个难点；同一个进程下，线程共享全局变量，静态变量等数据，进程之间的通信需要以通信的方式（IPC）进行。

(1)、进程间通信IPC，线程间可以直接读写进程数据段（如全局变量）来进行通信——需要进程同步和互斥手段的辅助，以保证数据的一致性。

5、资源开销—线程可以看做轻量级的进程——进程减肥后就能瘦成线程：每个进程都有独立的代码和数据空间（程序上下文），程序之间的切换会有较大的开销；线程可以看做轻量级的进程，同一类线程共享代码和数据空间，每个线程都有自己独立的运行栈和程序计数器（PC），线程之间切换的开销小。

(1)、没有线程的进程可以看做是单线程的，如果一个进程内有多个线程，则执行过程不是一条线的，而是多条线（线程）共同完成的；线程是进程的一部分，所以线程也被称为轻权进程或者轻量级进程。

6、 环境运行—线程是进程的一部分、进程可有多个线程——进程位高权重拥有更多选择权：一个线程只能属于一个进程，而一个进程可以有多个线程，但至少有一个线程。在操作系统中能同时运行多个进程（程序）；而在同一个进程（程序）中有多个线程同时执行（通过CPU调度，在每个时间片中只有一个线程执行）。

概率问题

1、貂蝉与西施回头率比美问题

结论1：貂蝉获胜的概率是0.5，但并不是指貂蝉、西施获胜的概率相等，即貂蝉获胜的概率有可能是90%。

结论2：其实P(C)是接近于0即没有用处的

结论3：如果有超过50%概率(比如60%)获胜，那么尽量多进行一场比赛(前边几场随机性比较强，比赛越多，越接近概率60%)

(1)、问题描述以及分析

(2)、代码模拟验证(10万次)实现，得到0.50335

2、从1,2,3,......,98,99,2015这100个数中任意选择若干个数(可能为0个数)求异或，试求异或的期望值。

解：计算每一位的期望。针对任何一个二进制位：取奇数个1异或后会得到1，取偶数个1异或后会得到0；与取0的个数无关。

 给定的最大数2015=(11111011111)2，共11位。针对每一位分别计算，考虑第 i 位Xi，假定给定的100个数中第 i 位一共有N个1，M个0，某次采样取到的1的个数为k。则有

(1)、11位二进制数中，每个位取1的期望都是0.5

(2)、采样模拟