一面

15c68ad5ba57c4307aaf8b5475c4205
9.19面试的，前面投实习的时候再加秋招前面简历挂了好多次了，这次面的时候就感觉大概率也g了，果然面完半小时就挂了。

面试过去首先面试官介绍了他们部门是做什么的，然后我做了自我介绍，然后面试官说给你三十分钟，让手撕三个力扣题，第一个是写一个查找字符串数组中的最长公共前缀；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def longest_common_prefix(strs):
    if not strs:
        return ""
    
    # 取第一个字符串作为基准进行比较
    prefix = strs[0]
    
    # 遍历数组中剩下的字符串
    for s in strs[1:]:
        # 逐渐缩短前缀，直到找到公共前缀
        while s[:len(prefix)] != prefix:
            prefix = prefix[:-1]
            if not prefix:
                return ""
    
    return prefix

# 测试用例
strs = ["flower", "flow", "flight"]
result = longest_common_prefix(strs)
print("Longest common prefix:", result)

时间复杂度：O(S)，其中 S 是数组中所有字符串的字符总数。在最坏情况下，算法需要逐个字符比较每个字符串的前缀。
空间复杂度：O(1)，除了输入数据外，额外使用的空间主要用于存储前缀。

关于这点我就说的很差，时间空间复杂度说的完全不对，我还以为是$O(mn)$， g

第二个是找出数组中所有可以使得数字和为target的组合，每个元素只能出现一次；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
def combination_sum(nums, target):
    # 先对数组排序，这样可以更容易地进行剪枝操作
    nums.sort()
    result = []

    # 定义回溯函数
    def backtrack(start, path, remaining_target):
        # 当剩余的target为0时，说明我们找到了一个有效的组合
        if remaining_target == 0:
            result.append(path[:])  # 将当前路径加入结果中
            return
        
        # 遍历从当前索引开始的每个数字
        for i in range(start, len(nums)):
            # 如果当前数字大于剩余的target，则无需继续搜索
            if nums[i] > remaining_target:
                break
            
            # 为了避免重复的组合，我们跳过相同的数字
            if i > start and nums[i] == nums[i - 1]:
                continue

            # 选择当前数字，继续递归搜索
            path.append(nums[i])
            # 递归，i + 1表示每个元素只能使用一次
            backtrack(i + 1, path, remaining_target - nums[i])
            # 回溯，撤销选择
            path.pop()

    # 调用回溯函数
    backtrack(0, [], target)
    return result

# 测试示例
nums = [10, 1, 2, 7, 6, 1, 5]
target = 8
combinations = combination_sum(nums, target)
print(combinations)

时间复杂度是指数级的 $O(2^n)$，属于递归经典的时间复杂度了，我这里说成了$O(N^2)$， 明显的直接g了， 这里的空间复杂度好像不太好算，应该是$O(k*2^n + n)$， k 是每个组合的平均长度， n是数组的长度。

第三题是一个链表数组，其中每个已经按照升序排列，合并成一个升序链表。写完后说时间和空间复杂度，这块没说清楚，对于第三题，问我为什么用堆，有什么优势，堆的几种基本操作的时间复杂度是多少。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
import heapq

# 定义链表节点的类
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def merge_k_sorted_lists(lists):
    # 创建一个最小堆
    heap = []
    
    # 将每个链表的头节点加入最小堆
    for i, lst in enumerate(lists):
        if lst:
            heapq.heappush(heap, (lst.val, i, lst))
    
    # 哨兵节点，用于构建最终的合并链表
    dummy = ListNode()
    current = dummy
    
    # 进行堆的操作，直到堆为空
    while heap:
        # 弹出堆中的最小值
        val, i, node = heapq.heappop(heap)
        
        # 将弹出的节点连接到最终结果链表中
        current.next = node
        current = current.next
        
        # 如果弹出的节点还有后续节点，将它的后续节点加入堆中
        if node.next:
            heapq.heappush(heap, (node.next.val, i, node.next))
    
    # 返回合并后的链表
    return dummy.next

# 测试用例
# 构建几个升序链表
list1 = ListNode(1, ListNode(4, ListNode(5)))
list2 = ListNode(1, ListNode(3, ListNode(4)))
list3 = ListNode(2, ListNode(6))

lists = [list1, list2, list3]

# 合并链表
merged_list = merge_k_sorted_lists(lists)

# 输出合并后的链表
while merged_list:
    print(merged_list.val, end=" -> ")
    merged_list = merged_list.next
print("None")

第三题这个不算特别难的，感觉比第二题还好一点，但是对于堆的相关概念说的不是很清楚，这个时间复杂度是$O(Nlogk)$，N是所有链表的节点总数，k是链表的个数，空间复杂度是$O(k)$，k是链表的个数。

然后让我讲下transformer结构，大致说了下，然后问transformer相比RNN有什么优势。这块实习的时候淘天就问过这个问题，当时说的模糊，思路不是很清晰，现在秋招了这块也没怎么看过，仍然说的不是很清楚，八股还是要背的，这种基础知识都说不好的肯定不行。

