2024-01-25 22:06:40    27    0    0

人生第二次现场面试。一次一二面面完,大约两小时。面试体验挺好,和大厂是另一种感觉。
办公地点寸土寸金,电梯负一楼直达地铁站,步行几百米就是三里屯,妈妈再也不用担心我上班路上风吹雨淋受冻了。
![](你们真会享受.jpg)
西二旗科技园是什么鬼地方。

获得hr小姐姐的茉莉花茶一瓶。

感觉业务蛮有意思的,是他们自研的基于postgresql的分布式数据库的工具开发,我的理解是工具本身主要用go来写,涉及到用c/c++在数据库内核开接口。北京主要做研发。杭州主要做计费、管理平台的开发、销售、运维。

面试内容主要是八股。

一面:

  • 计网相关的八股文:TCP的三次握手四次挥手,能不能用udp实现http,怎么查看程序占用的端口号,快开始,慢重传。丢失第一个FIN报文会发生什么,select/poll/epoll
  • 操作系统做进程调度前后切换了哪些东西?
  • 僵尸进程
  • 线程之间有哪些共享资源的方法
  • 遇到过死锁吗,你自己有哪些常用的避免方法?
  • 虚拟地址到物理地址的转换是对操作系统透明的吗?(我TM忘了MMU这个玩意儿,全都说成了CPU,尴尬)

二面:
主要是go和数据库的八股。
go:

  • map/slice及其实现,口头举了几个简单的slice的例子判断一下会发生什么,就那些常见的陷阱题。
  • GMP
  • 为什么用协程在用户态调度比用内核调度更好
  • 抢占式调度的实现
  • channel的实现,如果基于channel实现一个生产者消费者模型,可能的瓶颈在哪里?如果生产者和消费者的速率相当,但是面临激烈的锁竞争,有哪些可能的优化方法?
  • 多个缓冲区的消息队列的负载均衡,这一点自认为答得不好,可能得看看真正的消息队列的实现。
  • 你知道pprof是怎么做到收集这些profile信息的吗?
  • go程序的编译过程
  • CGO,我额外讲了在前司学到的如何在CGO_ENABLE=1的前提下静态链接。

数据库:

  • 主键索引
  • 事务的隔离性是如何实现的
  • MVCC的细节
  • 你对分布式数据库有哪些了解?
    没有raft/paxos这种分布式共识算法也敢叫分布式数据库?(狗头保命)
2024-01-23 20:56:10    11    0    0

图片标题

green    2023-04-12 14:59:24    243    0    0

面试官很友好,自己太菜了。意识到了自己对计算机的认知有多么浅薄 orz

一共75分钟,讲的口干舌燥

不知道哪些是答得不对或者不全的地方,也请懂的同学不要藏着掖着,可以在讨论区聊聊呀~

一个小厂面试难度竟然已经如此可怕了

感觉分布式已经是后端的必要技术栈了。卷成这样也是离谱。也许该好好考虑考虑 #互联网没坑了,还能去哪里# 这个话题了。

等我毕业了,银行等国企的坑也该填满了,感觉自己每多上一天学,就业就恶化一天。鉴定为:寄

回想起20年字节的实习门槛,回想起那时某些双非本科一个班能秋招4个进字节。努力在时代面前不值一提~

项目

HTTP/TCP的相关知识:三次握手,Long connection的含义、半连接的作用
socket操作,socket操作与三次握手之间的对应关系。

Session、Cookie、Token

Mysql为什么选择B+树(开始吟唱),答了支持范围查询(不能用哈希)+减少IO次数(B树、二叉树、红黑树、跳表都有更多次IO的问题)

Mysql有哪些优化措施:“先说这是一个很大的话题”,答了建立恰当的索引(以及避免索引失效)、低NF以空间换时间、改用适合业务场景的其他执行引擎(MyIASM, RocksDB)、分库分表(水平垂直分库分表)、建立主从集群(讲了一主多从、主从分离)。

操作系统:Page Cache的作用,操作系统进程的状态(答得不好,状态的名称记不太清了)、操作系统的进程调度算法(没看过,看过也忘了,寄)。

用过哪些命令。

磁盘IO有哪些优化?只想到了减少访存次数+顺序读写,面试官说之前提到的Cache也可以(傻了,竟然没想到),讲讲磁盘的Cache(说了mmap这种direct IO和缓冲IO,感觉说的不太好,可能没扣题)。

内存满了之后怎么办?答了通过页面淘汰算法淘汰页面,比如FIFO, LRU, LFU。

Go:协程切换VS线程切换,讲讲协程切换的细节(说了恢复上下文,包括保存的寄存器信息和pc指针,懂的同学可以讲讲)

容器:讲了讲docker的大体实现,docker是做什么的。

知道K8S这种容器编排吗?是做什么的?不会K8S,直接寄,听面试官大概讲了讲K8S用于万规模以

2023-04-07 20:54:07    123    0    0

https://article.itxueyuan.com/O0Pg3

