Yukinochyan's Blog

操作系统原理（面试向） 一、操作系统概述 1.1 操作系统的用处是什么？有哪些基本作用？ 1.操作系统是用户与计算机硬件之间的接口，提供系统调用和命令等。 2.操作系统是计算机资源的管理者（CPU，内存，文件，磁盘等）。 1.2 并发和并行有什么区别？ 并发指的是宏观上在一段时间内好似有多个程序在运行，但是微观上他们是交替执行的。 并行指的是同一时刻有多道程序在不同的处理器或处理器核心上运行。 1.3 什么是用户态和内核态？为什么要划分呢？ 内核态拥有最高特权，可执行包括特权指令在内的所有指令，并能访问内核允许访问的内存。用户态是普通应用程序运行的状态，对计算机资源受限访问。 之所以要划分内核态和用户态，主要是为了安全，保护系统稳定，这样可以防止恶意程序和bug破坏OS和硬件。 1.4 说说几种不同的操作系统类型？ 简单批处理系统，多道批处理系统。 分时系统（时间片），实时系统。 分布式操作系统，网络操作系统等。 1.5 说说几种不同的操作系统结构？ 分层结构：每层只能调用其下层的服务。其排查错误方便，但是效率低。 微内核结构：尽量减少在...

概率论与数理统计（面试向） 1. 什么是随机变量？ 随机变量是定义在样本空间上的实值函数，它把每个随机试验结果映射为一个数值。随机性来自试验结果的不确定性，而不是说变量的取值“毫无规律”；随机变量的取值规律通常可以由概率分布描述。 2. 什么是联合概率和边缘概率？ 联合概率描述多个事件或多个随机变量取值同时发生的概率。例如，离散随机变量的联合概率可以写为。 边缘概率只关注其中一个随机变量，可以从联合分布中消去其他变量。离散情形下有 连续情形下则对联合概率密度积分： 3. 什么是条件概率？ 若，则在事件已经发生的条件下，事件发生的概率称为条件概率： 4. 什么是贝叶斯公式？它有什么作用和意义？ 贝叶斯公式用于在获得新证据后更新事件发生的概率： 若事件构成样本空间的完备划分，则 例如，令事件表示患病，事件表示检测结果为阳性。是检测前的患病概率，是检测灵敏度，而才是检测呈阳性后真正患病的概率。贝叶斯公式还可用于机器学习、风险预测和故障诊断等领域。 5. 什么是先验概率？什么是后验概率？ 先验概率是在观察当前证据之前，对某个事件或参数的...

数据结构与算法（面试向） 一、基础知识 1.1 时间复杂度和空间复杂度概念是啥？ 时间复杂度描述算法执行时间随输入规模增长的渐近趋势，通常用基本操作的执行次数来估计。根据分析目标，可以讨论最好、平均和最坏时间复杂度；面试中若没有特别说明，通常重点关注最坏时间复杂度。 空间复杂度描述算法所需存储空间随输入规模增长的渐近趋势。分析时需要说明是否只计算辅助空间，例如原地算法通常指除输入数据和递归调用栈外只使用辅助空间。 1.2 数据的四种存储结构是什么？ 顺序存储：把逻辑上相邻的元素存储在物理位置相邻的存储单元中。其存储密度高、局部性好，但需要连续空间，扩容时可能需要整体搬迁，并可能存在预留容量浪费。 链式存储：使用指针表示元素之间的逻辑关系。其不要求连续存储，插入和删除灵活，但需要额外的指针空间，缓存局部性也较差。 索引存储：维护由关键字和地址组成的索引表。其检索速度较快，但会产生额外空间开销，修改数据时还需要维护索引。 哈希存储：根据关键字计算元素的存储地址。理想情况下增删改查的平均时间复杂度为，但冲突严重时最坏可退化为，因此需要合理设计哈希函数、负载因子与...

1. 离散数学中的笛卡尔积的定义是啥？ 设有两个集合 A 与 B，以 A 的元素作为第一个分量，以 B 的元素作为第二个分量， 用这种方式所组成的有序偶的全体构成一个集合，就是A和B的笛卡尔积。 2. 什么是二元关系？ 二元关系是指定义在两个集合上的关系，它是有序对的集合。显然，一个二元关系是两个集合的笛卡尔积的子集。 3. 二元关系会有什么性质？有什么类型的二元关系？ 自反性：对于集合A里的元素都有aRa； 对称性：若有aRb，则有bRa； 反对称性：若有aRb且bRa，则a=b； 传递性：若有aRb，bRc，则有aRc； 如果满足自反，对称，传递，则称这个关系为等价关系。 如果满足自反，反对称，传递，则称这个关系为偏序关系。 若偏序关系两个元素都可比较的，即不是aRb就是bRa，则这个关系是全序关系。 4. 偏序关系和等价关系都刻画了什么东西？ 偏序关系用于比较元素之间的相对顺序。对于集合中的任意两个元素， 可以根据某种规则来判断它们的顺序关系。 等价关系则用于刻画元素之间的相等性。 在一个等价关系上有若干个等价类，与 A 中的一个元...

