字节跳动抖音生活服务平台治理后端开发工程师一面面试经历，主要考察了Go语言基础、数据库设计、缓存机制和算法题，面试时长约53分钟
LeetCode 239 - 滑动窗口最大值（Sliding Window Maximum）
使用单调队列解决滑动窗口最大值问题，通过维护递减队列来高效获取每个窗口的最大值，时间复杂度O(n)，空间复杂度O(k)
LeetCode 560 - 和为 K 的子数组（Subarray Sum Equals K）
使用前缀和和哈希表解决子数组和问题，通过维护前缀和的出现次数来统计和为K的子数组数量
LeetCode 149 - 直线上最多的点数（Max Points on a Line）
使用哈希表存储斜率信息，通过枚举每个点作为基准点，计算与其他点形成的直线斜率，统计最多共线的点数。核心思路是避免浮点数精度问题，使用最简分数表示斜率。
LeetCode 50 - Pow(x, n)（快速幂算法）
使用快速幂算法高效计算 x 的 n 次方，通过二进制分解将时间复杂度从 O(n) 优化到 O(log n)，是数学计算中的经典优化技巧
LeetCode 172 - 阶乘后的零（Factorial Trailing Zeroes）
通过统计因子中5的个数来计算阶乘末尾零的数量，关键在于理解每个零都是由2和5配对产生的
LeetCode-23-合并 K 个升序链表
本文介绍了 LeetCode 第 23 题——合并 K 个升序链表的解题思路，包括最小堆的解法和顺序合并的解法。
技术八股: 悲观锁与乐观锁
本文深入探讨了多线程编程中两种核心的锁机制：悲观锁和乐观锁。内容涵盖了互斥锁、自旋锁、读写锁的原理和适用场景，并详细对比了悲观锁与乐观锁的思想、实现方式及优缺点，帮助你更好地理解并发控制，应对面试挑战。
LeetCode 148 - 排序链表（Sort List）
问题描述 给你链表的头结点 head，请将其按 升序 排列并返回 排序后的链表。 示例 示例 1： 12输入：head = [4,2,1,3]输出：[1,2,3,4] 示例 2： 12输入：head = [-1,5,3,4,0]输出：[-1,0,3,4,5] 示例 3： 12输入：head = []输出：[] 提示 链表中节点的数目在范围 [0, 5 * 10^4] 内 -10^5 <= Node.val <= 10^5 进阶 你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？ 解题思路 要排序链表，最直观的方法是先转换成数组，排序后再转回链表。但是这种方法需要 O(n) 的额外空间。如果要满足进阶要求，我们需要使用对链表友好的归并排序。 对于链表排序，可以考虑两种归并排序实现方式： 自顶向下：递归实现，空间复杂度为 O(log n) 自底向上：迭代实现，空间复杂度为 O(1) 方法一：自底向上归并排序 自底向上的归并排序是一种非递归的归并排序，它的基本思想是： 先将链表拆分成长度为 1 的多个子链表 然后两两合并成长度为 2 的子链表 再两两合并成长度为 4 的子链表 以此类推，直到整个链表排序完成 这种方法的空间复杂度是 O(1)，满足进阶要求。 代码实现（优化版） 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */func sortList(head *ListNode) *ListNode { // 处理空链表或单节点链表 if head == nil || head.Next == nil { return head } // 计算链表长度 length := getLength(head) // 创建哑节点，简化边界情况处理 dummy := &ListNode{Next: head} // 自底向上归并排序 // 每次迭代子链表长度乘以2（1->2->4->8...） for subLength := 1; subLength < length; subLength <<= 1 { prev, curr := dummy, dummy.Next // 每轮迭代处理整个链表 for curr != nil { // 第一个子链表的头节点 head1 := curr // 切割第一个子链表 for i := 1; i < subLength && curr != nil && curr.Next != nil; i++ { curr = curr.Next } // 第二个子链表的头节点 head2 := curr.Next curr.Next = nil // 断开第一个子链表 curr = head2 // 切割第二个子链表 for i := 1; i < subLength && curr != nil && curr.Next != nil; i++ { curr = curr.Next } // 记录下一次要处理的节点 var next *ListNode = nil if curr != nil { next = curr.Next curr.Next = nil // 断开第二个子链表 } // 合并两个子链表 merged := mergeTwoLists(head1, head2) prev.Next = merged // 移动prev到合并后链表的末尾 for prev.Next != nil { prev = prev.Next } // 处理下一对子链表 curr = next } } return dummy.Next}// 获取链表长度func getLength(head *ListNode) int { length := 0 for node := head; node != nil; node = node.Next { length++ } return length}// 合并两个有序链表func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode { dummy := &ListNode{} curr := dummy for l1 != nil && l2 != nil { if l1.Val < l2.Val { curr.Next = l1 l1 = l1.Next } else { curr.Next = l2 l2 = l2.Next } curr = curr.Next } // 连接剩余部分 if l1 != nil { curr.Next = l1 } else { curr.Next = l2 } return dummy.Next} 方法二：自顶向下归并排序 自顶向下的归并排序是一种递归实现，它的基本思想是： 使用快慢指针找到链表中点，将链表分为两半 递归排序两个子链表 合并两个排序后的子链表 这种方法的空间复杂度是 O(log n)，因为递归栈的深度是 log n。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950func sortList(head *ListNode) *ListNode { // 递归终止条件 if head == nil || head.Next == nil { return head } // 使用快慢指针找到链表中点 slow, fast := head, head.Next for fast != nil && fast.Next != nil { slow = slow.Next fast = fast.Next.Next } // 切分链表 mid := slow.Next slow.Next = nil // 递归排序两个子链表 left := sortList(head) right := sortList(mid) // 合并排序后的子链表 return mergeTwoLists(left, right)}// 合并两个有序链表func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode { dummy := &ListNode{} curr := dummy for l1 != nil && l2 != nil { if l1.Val < l2.Val { curr.Next = l1 l1 = l1.Next } else { curr.Next = l2 l2 = l2.Next } curr = curr.Next } // 连接剩余部分 if l1 != nil { curr.Next = l1 } else { curr.Next = l2 } return dummy.Next} 方法比较 方面 自底向上（迭代） 自顶向下（递归） 时间复杂度 O(n log n) O(n log n) 空间复杂度 O(1) O(log n) 优点 常数空间复杂度 代码简洁易懂 缺点 实现较复杂 需要额外的递归栈空间 推荐度 ★★★★★ ★★★★☆ 错误分析与总结 在尝试实现自底向上归并排序时，我遇到了几个典型的链表操作边界问题。以下是我的错误代码和具体分析，希望能帮助我（以及他人）避免重蹈覆辙。 初始错误代码 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970func sortList(head *ListNode) *ListNode { if head == nil || head.Next == nil { return head } dummyHead := &ListNode{} dummyHead.Next = head length := 0 cur := head for cur != nil { cur = cur.Next length++ } for k := 1; k < length; k <<= 1 { prev, cur := dummyHead, dummyHead.Next for cur != nil { head1 := cur // 这里应该是1开始 for i := 0; i < k && cur.Next != nil; i++ { cur = cur.Next } head2 := cur.Next cur.Next = nil // 可能会带来cur = nil cur = head2 for i := 0; i < k && cur != nil && cur.Next != nil; i++ { cur = cur.Next } var next *ListNode if cur != nil { next = cur.Next cur.Next = nil } prev.Next = mergeSorted(head1, head2) for prev.Next != nil { prev = prev.Next } // 这里没必要加，因为后面的处理完自然会加上 prev.Next = next cur = next } } return dummyHead.Next}func mergeSorted(head1, head2 *ListNode) *ListNode { dummyHead := &ListNode{} cur := dummyHead for head1 != nil && head2 != nil { if head1.Val < head2.Val { cur.Next = h...
技术八股: I/O多路复用详解 - select/poll/epoll原理与对比
深入解析I/O多路复用技术原理，详细对比select、poll、epoll的实现机制、性能差异及应用场景，掌握C10K问题的解决方案