GPT总结了一些：

  1. 并行计算能力
    RNN：RNN 是一种序列模型，必须按时间步依次处理输入数据。也就是说，第 t 时刻的输出依赖于第 t-1 时刻的计算结果，因此不能并行化处理序列中的元素，这导致训练时间较长。
    Transformer：Transformer 利用自注意力机制（Self-Attention），使得每个输入位置的处理可以与其他位置的元素并行进行。这意味着 Transformer 能够在同一时间处理整个输入序列，从而大大加快了训练和推理速度。这种并行化特性使 Transformer 非常适合在 GPU 上运行，尤其对于长序列，训练速度相较 RNN 显著提升。
  2. 捕捉长距离依赖关系的能力
    RNN：RNN 的主要缺点之一是难以有效捕捉长距离依赖关系。由于其每个时间步的状态依赖于上一个时间步的状态，随着序列的增长，长距离的依赖可能被遗忘（梯度消失问题）。虽然 LSTM 和 GRU 在一定程度上缓解了这个问题，但仍然存在限制。
    Transformer：通过自注意力机制，Transformer 可以直接建模序列中任意两个位置之间的依赖关系，无论这两个位置相隔多远。这意味着 Transformer 在处理长序列时，能够高效且准确地捕捉长距离的依赖关系，而不会像 RNN 那样受到序列长度的限制。
  3. 消除递归结构，提升效率
    RNN：RNN 的递归结构需要依次处理序列中的每个元素，这种顺序性导致模型无法并行执行，尤其在长序列任务中，RNN 的训练和推理效率较低。
    Transformer：Transformer 通过完全消除递归结构，取而代之的是基于全局自注意力机制的并行计算，这大大提升了计算效率。每个位置的输出只需通过矩阵运算来计算，无需逐个时间步依赖前一个输出，极大地提升了效率。
  4. 更好的记忆和上下文捕捉
    RNN：RNN 的记忆是通过隐状态（hidden state）来传递的，每一步的状态依赖于前一步的信息传递。这种方式在处理长序列时会因为过多的信息传递而产生信息损失，导致模型难以保留远距离的上下文信息。
    Transformer：Transformer 使用自注意力机制，使得每个词或元素能够直接与其他所有元素建立联系。这种全局视角能够让模型在同一层次上捕捉到整个输入序列的全局信息，从而更好地保留上下文信息。
  5. 避免梯度消失问题
    RNN：RNN 依赖于逐步传递的隐状态，训练时容易遇到梯度消失或梯度爆炸的问题，尤其是在处理长序列时，梯度的传播会变得非常困难。
    Transformer：Transformer 没有依赖于序列传递的隐状态，而是通过自注意力机制和前馈神经网络来计算输出。这样就避免了在长序列上梯度消失或爆炸的问题，训练更为稳定，尤其在长文本或长序列任务中表现尤为显著。
  6. 更强的表示能力
    RNN：RNN 只能通过顺序计算来处理序列信息，这种线性的计算方式在处理复杂序列依赖时可能有局限。
    Transformer：通过多头自注意力机制（Multi-Head Attention），Transformer 可以从多个子空间同时处理信息，每个注意力头关注不同的信息模式，增强了模型的表示能力。多头自注意力机制允许模型同时关注输入序列中的不同部分，获取不同层次的特征。
  7. 适应性更强的输入表示
    RNN：RNN 的输入表示是通过序列顺序传递的，缺乏对输入元素之间关系的灵活表示。
    Transformer：Transformer 通过位置编码（Positional Encoding）来为序列中的每个位置引入位置信息。这种设计使得 Transformer 在处理文本等有序数据时，不会像 RNN 一样依赖于输入的顺序，还可以灵活适应各种输入长度和结构。
  8. 更容易并行扩展
    RNN：RNN 的递归结构天然不适合并行处理，尤其在训练非常深层的 RNN 模型时，计算资源的利用效率较低。
    Transformer：Transformer 的并行性和层级结构使其更容易扩展到大规模数据和模型，特别适合深层模型的并行计算。因为没有递归关系，Transformer 可以利用 GPU 进行大规模的并行计算，大幅提升训练效率和处理能力。
  9. 更适合预训练和迁移学习
    RNN：尽管 RNN 可以在特定任务上进行预训练，但其能力有限，尤其在处理大规模数据和迁移学习时，效果不如 Transformer。
    Transformer：Transformer 的架构非常适合大规模预训练模型，如 BERT、GPT 系列。这些模型通过在大规模数据上进行无监督预训练，能够很好地迁移到各种下游任务中，并且预训练的表示可以用于不同领域的任务，大大提高了模型的泛化能力和迁移学习能力。

之后是问简历上的实习经历，大致问了下，讲了背景，然后说具体是做了哪方面的工作，经典的一个问题就是，这个任务用大模型做有什么优势，这块我说我就是预研的一个探索，用大模型端到端的做这件事，实际上需要的数据什么的还是用的传统方法获得的，这块其实这样说还是不太好。另外涉及具体的工作，他们这边好像也是有做类似的东西，但是我也没讲的很出彩，然后中间问到了一个问题，我听的不是很明白，面试官就没什么兴趣了，我这块还没说完然后差不多就一个小时了，就让反问，然后就结束了。

面完就感觉不行了，过一会去看就挂了，淘天还是这么喜欢让手撕代码，这块还是要准备下。总之投实习的时候就淘天面的最差，现在秋招了，淘天还是面的最差的，问题还是有很多，面完要复盘总结经验。