操作系統与计算机结构

  • ThreadPool，Jdk原生线程池，四个参数详细解释原理，当线程池中poolSize达到corePoolSize且阻塞队列已满，再来一个任务，如何处理。

  • 多线程实现同步的方式，互斥同步，非阻塞同步。

  • 程序的编译、链接过程。

  • 死锁的条件是什么？以及如何处理死锁问题？
    条件：互斥条件（Mutual exclusion）：
    1、资源不能被共享，只能由一个进程使用。
    2、请求与保持条件（Hold and wait）：已经得到资源的进程可以再次申请新的资源。
    3、非剥夺条件（No pre-emption）：已经分配的资源不能从相应的进程中被强制地剥夺。
    4、循环等待条件（Circular wait）：系统中若干进程组成环路，该环路中每个进程都在等待相邻进程正占用的资源。
    解决方法：
    1、忽略该问题。例如鸵鸟算法，该算法可以应用在极少发生死锁的的情况下。为什么叫鸵鸟算法呢，因为传说中鸵鸟看到危险就把头埋在地底下，可能鸵鸟觉得看不到危险也就没危险了吧。跟掩耳盗铃有点像。
    2、检测死锁并且恢复。
    3、仔细地对资源进行动态分配，以避免死锁。
    4、通过破除死锁四个必要条件之一，来防止死锁产生。（Synchronize）

  • 请阐述动态链接库与静态链接库的区别。
    静态链接库是 .lib 格式的文件，一般在工程的设置界面加入工程中，程序编译时会把lib文件的代码加入你的程序中因此会增加代码大小，你的程序一运行lib代码强制被装入你程序的运行空间，不能手动移除lib代码。
    动态链接库是程序运行时动态装入内存的模块，格式 .dll ，在程序运行时可以随意加载和移除，节省内存空间。
    在大型的软件项目中一般要实现很多功能，如果把所有单独的功能写成一个个lib文件的话，程序运行的时候要占用很大的内存空间，导致运行缓慢；但是如果将功能写成dll文件，就可以在用到该功能的时候调用功能对应的dll文件，不用这个功能时将dll文件移除内存，这样可以节省内存空间。

  • 请阐述进程与线程的区别。
    从概念上：
    进程：一个程序对一个数据集的动态执行过程，是分配资源的基本单位。
    线程：一个进程内的基本调度单位。线程的划分尺度小于进程，一个进程包含一个或者更多的线程。
    从执行过程中来看：
    进程：拥有独立的内存单元，而多个线程共享内存，从而提高了应用程序的运行效率。
    线程：每一个独立的线程，都有一个程序运行的入口、顺序执行序列、和程序的出口。但是线程不能够独立的执行，必须依存在应用程序中，由应用程序提供多个线程执行控制。
    从逻辑角度来看（重要区别）：
    多线程的意义在于一个应用程序中，有多个执行部分可以同时执行。但是，操作系统并没有将多个线程看做多个独立的应用，来实现进程的调度和管理及资源分配。

  • 用户进程间通信主要哪几种方式？
    主要有以下6种：
    1、管道：管道是单向的、先进先出的、无结构的、固定大小的字节流，它把一个进程的标准输出和另一个进程的标准输入连接在一起。写进程在管道的尾端写入数据，读进程在管道的道端读出数据。数据读出后将从管道中移走，其它读进程都不能再读到这些数据。管道提供了简单的流控制机制。进程试图读空管道时，在有数据写入管道前，进程将一直阻塞。同样地，管道已经满时，进程再试图写管道，在其它进程从管道中移走数据之前，写进程将一直阻塞。
    无名管道：管道是一种半双工的通信方式，数据只能单向流动，而且只能在具有亲缘关系（通常是指父子进程关系）的进程间使用。
    命名管道：命名管道也是半双工的通信方式，在文件系统中作为一个特殊的设备文件而存在，但是它允许无亲缘关系进程间的通信。当共享管道的进程执行完所有的I/O操作以后，命名管道将继续保存在文件系统中以便以后使用。
    2、信号量：信号量是一个计数器，可以用来控制多个进程对共享资源的访问。它常作为一种锁机制，防止某进程正在访问共享资源时，其它进程也访问该资源。因此，主要作为进程间以及同一进程内不同线程之间的同步手段。
    3、消息队列：消息队列是由消息的链表，存放在内核中并由消息队列标识符标识。消息队列克服了信号传递信息少、管道只能承载无格式字节流以及缓冲区大小受限等缺点。
    4、信号：信号是一种比较复杂的通信方式，用于通知接收进程某个事件已经发生。
    5、共享内存：共享内存就是映射一段能被其它进程所访问的内存，这段共享内存由一个进程创建，但多个进程都可以访问。共享内存是最快的IPC方式，它是针对其它进程间通信方式运行效率低而专门设计的。它往往与其它通信机制（如信号量）配合使用，来实现进程间的同步和通信。
    6、套接字：套接字也是一种进程间通信机制，与其它通信机制不同的是，它可用于不同机器间的进程通信。

  • 巨量化数据处理模型Hadoop和Spark的基本原理和区别。

  • Python垃圾回收机制（gc）：引用计数、标记回收、分代回收。

  • MySQL第一、二、三范式要求。（属性原子性；不存在函数依赖；不存在传递依赖）

  • CDN(Content Delivery Network)工作机制。（能够根据实时网络流量和各节点的链接、负载状况以及到用户的距离和响应时间等综合信息，将用户请求重新定向至离用户最近的服务节点上，解决网络拥挤和提高访问响应速度）

