@throwingup 是个P
FantasticPsq 发布的帖子
-
RE: 彭少青的学习日志
昨天 2021/2/23 面试了字节后端实习,虽然面试时间长达差不多两个多小时,但是整个过程和面试官聊得很嗨,面试官也特别友好,面试过程也非常正式,感觉和蚂蚁金服相比就面试而言好太多了,面试官也不是只关注于种语言(蚂蚁金服只关注Java,可能是因为它这个职位就是叫做Java服务端实习),后端所有方面的知识点都有所问到,以下记录一下昨天面试没有答出来的问题:
- tcp的四次挥手答得很不好(知识点记不太清楚了),tcp和udp的socket编程connect的区别,以及为什么udp也要进行connect这两个问题没有回答出来。还有一个细节问题,SYN,ACK等是在tcp的头部还是在IP的头部,我不太记得了,盲猜在tcp头部,后来又坦白说自己不记得了
- 为什么Python要有协程,以及为什么会有GIL全局解释器锁,为什么Python没有解决这个问题?这几个问题答得很模糊,没有得到面试官的认可。
- Java中构造函数与析构函数能不能被重载,能不能被重写?为什么?重载的底层原理是怎么实现的?由于不记得析构函数的定义了,所以答得很差,重载的底层原理很久之前学过,但是时间太久了,没有复习,忘得差不多了。
- Redis缓冲的穿透,击穿以及雪崩出现的原因以及怎么解决,我回答时把穿透和击穿搞混了。
- 线程间通信的三种方式,我只记得信号量了
- tcp的拥塞控制没怎么答出来,忘了
主要这几点印象深刻一点,其他的答得还可以,算法也没有什么问题,主要是删除链表倒数第五个节点这个算法调试的时候出了点问题,然后面试官和我一起找问题,结果他以为我写对的地方写错了,然后就纠结了许久,后来发现是输出是指针没有后移,导致打印出来的都是头节点的值。
-
RE: 彭少青的学习日志
啊这,玩了好多天,玩得很高兴很痛快,乡下过年真的很热闹。年差不多过完了,是该收心学习了。希望春招能有个好结果!
今日刷题 1004. 最大连续1的个数 III
开始复习操作系统原理 -
RE: 彭少青的学习日志
1.27
被阿里面试官拿下之后,发现自己基础确实不扎实,这两天准备从头把Java基础复习了,目前复习到了Java多线程部分。
希望下一次面试完了之后能很有信心地拿下。
-
RE: 彭少青的学习日志
1.24
剑指offer 19 正则表达式 困难 终于把这个正则表达式搞懂了,以前看过,但是没搞懂,总结起来和数学的分类讨论差不多,需要考虑完全
力扣 28 实现strStr() 简单 这题暴力法非常简单,看了别人的题解,看懂了多种方式实现的kmp算法(第一种是动态规划解决KMP算法,一种是最长公共前缀和后缀实现KMP算法),看完之后自愧不如啊!
-
重温设计模式之七大原则
开闭原则
开闭原则要求当应用需求改变时,在不改变源代码或二进制代码的前提下,可以拓展模块的功能,以满足新的需求。
里氏替换原则
里氏替换原则要求子类可以拓展父类的功能,但不能改变父类原有的功能。
里氏替换原是继承复用的基础,它反映了基类与子类之间的关系,是对开闭原则的补充,是对实现抽象化的具体步骤的规范。依赖倒置原则
依赖倒置原则要求要面向接口编程,不要面向实现编程。
依赖倒置原则是实现开闭原则的重要途径之一,它降低了客户与实现模块之间的耦合。
依赖倒置原则的目的是通过要面向接口的编程来降低类间的耦合性。单一职责原则
单一职责原则提出对象不应该承担太多职责,如果一个对象承担了太多的职责,至少存在以下两个缺点:
- 一个职责的变化可能会削弱或者抑制这个类实现其他职责的能力;
- 当客户端需要该对象的某一个职责时,不得不将其他不需要的职责全都包含进来,从而造成冗余代码或代码的浪费。
接口隔离原则
接口隔离原则(Interface Segregation Principle,ISP)要求程序员尽量将臃肿庞大的接口拆分成更小的和更具体的接口,让接口中只包含客户感兴趣的方法。
接口隔离原则和单一职责都是为了提高类的内聚性、降低它们之间的耦合性,体现了封装的思想,但两者是不同的:- 单一职责原则注重的是职责,而接口隔离原则注重的是对接口依赖的隔离。
- 单一职责原则主要是约束类,它针对的是程序中的实现和细节;接口隔离原则主要约束接口,主要针对抽象和程序整体框架的构建。
迪米特原则
迪米特法则(Law of Demeter,LoD)又叫作最少知识原则,定义是:只与你的直接朋友交谈,不跟“陌生人”说话。
迪米特法则中的“朋友”是指:当前对象本身、当前对象的成员对象、当前对象所创建的对象、当前对象的方法参数等,这些对象同当前对象存在关联、聚合或组合关系,可以直接访问这些对象的方法。合成复用原则
合成复用原则又叫组合/聚合原则,它要求在软件复用时,要尽量先使用组合或者聚合等关联关系来实现,其次才考虑使用继承关系来实现。
如果要使用继承关系,则必须严格遵循里氏替换原则 -
重温redis设计与实现之跳跃表
Redis 跳跃表
- 重点内容:
1. 跳跃表是有序集合的底层实现之一 2,Redis的跳跃表实现由zskiplist和zskiplistNode两个结构组成,其中zskiplist 用于保存跳跃表的信息(比如头节点,尾节点,长度等),而zskiplistNode用于表示 跳跃表的节点 3. 每个跳跃表节点的层数是1到32之间的随机数,产生随机数用的是次幂定律(越大的数 出现的概率越小)。 4. 同一个跳跃表中,多个节点的分值可以相同,但是每个节点的成员对象必须是唯一的。 5. 跳跃表中的节点按照分值从小到大进行排列,当分支相同时,节点按照成员对象的大小 进行排序。
- zskiplist:
typedef struct zskiplist { // 表头节点和表尾节点 struct zskiplist *header,*tail; // 表中节点的数量 unsigned long length; // 表中层数量最大的节点的层数 int level; } zskiplist;
header和tail指针分别指向跳跃表表头节点和表尾节点,通过这两个指针,程序定位表头节点
和表尾节点的复杂度为O(1)。
通过使用length属性记录跳跃表中节点的数量,level表示表中层数最多的那个节点的层数,注意
并不包括头节点的层数。
- zskiplistNode
typedef struct zskiplistNode { struct zskiplistLevel { //前进指针 struct zskiplistNode *forward; // 跨度: // 两个节点之间的跨度越大,他们相距的越远 // 指向NULL的所有前进指针的跨度都为0 unsigned int span; } level[]; // 后退指针 struct zskiplistNode *backward; // 分值 double score; //成员对象:节点的成员对象是一个指针,他指向一个字符串对象,而字符串对象则保存一个SDS值 robj *obj; } zskiplistNode;
-
数据结构与算法总结之递归反转单链表
单链表节点的结构:
public class ListNode { int val; ListNode next; ListNode(int x){val = x;} }
反转整个链表
ListNode reverseLinkedList(ListNode head){ // base case:只有一个节点就返回那个节点 if(head.next==null){ return head; } ListNode last = reverseLinkedList(head.next); // 反转箭头 head.next.next = head; // 头节点的next置空 head.next = null; // 最后一个节点变成头节点 return last; }
反转前n个节点
反转前n个节点与反转整个链表的区别是需要记录第n个节点的下一个节点node,然后将
head.next
设置为node即可。public class ReverseLinkedList{ // 记录第n个节点的下一个节点 ListNoe lastNext = null; ListNode reverseFirstN(ListNode head,int N){ if(N==1){ lastNext = head.next; return head; } ListNode last = reverseFirstN(head.next,N-1); head.next.next = head; head.next = lastNext; return last; } }
反转区间[m,n]部分的链表
1<=m<=n<=链表长度
与反转前n个节点其实是一样的,只是需要找到第m个节点作为递归的头节点,并将第m-1个节点的下一个节点置为last即可。
public class ReverseLinkedList{ // 记录第n个节点的下一个节点 ListNoe lastNext = null; ListNode reverseBetween(ListNode head,int m,int n){ if(m==1){ return reverseFirstN(head,n); } // ListNode last = reverseBetween(head.next,m-1,n-1); // head.next = last; head.next = reverseBetween(head.next,m-1,n-1); } }
-
再看二分查找
最基本的二分查找
int binarySearch(int[] nums, int target) { int left = 0; int right = nums.length - 1; // 注意 while(left <= right) { int mid = left + (right - left) / 2; //注意 if(nums[mid] == target) return mid; else if (nums[mid] < target) left = mid + 1; else if (nums[mid] > target) right = mid - 1; } return -1; }
寻找左侧边界的二分查找——查找有多少个数小于目标数
int leftBound(int[] nums,int target) { int left = 0; int right = nums.length - 1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] < target) { left = mid + 1; } else { right = mid-1; } } if(left>=nums.length || nums[left+1]!=target){ return -1; } return left; }
寻找右侧边界的二分查找
int rightBound(int[] nums, int target) { int left = 0; int right = nums.length-1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] > target) { right = mid-1; } else { left = mid+1; } } if(right<0 || nums[right]!=target){ return -1; } return nums.length-1-right; }
-
聊一聊单例模式
单例模式
简介
单例模式(SingletonPattern)是Java中最简单的设计模式之一。这种类型的设计模式属于创建型模式,它提供了一种创建对象的最佳方式。
这种模式涉及到一个单一的类,该类负责创建自己的对象,同时确保只有单个对象被创建。这个类提供了一种访问其唯一的对象的方式,可以直接访问,不需要实例化该类的对象。
注意:
- 单例类只能由一个实例
- 单例类必须自己创建自己的唯一实例
- 单例类必须给所有其他对象提供这一实例
具体介绍
-
意图:保证一个类仅有一个实例,并提供了一个访问它的全局访问点
-
主要解决:一个全局使用的类频繁地创建与销毁。
-
何时使用:当您想控制实例数目,节省系统资源的时候。
-
如何解决:判断系统是否已经有这个单例,如果有则返回,如果没有则创建
-
关键代码:构造函数是私有的。
-
应用实例:
- Windows 是多进程多线程的,在操作一个文件的时候,就不可避免地出现多个进程或线程同时操作一个文件的现象,所以所有文件的处理必须通过唯一的实例来进行。
- 一些设备管理器常常设计为单例模式,比如一个电脑有两台打印机,在输出的时候就要处理不能两台打印机打印同一个文件。
-
优点:
- 在内存里只有一个实例,减少了内存的开销,尤其是频繁的创建和销毁实例
- 避免对资源的多重占用(比如写文件操作)。
-
缺点:
- 没有接口,不能继承,与单一职责原则冲突,一个类应该只关心内部的逻辑,而不应该关心外部怎么来实例化
-
使用场景:
- 要求产生唯一的序列号
- WEB中的计数器,不用每次刷新都在数据库里加一次,用单例先缓存起来
- 创建一个对象需要消耗的资源过多,比如I/O与数据库的连接等。
注意事项:getInstance()方法中需要使用同步锁synchronized(Singleton.class)防止多线程同时进入造成instance被多次实例化。
实现
我们将创建一个 SingleObject 类。SingleObject 类有它的私有构造函数和本身的一个静态实例。
SingleObject 类提供了一个静态方法,供外界获取它的静态实例。SingletonPatternDemo 类使用 SingleObject 类来获取 SingleObject 对象。
SingleObject.java
public class SingleObject { //创建 SingleObject 的一个对象 private static SingleObject instance = new SingleObject(); //让构造函数为 private,这样该类就不会被实例化 private SingleObject(){} //获取唯一可用的对象 public static SingleObject getInstance(){ return instance; } public void showMessage(){ System.out.println("Hello World!"); } }
从singleton类获取唯一的对象
SingletonPatternDemo.java
public class SingletonPatternDemo { public static void main(String[] args) { //不合法的构造函数 //编译时错误:构造函数 SingleObject() 是不可见的 //SingleObject object = new SingleObject(); //获取唯一可用的对象 SingleObject object = SingleObject.getInstance(); //显示消息 object.showMessage(); } }
单例模式的几种实现方式
1、懒汉式,线程安全
是否Lazy初始化:是
是否多线程安全:是
实现难度:易
描述:这种方式具备良好的lazy loading,能够在多线程中很好的工作,但是,效率很低,99%情况下不需要同步。
优点:第一次调用才初始化,避免内存浪费
缺点:必须加锁synchronized才能保证单例,但加锁会影响速率。
getInstance()的性能对应用程序不是很关键(该方法使用不太频繁)。
public class Singleton { private static Singleton instance; private Singleton (){} public static synchronized Singleton getInstance() { if (instance == null) { instance = new Singleton(); } return instance; } }
2、饿汉式
是否Lazy初始化:否
是否多线程安全:是
实现难度:易
描述:这种方式比较常用,但容易产生垃圾对象。
优点:没有加锁,执行效率会提高
缺点:类加载时就初始化,浪费内存。
它基于classloader机制避免了多线程的同步问题,不过,instance在类装载时就实例化,虽然导致类装载的原因有很多,在单例模式中大多数都是调用getInstance方法,但是也不能确定有其他的方式(或者其他的静态方法)导致类加载,这时候初始化instance显然没有达到lazy loading(懒加载就是延迟加载,即当对象需要用到的时候再去加载)的效果。
public class Singleton { private static Singleton instance = new Singleton(); private Singleton (){} public static Singleton getInstance() { return instance; } }
3、双检验/双重校验(DCL,即double-check locking)
JDK版本:1.5起
是否Lazy初始化:是
是否多线程安全:是
实现难度:较复杂
描述:这种方式采用双锁机制,安全且在多线程情况下能保持高性能。
public class Singleton { private volatile static Singleton singleton; private Singleton (){} public static Singleton getSingleton() { // HashMap以及ConcurrentHashMap的put都使用了 if (singleton == null) { synchronized (Singleton.class) { if (singleton == null) { singleton = new Singleton(); } } } return singleton; } }
4、登记式/静态内部类
是否懒加载:是
是否多线程安全:是、
实现难度:一般
描述:这种方式能达到双检锁方式00简单。对静态域使用延迟初始化,应使用这种方式而不是双检锁。这种方式只适用于静态域情况,双检锁方式可在实例域需要延迟初始化时使用。
这种方式利用了classloader机制来保证初始化instance时只有一个线程,它跟第 3 种方式不同的是:第 3 种方式只要 Singleton 类被装载了,那么 instance 就会被实例化(没有达到 lazy loading 效果),而这种方式是 Singleton 类被装载了,instance 不一定被初始化。因为 SingletonHolder 类没有被主动使用,只有通过显式调用 getInstance 方法时,才会显式装载 SingletonHolder 类,从而实例化 instance。想象一下,如果实例化 instance 很消耗资源,所以想让它延迟加载,另外一方面,又不希望在 Singleton 类加载时就实例化,因为不能确保 Singleton 类还可能在其他的地方被主动使用从而被加载,那么这个时候实例化 instance 显然是不合适的。这个时候,这种方式相比第 3 种方式就显得很合理。
public class Singleton { private static class SingletonHolder { private static final Singleton INSTANCE = new Singleton(); } private Singleton (){} public static final Singleton getInstance() { return SingletonHolder.INSTANCE; } }
5、枚举
JDK版本:JDK1.5起
是否Lazy初始化:否
是否多线程安全:是
实现难度:易
描述:这种实现方式还没有被广泛采用,但这是实现单例模式的最佳方法。它更简洁,自动支持序列化机制,绝对防止多次实例化。
这种方式是 Effective Java 作者 Josh Bloch 提倡的方式,它不仅能避免多线程同步问题,而且还自动支持序列化机制,防止反序列化重新创建新的对象,绝对防止多次实例化。不过,由于 JDK1.5 之后才加入 enum 特性,用这种方式写不免让人感觉生疏,在实际工作中,也很少用。
不能通过 reflection attack 来调用私有构造方法。public enum Singleton { INSTANCE; public void whateverMethod() { } }