Linux Linux 的体系结构 体系结构主要分为 用户态(用户上层活动)和内核态 内核： 本质是一段管理计算机硬件设备的程序 系统调用：内核的访问接口，是一种不能再简化的操作。 原子性的操作。 公用函数库： 系统调用的组合拳 Shell:命令解释器， 可编程 windows - cigwin 查看系统调用 Linux - man 2 syscalls less / more / cat /tail 切换默认shell 查找特定的文件 find 语法： find path [options] params 作用： 在指定目录下查找文件 1find ./ -name "fileName" # 精确查找 2find ~ -name "target*" # 模糊查找文件 3find ~ -iname "target*" # 忽略大小写的查找 4man find # 查看find的使用说明 检索文件内容 grep 语法： grep [options] pattern file 全称 Global Regular Expression Print 作用： 用于查找文件里符合条件的字符串, 智慧筛选出目标字符串所在的行 1grep "moo" target* # 查找 target* 开头的文件中包含 "moo" 的行 管道操作符 | 可以将指令连接起来，前一个指令的输出作为后一个指令的输入 只处理前一个命令的正确输出， 不处理错误输出 右边命令必须接收标准输入流，否则传递过程中数据会被抛弃 sed, awk, grep, cut, head, top, less, more, wc, join, sort, split 等 1grep 'partial\[true\]' test.

1. 垃圾回收之标记算法 GC 对象被判定为垃圾的标准 没有被其他对象引用 判定对象是否为垃圾的算法 引用计数法 通过判断对象的引用数量决定对象是否可以被回收 每个对象实例都有一个引用计数器，被引用则+1， 完成引用则-1 任何引用计数为0的实例 可以当做垃圾被回收 优点： 执行效率高， 程序受影响比较小 缺点： 无法检测出循环引用的情况，导致内存泄露 可达性分析算法 通过判断对象的引用链是否可达到，来决定对象是否可以被回收 可以作为GC Root的对象： 虚拟机栈中引用的对象（栈帧中的本地变量表） 方法区中的常量引用的对象 方法区中类静态属性引用的对象 本地方法栈中JNI(Native 方法) 的引用对象 活跃线程的引用对象 2. 谈谈你了解的垃圾回收算法 标记-清除法 Mark and Sweep 标记： 从根集合进行扫描，对存活的对象进行标记 清除： 对堆内存从头到尾进行线性遍历，回收不可达对象内存 Mark 阶段 -> Sweep 阶段 存在问题： 碎片化严重，大对象无法找到连续的内存，容易触发下次垃圾回收，outofmemery 复制算法 Coping - 年轻代 适用于对象存活时间比较低的情况 分为对象面和空闲面 对象在对象面上创建 存活对象从对象面复制到空闲面 将对象面所有对象内存清除 有点： 解决了碎片化问题， 顺序分配内存，简单高效，适用于对象存活率低的场景–年轻代 标记整理法 - 老年代 整理： 移动所有存活的对象，且按内存地址次序依次排列，然后将末端内存地址以后的内存全部回收。 优点： 避免了内存不连续，不用设置两块内存互换，适用于存活率高的场景 分代收集算法 垃圾回收算法的组合拳 按照生命周期的不同划分区域， 以采用不同的垃圾回收算法 提高了JVM的垃圾回收效率 Survivor Partitiion 年轻代 复制算法