计算机网络

Link

  • OSI七层结构和功能。

  • TCP四层结构和功能。

  • 五层协议的基本机构。

  • IP地址的分类，ABC三类以及Internet上保留地址用于内部。

  • IP地址和子网掩码相与得到主机号。

  • ARP地址解析协议工作流程。

  • 基本网络协议。（ICMP、TFTP、HTTP、DHCP、NAT、DHCP）

  • 三次握手和四次挥手。

  • 在浏览器中输入网址后执行的全部过程。（DNS -> IP找server -> 打包报文段 -> 选择和传输路由（ARP） -> 通过协议进行端对端传输）

  • TCP和UDP的区别（传输可靠性和面向连接，传输单位，数据安全性）。

  • 报文段和用户数据报结构。(TCP -> 首 + 数据，固定部分20字节，UDP -> 首 + 数据，固定部分20字节)

  • TCP协议端口。（FTP、Telnet、SMTP、POP3、HTTP）

  • UDP协议端口。（DNS、SNMP、TFTP）

  • DNS域名系统的工作原理。

  • 面向连接和非面向连接服务的特点是什么？

  • TCP三次握手可以改成两次吗？为什么？

  • TCP和UDP的12字节伪首部。
    TCP：源IP地址（4）+目的IP地址（4）+0（1）+6(TCP标识符)(1)+TCP长度(2)
    UDP：源IP地址（4）+目的IP地址（4）+0（1）+17(UDP标识符)(1)+UDP长度（2）

  • 什么是交换器、路由器、网关和主机。

程式语言

  • 解释Synchronize关键字的锁优化技术，偏向锁，轻量级锁，重量级锁，这些锁是如何存储的，偏向锁撤销升级为轻量级锁的过程

  • volatile关键字语义，内存屏障如何实现，JMM对内存屏障做了哪些优化，volatile的语义增强。

  • Integer与int的区别。

  • hashMap为什么会造成死循环。Link

  • C++如何实现动态绑定（Virtual动态绑定，利用基类动态指针和当前静态类型指针指向同一个对象的Virtual函数）。Link

  • C++虚函数，虚函数表，虚指针，内存模型。

  • 指针数组和数组指针的区别。

  • malloc-free和new-delete的区别。Link

  • sizeof和strlen的区别。Link

  • C++中父类构造函数，子类构造函数，父类派生函数，子类派生函数训醒顺序。Link

  • C++ STL里面的vector的实现机制。(Vector的底层实现一般是连续的内存(数组)。deque的实现是连续的内存块，list的是双链表，set和map是红黑树)Link

  • (STL) STL的容器可以分为以下几个大类:
    1、 顺序（序列）容器:有 vector,list,deque , string,stack(适配器类), queue(适配器类), priority queues(适配器类)。
    2、关联容器:有set, multiset,map,multimap, bitset,hash_set, hash_map, hash_multiset, hash_multimap。

  • 怎么防止单例模式被破坏。Link

  • LRU（Least Recently Used）cache 设计数据结构，怎么实现。Link

  • 熟悉基本的设计模式：单例、工厂、观察者、装饰者以及MVC等模式。

  • Java中HashMap和HashTable的不同之处。（包括线程安全性，可否为null以及遍历方式，初始值与扩容方式，hash算法实现等等）