计算机网络原理 自用面试向 第一章 概述 1.1 三种交换方式： 电路交换：建立连接，通话，释放连接，e.g:电话（计算机使用效率低） 分组交换：发送一个个分组报文到网络之中，从而传输给接收者 报文交换：早期电报通信网使用，不再详细说明 主要使用分组交换。其优点很明显：无需建立连接，线路利用率高，加速传输，减少了重传的数据量…，缺点：转发时延，需要传输额外的头部信息，对于数据报服务存在失序，重复分组等问题；对于虚电路服务，存在建立传输释放等过程。 1.2 计算机网络的性能指标 速率（MB/s）：比特率，表示单位时间内传输多少个二进制位； 带宽（MB/s）：数据的最大传输能力，可以类比为一根水管的粗细； 吞吐量（MB/s）：实际传输的速率； 时延：数据包从源到目的端需要多少时间 总时延发送时延（传输时延）传播时延处理时延排队时延 往返时间RTT：从发送端出发，到达接收端并收到返回信息所需的总时间； 利用率：吞吐量/带宽； 丢包率：发送的数据包中，有多少没有成功到达。 1.3 为什么要使用分层的思想设计计算机网络系统 1.容易定位问题。可以快速知道哪...

复习线性代数必须意识到的一点：线性代数的本质是线性变换。 对于这个式子来说，我们对向量做线性变换，而矩阵是线性变换的规则。 一、一些基础概念 1.1 向量 向量在数学、计算机、物理领域有着不同的含义，而在线性代数领域，我们习惯把它理解为：从原点开始，在不同的方向上做一定程度的运动。 注意从原点开始这一点。如果一个变换使一个向量的起点不是原点，我们就不能认为这个变换是线性变换。经典的案例：平移。 1.2 线性组合、空间 我们不妨换一种看法：在二维空间中举例，每个分量可以看作对该分量上的单位向量进行拉伸，之后对拉伸后的单位向量进行矢量求和。 这个改变很有意思，因为我们把一个向量，视为了一组基向量的线性组合。 所谓线性组合，实际你可以理解为：你手里有一堆向量，对这些向量你每个可以自由伸缩，然后再对他们进行矢量求和。 所谓空间，个向量的所有线性组合就张成了这个向量的空间。 一个例子：二维空间两个不共线的向量张成了一个平面。 1.3 基 想象一个三维空间，你现在手里有两个向量，其张成的空间是一个平面。如果再给你一个向量，这个向量在平面之内，是不是你永远也无法用这三...

Atcoder Beginner Contest 452 A:Gothec 直接按照题目要求判断即可。可以注意到，对于3、5、7、9月都是月份等于日期，所以加几个特判就好。 Code: 12345678910111213#include<bits/stdc++.h>using namespace std;#define int long longint n,m;signed main(){ cin>>n>>m; if(n==1 && m==7) { cout<<"Yes"; return 0; } if(n==m&&(n%2==1)&&(n!=11)&&(n!=1)) cout<<"Yes"; else cout<<"No"; return 0;} B:Draw Frame 按照题目要求输出矩阵即可（多来点这种不用读题的T2好不好）。 Code: 123456789101112131415161...

Atcoder Beginner Contest 451 A：illegal 根据题意直接判断字符串长度是否等于5，按要求输出即可。 Code： 12345678910111213#include<bits/stdc++.h>using namespace std;#define int long longstring s;signed main(){ cin>>s; int len=s.size(); if(len%5==0) cout<<"Yes"; else cout<<"No"; return 0;} B：Personnel Change 将部门编号作为下标建立数组，对于每条输入，,最后输出数组中所有值即可。 Code: 1234567891011121314151617#include<bits/stdc++.h>using namespace std;#define int long longconst int maxn=1000002;int n,m,a,b;...

Atcoder Beginner Contest 450 A:3,2,1,GO 直接按题意输出即可。 Code： 123456789101112131415#include<bits/stdc++.h>using namespace std;#define int long longint n;signed main(){ cin>>n; for(int i=n;i>=1;i--) { if(i!=1) cout<<i<<","; else cout<<i; } return 0;} B:Split Ticketing 输入的时候注意不要输入的情况，随后按题意枚举即可（记得从西向东，因此吃了罚时）。 123456789101112131415161718192021222324252627282930#include<bits/stdc++.h>using namespace std;#define int long longco...

Atcoder Beginner Contest 449 A：π 直接输出 Code: 12345678910111213#include<bits/stdc++.h>using namespace std;#define int long longconst int maxn=100002;double n;double pi=3.141592653589793;signed main(){ scanf("%lf",&n); n/=2; printf("%lf",pi*n*n); return 0;} B：Deconstruct Chocolate 观察可知巧克力块永远保持矩形的形状，故只需要定义两个变量维护矩形的长宽即可。 Code： 123456789101112131415161718192021222324252627#include<bits/stdc++.h>using namespace std;#define int long longconst int maxn=1002;int h,w,q,op,tmp;i...