参考类似二分查找的方法,每次选择按照二进制位统计,“更少”的那一堆。
当然了,这种方法要借助文件。每次,按照二进制位是0还是1,将其分为两部分。分好的结果可以append到文件中。
另一种方法:直接使用bitmap来统计,每个元素是否出现。复杂度O(N),需要大约512M内存空间。

2023-03-18 21:06:01    65    0    0

给你一个整型数组 nums,在数组中找出由三个数组成的最大乘积,并输出这个乘积。

https://leetcode.cn/problems/maximum-product-of-three-numbers/

分类讨论:三个正数|一个正数两个负数|两个正数一个负数|整个数组没有正数。

  • 三个正数:排序后最大的三个;
  • 一个正数两个负数:最小的两个负数*最大的正数;
  • 没有正数:最大的三个数;
  • 两正一负:如果只有这三个数,则就是最大三个数,如果还有一个正数或者负数,都能凑出更大的正数,因此不考虑。
    因此,需要找出最大的三个数和最小的两个数。
    寻找方法:一次扫描,然后暴力记录。
  1. int min1=INT_MAX, min2=INT_MAX;
  2. int max1=INT_MIN, max2=INT_MIN, max3=INT_MIN;
  3. for(int num:nums){
  4. //先更新最小值
  5. if(num<min1){
  6. min2=min1;
  7. min1=num;
  8. }
  9. else if(num<min2){
  10. min2=num;
  11. }
  12. //更新最大值
  13. if(num>max1){
  14. max3=max2;
  15. max2=max1;
  16. max1=num;
  17. }
  18. else if(num>max2){
  19. max3=max2;
  20. max2=num;
  21. }
  22. else if(num>max3){
  23. max3=num;
  24. }
  25. }
  26. return max(max1*max2*max3, min1*min2*max1);
2023-03-04 19:53:59    93    0    0

基本概念

滑动窗口是一种基于双指针的一种思想,两个指针指向的元素之间形成一个窗口。

分类:窗口有两类,一种是固定大小类的窗口,一类是大小动态变化的窗口。

应用:什么情况可以用滑动窗口来解决实际问题呢?

  1. 一般给出的数据结构是数组或者字符串
  2. 求取某个子串或者子序列最长最短等最值问题或者求某个目标值时
  3. 该问题本身可以通过暴力求解

固定窗口大小:通常直接固定下窗口的长度,for循环只用关注最左边的点l,每次进入l+window.size,出栈l即可。
非固定窗口大小:扩张r, 直到符合要求,然后收缩l。

leetcode类型题目:
https://leetcode.cn/problems/minimum-window-substring
https://leetcode.cn/problems/find-all-anagrams-in-a-string/

2023-02-26 17:43:49    49    0    0

title

2023-02-26 16:55:58    61    0    0

剑指 Offer 52. 两个链表的第一个公共节点

https://leetcode.cn/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof/

虽然标为【简单】,但其实进阶做法较有技巧。其和链表成环一样,都能想到双指针。但是本题双指针的取巧性更强。

具体而言,假设链表A的私有部分长为a,链表B的私有部分长为b,二者的公共部分(如有)长度为c。

在aPtr走到尽头时,走了长度为a+c,此时只要将其接到B上继续往下走,走长度b时,总步数为a+c+b。而bPtr走到尽头时,接到A上继续往下走长度为a时,总步数也为a+c+b,即二者重合时【而且】此时二者都在第一个公共节点上。

  1. class Solution {
  2. public:
  3. ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
  4. if (headA == nullptr || headB == nullptr) {
  5. return nullptr;
  6. }
  7. ListNode *pA = headA, *pB = headB;
  8. while (pA != pB) {
  9. pA = pA == nullptr ? headB : pA->next;
  10. pB = pB == nullptr ? headA : pB->next;
  11. }
  12. return pA;
  13. }
  14. };
2023-02-24 23:04:26    62    0    0

不允许使用任何比较运算符(例如>,<,?:等),判断语句,maxmin等函数,判断a和b的大小?

解法1:绝对值法:

return a+b+abs(a-b)/2

如果a比较大,返回a,如果b比较大,返回b

解法2:
计算a-b,取出最高位的元素,即r=(a-b)&0x8000_0000
res=r==1?a:n

2023-02-17 19:52:17    62    0    0

难度:leetcode hard
给定 n 个非负整数表示每个宽度为 1的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。
原文地址:
https://leetcode.cn/problems/trapping-rain-water/
title

这道题的算法原理较好想到,其实就是确定任何一点的左右最大值,就可以得知这个点能够装到的最高的水。难在如果先做一遍遍历再将最大值存在数组中,无法做到从O(N)空间到O(1)的优化。
实际使用的方法是难点【双指针】。其实就是,维护left指针和right指针,如果当前left点的高度比right更低,那么left点的储水量就已知了(因为right向左移动,新值一定比right更大,因此,限制当前left点储水高度的,一定是left点的高度。)在求出left点的储水量后,向右边移动left即可。如此继续这个步骤,直到left==right。

这道题其实和leetcode medium中的盛水最多的容器很相似,从两端开始贪心,在找到当前限制条件(短板)后,提高短板到下一个极值点。

1/5