机器学习、算法和自然语言处理

  • SSD（Single Shot MultiBox Detector）的思路和里面的网络结构

  • 讲下LR模型，LR模型为什么采用似然估计损失函数。

  • 说下基本主题的LDA模型。

  • doc2vec中向量怎么产生的。（word2vec + TokenID）

  • 说下频繁序列挖掘prefixspan 算法。（对比Apriori算法的过程和缺点，讲解该算法的优势，只需要扫描一次序列数据集，目标是挖掘出满足最小支持度的频繁序列，长度为1的前缀开始挖掘序列模式，搜索对应的投影数据库的频繁序列，然后递归的挖掘长度为2的前缀所对应的频繁序列。以此类推，一直递归到对应的投影数据库为空或者对应投影数据库中各项的支持度计数小于阈值为止。整个过程就是前缀不断的增长，产生1，2…N 频繁序列，对应的投影数据库不断缩小直至为空。优点：PrefixSpan算法由于不用产生候选序列，且投影数据库缩小的很快，内存消耗比较稳定，作频繁序列模式挖掘的时候效果很高。）

  • 说说RBM编码器，Restricted Boltzmann Machine (RBM)限制波尔兹曼机。Link
    作用：
    1.降维，类似稀疏自动编码器
    2.用RBM训练得到的权重举证和偏移量作为BP神经网路的初始值，避免陷入局部极小值
    3.可以估计联合分布P(v,h)，进而求出P(h|v)。生成式模型
    4.直接计算P(h|v)进行分类。判别式模型

  • (序列标注) 适合序列标注问题的模型：
    1、HMM
    2、CRF
    3、RNN

  • (反向传递) 在电影票房预测工作中，假如使用梯度下降优化均方差损失函数，并且希望模型训练效更偏重于票房较大的电影样本。
    能： 1、在训练数据中直接复制大票房电影的数据。2、修改损失函数，使其偏重大票房电影的误差。3、针对大票房数据，在训练时增加学习步长。(增大Learning rate相当于增大了权重值)
    不能： 增加大票房电影独有的特征，例如访问流量是否大于一定阈值。（不一定对训练有帮助，反而容易干扰学习方向）

  • (降维) 降维算法的实现有：
    1、Latent Dirichlet Allocation(LDA)把文件投影到topic空间，降低了文件有效特征数。
    2、Word2Vec利用word embedding表示词的向量，将传统的dim维度稀疏的向量one-hot vector压缩到n维的向量，n<<dim。
    3、Principal component analysis(PCA)主成分分析，将特征通过在某个维度上的映射来降维。
    4、AutoEncoder神经网络压缩特征向量常用的方法。

  • (过拟合) 防止过拟合的方法：
    1、使用正则化项
    2、扩增训练数据集
    3、决策树模型剪枝
    4、early stop

  • (生成、判别式模型) 判别式(Discriminative model)和生成式(Generative model)模型分类：
    判别式 ： 线性回归、逻辑回归、神经网络、SVM、高斯处理(Gaussian Process)、条件随机场(CRF)、CART
    生成式 ： 朴素贝叶斯、KNN、混合高斯模型、HMM、Sigmoid Belief Networks、马尔科夫随机场、深度信念网络(DBN)

  • (无约束优化) 用来解决无约束优化的算法：（SMO用来解约束优化算法）
    1、随机梯度下降
    2、LBFGS
    3、共轭梯度法
    4、拟牛顿法

  • (二叉树) 一颗高度为4的平衡二叉树，其最少节点数为 : 7
    深度为n的平衡二叉树（Balance binary tree）至少有F（n）个节点，那么F（n）满足：F(n) = F(n-1)+F(n-2)+1

  • (二叉树) 一共三个结点的二叉树可能出现多少种结构 : 5
    节点形态数 = 卡特兰数 = C(2n, n) / (n+1)

  • (哈弗曼编码) 现有一段文本，其中只有A，B，C，D，E包含五个字母，它们出现的次数分别是A出现1次，B出现2次，C出现10次，D出现6次，E出现4次，那么经过哈弗曼编码后，各个字母对应的编码可能是下面哪一组？

  • word2vec、sent2vec（doc2vec）如何得到向量？

  • 词嵌入（Word Embedding）过程中，如何找到相似的字符。

  • 传统机器学习、深度学习考点：Link

  • 常见数据挖掘算法：Link

  • 卡方检定基本功能。（同质性、适合度、独立性分析）

  • 基础算法编程: Link

  • 经典演算法实例：Link

  • 排序算法和比较：Link

其他

其他的问题可以参考牛客网专项练习和公司专题。