字节现在还考原题吗？

大家好，我是吴师兄。

继续每天陪大家练习一场大厂算法题，拿下秋招！

2024 年的大厂真题可以在我的网站上进行练习。

网站地址： https://oj.algomooc.com/

关注吴师兄，算法学习好轻松

最近讲了几场秋招的算法笔试题，比如 华为0911秋招笔试 、 网易雷火0911秋招笔试 、 中兴0910秋招笔试 ，大家听下来的整体感觉是题目难度属于中等偏下，但依然考察了算法基础、数据结构应用和编程能力，而且越来越考察 阅读理解 的能力，笔试题目的设计越来越注重实际应用场景中的问题解决能力，并非像 LeetCode 那样简洁明了的用一两句话来说明。

举个例子，比如 LeetCode 第 743 号问题： 网络延迟时间 ，题目描述非常简单明了，特别是还有关键词 有向 ，了解图算法相关的知识后能马上从图相关的角度去思考问题。

但是在真正笔试过程中，题目都是结合具体场景去描述，比如华为的一道算法题，思路和代码和 网络延迟时间 几乎一模一样，

所以这里建议大家不用只去做 LeetCode 算法题，得多多阅读秋招真题， 就连字节都开始频繁的考一些变种题，直接考 LeetCode 原题的概率非常非常低了。

继续回到我们公众号的主题，今天分享的是 网易雷火0911秋招笔试 。

1、配置表差异比对

在游戏开发过程中，配置表用于存储各种游戏玩法相关的数值数据。每当游戏版本更新时，策划人员会根据游戏玩法的变化对配置表进行更新。为了确保更新的正确性并防止人为错误，我们需要一个程序来比对配置表的新旧版本，并标识出其中的差异。

输入

程序的输入包括四个参数，分别为旧表的主键列表、旧表的值列表、新表的主键列表和新表的值列表。

输出

输出是一个包含三个列表的列表：

• 第一个列表包含新增行的ID。
• 第二个列表包含修改行的ID。
• 第三个列表包含删除行的ID。

样例

输入：
[1,2],["nowcoder","best"],[1,2],["nowcoder","great"]
输出：
[[],[2],[]]
提示：
本样例中，没有数据新增，故新增行ID列表为空。ID为2的数据行发生了修改，所以修改行ID列表包含[2]。没有数据删除，故删除行ID列表为空。

解题思路

本题要求我们比较两个版本的配置表，找出新增、修改、和删除的记录。使用字典（哈希表）是一个很好的选择，因为可以通过主键快速定位值，并进行比较。

1. 新增行 ：在新表中存在，但旧表中不存在的行。
2. 修改行 ：主键相同，但值不同的行。
3. 删除行 ：在旧表中存在，但新表中不存在的行。

具体操作

• 使用字典分别存储旧表和新表的主键与对应的值。
• 通过遍历旧表字典，检查每个主键是否在新表中，若不存在则记录为删除行，若存在但值不同则记录为修改行。
• 新增行可以通过找出新表主键集中不在旧表中的主键。

参考代码

# 关注吴师兄，算法学习好轻松
from typing import List

class Solution:
    def compare_configs(self, old_ids: List[int], old_values: List[str], new_ids: List[int], new_values: List[str]) -> List[List[int]]:
        # 将旧表的主键和对应的值存储在字典old中
        old = {k: v for k, v in zip(old_ids, old_values)}
        # 将新表的主键和对应的值存储在字典new中
        new = {k: v for k, v in zip(new_ids, new_values)}
        
        # 初始化结果列表，包含新增、修改、删除的ID
        ans = [[], [], []]
        
        # 遍历旧表的所有主键和值
        for k, v in old.items():
            # 如果主键k不在新表中，说明该行已被删除
            if k not in new:
                ans[2].append(k)  # 记录删除行的ID
            # 如果主键k在新表中，但对应的值不同，说明该行被修改
            elif v != new[k]:
                ans[1].append(k)  # 记录修改行的ID
        
        # 通过差集找出新增的主键，新增的主键在新表中，但不在旧表中
        ans[0] = sorted(set(new.keys()) - set(old.keys()))  # 记录新增行的ID
        
        # 返回所有结果列表，按升序排序
        return [sorted(v) for v in ans]

2、像素直线涂色挑战

在一个无限大的像素平面上，每个像素点由其XY坐标唯一确定，坐标原点为(0,0)，向右和向上递增。若从原点(0,0)到目标像素(X,Y)绘制一条直线，且此直线与某像素的边界相交，则该像素会被涂色。现在给定目标像素坐标(X, Y)，计算有多少个像素会被这条直线涂上色。

输入

输入一行，包含两个整数X和Y，表示目标像素的坐标。

输出

输出一个整数，表示从(0,0)到(X,Y)的直线会涂色多少个像素。

样例

输入：
3 2
输出：
6

输入：
2 2
输出：
3

解题思路

从(0, 0)到(X, Y)的直线可能会经过多个像素的边界。该问题的核心在于计算这条线经过多少个像素。

通过数学公式可以推导出，经过的像素数量是 X + Y - gcd(X, Y) ，其中 gcd 是X和Y的最大公约数。

参考代码

# 关注吴师兄，算法学习好轻松
from math import gcd  # 导入gcd函数，计算最大公约数

# 读取输入的两个整数，表示目标像素的坐标X和Y
x, y = map(int, input().split())

# 由于题目要求包括坐标(X, Y)，将X和Y加1
x += 1  # X加1，因为需要包含(X, Y)这个点
y += 1  # Y加1

# 使用公式计算被涂色的像素数量，并输出结果
# 被涂色的像素数量为X + Y - gcd(X, Y)，其中gcd是X和Y的最大公约数
print(x + y - gcd(x, y))

3、高效排序挑战

给定一组数据，每条数据包括一个名称和两个排序关键字 sort1 和 sort2 。需要设计一个算法，根据指定的排序字段和顺序来排序这些数据。

这些数据如下：

[
    {"name": "ace", "sort1": 8, "sort2": 4},
    {"name": "bre", "sort1": 2, "sort2": 3},
    {"name": "cat", "sort1": 5, "sort2": 2},
    {"name": "dog", "sort1": 1, "sort2": 1}
]

输入

输入包括两部分：排序字段 orderBy 和排序类型 orderType （升序"asc"或降序"desc"）。

输出

输出根据指定排序条件排序后的数据名称。

样例

输入：
sort1 asc
输出：
dog 
bre 
cat 
ace
提示：
按照sort1升序排序后，数据顺序为：dog (sort1=1), bre (sort1=2), cat (sort1=5), ace (sort1=8)。

解题思路