字节一面过了,准备二面
一面主要是计网方面答得比较差,这几天重点复习一下计算机网络。
另外感觉许多知识点没有理解的通透,导致回答起来不太准备与完整。
昨天 2021/2/23 面试了字节后端实习,虽然面试时间长达差不多两个多小时,但是整个过程和面试官聊得很嗨,面试官也特别友好,面试过程也非常正式,感觉和蚂蚁金服相比就面试而言好太多了,面试官也不是只关注于种语言(蚂蚁金服只关注Java,可能是因为它这个职位就是叫做Java服务端实习),后端所有方面的知识点都有所问到,以下记录一下昨天面试没有答出来的问题:
主要这几点印象深刻一点,其他的答得还可以,算法也没有什么问题,主要是删除链表倒数第五个节点这个算法调试的时候出了点问题,然后面试官和我一起找问题,结果他以为我写对的地方写错了,然后就纠结了许久,后来发现是输出是指针没有后移,导致打印出来的都是头节点的值。
被阿里面试官拿下之后,发现自己基础确实不扎实,这两天准备从头把Java基础复习了,目前复习到了Java多线程部分。
希望下一次面试完了之后能很有信心地拿下。
剑指offer 19 正则表达式 困难 终于把这个正则表达式搞懂了,以前看过,但是没搞懂,总结起来和数学的分类讨论差不多,需要考虑完全
力扣 28 实现strStr() 简单 这题暴力法非常简单,看了别人的题解,看懂了多种方式实现的kmp算法(第一种是动态规划解决KMP算法,一种是最长公共前缀和后缀实现KMP算法),看完之后自愧不如啊!
啊这,玩了好多天,玩得很高兴很痛快,乡下过年真的很热闹。年差不多过完了,是该收心学习了。希望春招能有个好结果!
今日刷题 1004. 最大连续1的个数 III
开始复习操作系统原理
开闭原则要求当应用需求改变时,在不改变源代码或二进制代码的前提下,可以拓展模块的功能,以满足新的需求。
里氏替换原则要求子类可以拓展父类的功能,但不能改变父类原有的功能。
里氏替换原是继承复用的基础,它反映了基类与子类之间的关系,是对开闭原则的补充,是对实现抽象化的具体步骤的规范。
依赖倒置原则要求要面向接口编程,不要面向实现编程。
依赖倒置原则是实现开闭原则的重要途径之一,它降低了客户与实现模块之间的耦合。
依赖倒置原则的目的是通过要面向接口的编程来降低类间的耦合性。
单一职责原则提出对象不应该承担太多职责,如果一个对象承担了太多的职责,至少存在以下两个缺点:
接口隔离原则(Interface Segregation Principle,ISP)要求程序员尽量将臃肿庞大的接口拆分成更小的和更具体的接口,让接口中只包含客户感兴趣的方法。
接口隔离原则和单一职责都是为了提高类的内聚性、降低它们之间的耦合性,体现了封装的思想,但两者是不同的:
迪米特法则(Law of Demeter,LoD)又叫作最少知识原则,定义是:只与你的直接朋友交谈,不跟“陌生人”说话。
迪米特法则中的“朋友”是指:当前对象本身、当前对象的成员对象、当前对象所创建的对象、当前对象的方法参数等,这些对象同当前对象存在关联、聚合或组合关系,可以直接访问这些对象的方法。
合成复用原则又叫组合/聚合原则,它要求在软件复用时,要尽量先使用组合或者聚合等关联关系来实现,其次才考虑使用继承关系来实现。
如果要使用继承关系,则必须严格遵循里氏替换原则
单链表节点的结构:
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个节点的下一个节点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;
}
}
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;
}
1. 跳跃表是有序集合的底层实现之一
2,Redis的跳跃表实现由zskiplist和zskiplistNode两个结构组成,其中zskiplist
用于保存跳跃表的信息(比如头节点,尾节点,长度等),而zskiplistNode用于表示
跳跃表的节点
3. 每个跳跃表节点的层数是1到32之间的随机数,产生随机数用的是次幂定律(越大的数
出现的概率越小)。
4. 同一个跳跃表中,多个节点的分值可以相同,但是每个节点的成员对象必须是唯一的。
5. 跳跃表中的节点按照分值从小到大进行排列,当分支相同时,节点按照成员对象的大小
进行排序。
typedef struct zskiplist {
// 表头节点和表尾节点
struct zskiplist *header,*tail;
// 表中节点的数量
unsigned long length;
// 表中层数量最大的节点的层数
int level;
} zskiplist;
header和tail指针分别指向跳跃表表头节点和表尾节点,通过这两个指针,程序定位表头节点
和表尾节点的复杂度为O(1)。
通过使用length属性记录跳跃表中节点的数量,level表示表中层数最多的那个节点的层数,注意
并不包括头节点的层数。
typedef struct zskiplistNode {
struct zskiplistLevel {
//前进指针
struct zskiplistNode *forward;
// 跨度:
// 两个节点之间的跨度越大,他们相距的越远
// 指向NULL的所有前进指针的跨度都为0
unsigned int span;
} level[];
// 后退指针
struct zskiplistNode *backward;
// 分值
double score;
//成员对象:节点的成员对象是一个指针,他指向一个字符串对象,而字符串对象则保存一个SDS值
robj *obj;
} zskiplistNode;