快手可灵 - Java后端 一面 总结

1. 先做个自我介绍

您好，我是XXX，目前在XXX大学读计算机专业。我对后端开发和算法都比较感兴趣，有一些项目经验和实习经历。

技术方面，熟悉Java、Spring Boot、MySQL、Redis这些后端技术。算法基础还可以，参加过一些编程竞赛，平时也会刷LeetCode保持手感。

实习经历方面，之前在一家公司做过底层开发，接触过Linux内核相关的工作，对操作系统原理有比较深入的了解。

项目上做过对话系统，实现了多轮对话、上下文管理等功能。也做过一些常规的Web项目，处理过并发优化的问题。

我对快手可灵的AI视频生成技术很感兴趣，希望能加入团队学习和成长。

2. 算法题：二叉树翻转（镜像）

这题要把二叉树左右翻转，就是交换每个节点的左右子树。

思路是递归处理。对于每个节点，先递归翻转它的左子树和右子树，然后交换左右子树的位置就行了。

递归的终止条件是节点为空，直接返回null。

时间复杂度是O(n)，因为每个节点都要访问一次。空间复杂度是O(h)，h是树的高度，主要是递归调用栈的开销。

也可以用迭代的方式，用队列做层序遍历，每次取出一个节点就交换它的左右子树，然后把子节点加入队列继续处理。

3. 算法题：二叉树的层序遍历

层序遍历就是一层一层地遍历二叉树，每层从左到右。

用队列实现比较简单。先把根节点放进队列，然后循环处理：每次记录当前队列的大小，这就是当前层有多少个节点。然后把这一层的节点都取出来，记录它们的值，同时把它们的子节点加入队列。

关键点是要知道每层有多少个节点，所以在处理每层之前先记录队列大小。

时间复杂度O(n)，每个节点访问一次。空间复杂度O(n)，队列最多存储一层的节点，最坏情况最后一层有n/2个节点。

4. 说说你的实习经历，做过什么工作？

我之前在一家做系统软件的公司实习，主要做Linux相关的底层开发。

具体工作是开发设备驱动程序，需要在内核态编写代码，让硬件设备能够被操作系统识别和使用。这个工作和普通的应用开发很不一样，需要对操作系统原理有深入理解。

印象最深的是开发一个网络设备驱动。这个驱动要处理网络数据包的收发，对性能要求很高。我需要理解网络协议栈、DMA传输、中断处理这些底层机制。

调试也很困难，因为内核代码出错可能导致系统崩溃，不能用常规的调试工具，主要靠打印日志和分析崩溃信息。

通过这段实习，我对操作系统、内存管理、并发控制这些有了更深的理解，也锻炼了解决复杂问题的能力。

5. 内核驱动开发和普通应用开发有什么区别？

区别还挺大的。

首先是运行环境不同。驱动运行在内核态，有最高权限，可以直接操作硬件。应用程序运行在用户态，权限受限，要通过系统调用访问资源。

编程限制也不同。内核态不能用标准C库的很多函数，不能做浮点运算，在某些上下文不能睡眠，栈空间也很小。应用开发就自由多了。

错误后果不同。内核代码出错可能导致整个系统崩溃蓝屏，所以要特别小心。应用程序崩溃只影响自己，操作系统会把它终止掉。

调试方式不同。内核主要靠printk打印日志，或者用串口调试。应用程序可以用gdb这些调试器，方便很多。

并发处理更复杂。内核有中断、软中断、进程上下文等多种执行环境，要仔细处理同步问题。应用主要是多线程，相对简单。

性能要求更高。内核代码要考虑每一点开销，内存分配、锁的使用都要很谨慎。

虽然内核开发难度大，但能学到很多底层知识，对理解计算机系统很有帮助。

6. 介绍一个你在内核开发中常用的函数

我经常用kmalloc这个函数，用来在内核中分配内存。

它的参数有两个，一个是要分配的字节数，另一个是分配标志。分配标志很重要，决定了内存从哪里分配，能不能睡眠。

常用的标志有GFP_KERNEL和GFP_ATOMIC。GFP_KERNEL用于普通情况，可能会睡眠等待内存，适合在进程上下文使用。GFP_ATOMIC是原子分配，不能睡眠，适合在中断处理或持有自旋锁时使用。

kmalloc分配的内存是物理连续的，适合小块内存，一般不超