Java 多线程与并发 1. 进程与线程的区别 关于jdk版本的选择 JDK8,JDK11:Oracle 长期支持 Java线程知识考点 进程和线程的区别 用户态和内核态的转换 进程和线程的由来 串行 初期的计算机只能执行串行执行任务，并且需要长时间等待用户输入 批处理 预先将用户指令集中成清单，批量串行处理用户指令，仍然无法并发执行 进程 进程独占内存空间，保存各自运行状态，相互间不干扰且可以互相切换，为并发处理任务提供了可能 线程 共享进程的内存资源，相互间切换更快捷，支持更细粒度的任务控制，使进程内的子任务得以并发执行 进程和线程的区别 进程是资源分配的最小单位，线程是CPU调度的最小单位 所有与进程相关的资源，都被记录在PCB中 进程是抢占处理机的调度单位；线程属于某个进程，共享其资源 线程只由堆栈寄存器、程序计数器和TCB组成 总结 线程不能看做独立应用，而进程可以看做独立应用 线程有独立的地址空间， 相互不影响，线程只是进程的不同执行路径 线程没有独立的地址空间，多进程的程序比多线程程序健壮 进程的切换比线程的切换开销大 Java进程和线程的关系 - Java对操作系统提供的功能进行封装，包括进程和线程 - 运行一个程序会产生一个进程，进程包含至少一个线程 - 每个进程对应一个JVM实例，多个线程共享JVM里的堆 - Java采用单线程编程模型，程序会自动创建主线程 - 主线程可以创建子线程，原则上要后于子线程完成执行 2. Thread 中start和run方法的区别 start native 方法 openjdk.java.net 调用start() 方法会创建一个新的子线程并启动 run()方法只是一个Thread的一个普通方法的调用 3. Thread 和Runnable 的区别 Thread 实现了Runnable接口的类，使得run支持多线程 Runnable 只有一个抽象方法run 因为单一继承的原则，推荐多使用Runnable结构 4. 如何给run()方法传参 实现方式主要有三种 构造函数传参 成员变量传参 回调函数传参 如何实现处理线程的返回值 实现方式主要有三种 主线程等待法（有多个变量的时候比较难处理，循环等待的时间是不精确的） 使用Thread的join()方法阻塞当前线程以等待子线程处理完毕(粒度不够细) 通过Callable接口是实现： 通过FutureTask 或者 线程池获取 5.

javabasic 课程涉及到的Java代码，持续更新中…

算法面试到底是什么鬼？ 1-1 算法面试不仅仅是正确的回答问题 算法面试的目的 展现思考问题的方式 算法面试过程 看做是和面试官一起探讨一个问题的解决方案。对于问题的细节和应用环境，可以和面试官沟通。 这种沟通本身很重要，它暗示着你思考问题的方式。 我们需要对一组数据进行排序。 快速排序算法 O(nlogn) 正确+更优 这组数据有什么样的特征？ 有没有可能包含有大量的重复元素？ 如果有这种可能的话，三路快排是更好的选择。 Java 默认是三路快排。 这组数据有什么样的特征？ 是否大部分数据距离它的正确位置很近？是否近乎有序？ 如果是这样的话插入排序更优 是否数据的取值范围非常有限？比如学生成绩排序。 计数排序更优 对排序有什么额外的要求 是否需要稳定排序 归并排序更优 数据的存储状况是怎样的 如果使用链表存储，归并排序更优 数据的大小是否可以装在内存里， 外部排序 什么是正确的回答一个算法问题 正确还包含对问题的独到见解，容错性， 1-2 算法面试只是面试的一部分 算法面试优秀不意味着技术面试优秀 算法面试只是技术面试的一部分 项目经历和项目中遇到的实际问题 你遇到印象最深的bug是什么？ 面向对象 设计模式 网络相关：安全相关，内存相关，并发相关 系统设计： scalability 面试不仅仅是考察技术水平，以及对过去项目的思考 项目经历 通过过去了解你的思考行为方式 遇到的最大的挑战 犯过的错误 遇到的失败 最享受的工作内容 遇到冲突的处理方式 做的最与众不同的事儿 准备好合适的问题问面试官 1-3 如何准备算法面试 避免完美学习 使用时间片学习 远远不需要达到竞赛的水平 不要轻视基础算法和数据结构，而只关注有意思的题目 各种排序算法 技术数据结构和算法的实现： 如堆，二叉树，图 基础数据结构的使用： 如链表、栈、队列、哈希表、图、Tire、并查集 基础算法： 深度优先、广度优先、二分查找、递归 基本算法思想：递归、分治、回溯搜索、贪心、动态规划 选择合适的OJ online judge leetcode： online portal for interview

二叉树和递归 二叉树天然的递归结构 满二叉树 二叉树的前序遍历 递归实现 1void preOrder(TreeNode node){ 2 if(node==null){ 3 return; // 递归终止条件 4 } 5 System.out.print(node.val); 6 preOrder(node.left); // 递归过程 7 preOrder(node.right); 8} 二叉树的定义：空是一棵二叉树 二叉树总是否包含某个key 1boolean contain(TreeNode node, Key key){ 2 if(node == null){ 3 return false; 4 } 5 if(key == node.key){ 6 return true; 7 } 8 if(contain(node.left,key)|| contain(node.right, key)){ 9 return true; 10 } 11 return false; 12} 1// c++ 释放二叉树的内存 2void destory(TreeNode node){ 3 if(node == null){ 4 return; 5 } 6 destory(node.

动态规划基础 什么是动态规划 斐波那契数列 Fibonacci Sequence 1//时间复杂度 应该是指数级 2int fib(){ 3 if(n==0){ 4 return 0; 5 } 6 if(n==1){ 7 return 1; 8 } 9 return fib(n-1)+fib(n-2); 10} 递归会有很多的重复计算，重复的计算量会非常大。 所以想办法对重复的计算 只计算一次 记忆化搜索-自上而下的解决问题 改进的Fibonacci 1// 记忆化搜索 时间复杂度O(n) 2int memo[]; 3int fib(){ 4 if(n==0){ 5 return 0; 6 } 7 if(n==1){ 8 return 1; 9 } 10 if(memo[n]==-1){ 11 memo[n]=fib(n-1)+fib(n-2); 12 } 13 return memo[n]; 14} 动态规划-自下而上的解决问题 1// 动态规划 2int fib(int n){ 3 vector<int> memo(n+1, -1); 4 memo[0] = 0; 5 memo[1] = 1; 6 for(int i=2; i<n;i++){ 7 memo[i] = memo[i-1]+memo[i-2]; 8 } 9 return memo[n]; 10} 动态规划：

图 图的表示 邻接矩阵（Adjacent Matrix） 邻接表（Adjacent Matrix） 邻接表适合表示稀疏图（Sparse Graph） 邻接矩阵适合表示稠密图（Dense Graph） 稀疏图 稠密图和完全图 寻路 获得两点之间的一条路径 图的深度优先遍历-时间复杂度 稀疏图（邻接表）：O(V+E) 稠密图（邻接矩阵）：O(v^2^) 深度优先遍历算法-有向图 dfs 查看是否有环- 有向图 广度优先遍历和最短路径 借助队列实现 广度优先遍历求出了无权图的最短路径 图的广度优先遍历-时间复杂度 稀疏图（邻接表）：O(V+E) 稠密图（邻接矩阵）：O(v^2^) 无权图的应用- 迷宫生成，PS抠图 flood fill 魔棒抠图 连通分量 扫雷 走迷宫、 迷宫生成 迷宫的本质是一棵树 本质是一个生成树的过程 不能只用一种方式遍历， 随机队列遍历 欧拉路径 哈密尔顿路径 二分图 同学选课 地图着色

最小生成树 Minimum Span Tree 有权图 Weight Graph 邻接矩阵 Adjacent Matrix 邻接表 使用Edge 表示每一条连接边 最小生成树问题和切分定理 带权无向图、连通图 找V-1条边 切分定理 Cut Property 把图中的节点分成两部分，成为一个切分(Cut) 如果一个边的两个端点，属于切分不同的两边，这个边成为横切边(Crossing Edge); 切分定理： 给定任意切分，横切边中权值最小的边必然属于最小生成树 Prim算法 Lazy Prim Lazy Prim 最小堆中依然有不会是横切边的边。 Lazy Prim 的时间复杂度为O(ElogE) Prim 算法优化 时间复杂度O(ElogV) IndexMinHeap Kruskal算法 使用并查集 使用Union Find 快速判断环 最小生成树问题 最小生成树问题思考 Lazy Prim O(ElogE) Prim O(ElogV) Kruskal O(ElogE) 如果横切边有相等的边 根据具体的算法实现，每次选择一个边 此时，图存在多个最小生成树 Vyssotsky’s Algorithm 将边逐渐添加到生成树中 一旦形成环，删除环中权值最大的边