citadel 2025 ng oa 题目

更多资源与服务

想要了解更多编程面试技巧，或者需要专业的面试辅导、OA代做、简历润色等服务？我们提供全方位的求职面试支持，帮助您在大厂面试真题、系统设计面试和算法面试中脱颖而出，轻松拿到心仪的 offer！无论您是留学生、刚踏入职场的新人，还是需要代码优化建议的开发者，我们的团队由ACM奖牌得主、大厂资深 TLM 及经验丰富的行业老兵组成，确保为您提供最专业的指导。

扫描下方二维码，添加我们的微信，获取更多服务：

关键词：

• 面试代面
• 代码代写
• OA代做
• 面试技巧
• 面试经验分享
• 职业规划
• 编程练习

让我们帮助您在技术面试中脱颖而出，实现职业上的飞跃！

问题 2：服务器稳定子段的计算

解题思路：

这道题主要考察对区间求和的理解和滑动窗口的应用。需要找出符合条件的稳定子段，关键在于如何高效地计算多个区间的端点与内部元素的关系。

1. 遍历所有可能的子段：
   • 长度至少为 3 的子段，所以需要尝试不同的起始和结束位置 (l, r)。
2. 计算内区间和：
   • 内部区间为 [l+1, r-1]，可以使用前缀和来优化计算。
3. 前缀和的优化：
   • 建立一个前缀和数组 prefix_sum，其中 prefix_sum[i] 表示从第 0 个元素到第 i 个元素的和。
   • 内部区间的和可以通过公式计算：prefix_sum[r-1] - prefix_sum[l]。
4. 验证条件：
   • 对于每个子段 [l, r]，检查是否满足 capacity[l] == capacity[r] == sum(l+1, r-1)。

代码实现：

def count_stable_subsegments(capacity):
    n = len(capacity)
    prefix_sum = [0] * (n + 1)

    # 构建前缀和数组
    for i in range(n):
        prefix_sum[i + 1] = prefix_sum[i] + capacity[i]

    stable_count = 0

    # 遍历所有可能的子段，长度至少为 3
    for l in range(n):
        for r in range(l + 2, n):
            interior_sum = prefix_sum[r] - prefix_sum[l + 1]
            if capacity[l] == capacity[r] == interior_sum:
                stable_count += 1

    return stable_count

# 测试示例
capacity = [9, 3, 3, 3, 9]
print(count_stable_subsegments(capacity))  # 输出 2

问题 3：社交网络中的好友推荐

解题思路：

这道题主要考察图算法的应用，特别是如何在社交网络中进行好友推荐。关键是找出两个用户之间的公共好友数量，并基于该数量进行推荐。

1. 输入数据的处理：

   • 我们有 n 个用户和 m 对朋友关系。通过这些关系构建每个用户的好友列表。
   • 使用一个邻接表（如字典）来存储每个用户的好友集合。

2. 查找最大公共好友：

   • 对于每个用户 x，需要检查与其他不在其好友列表中的用户之间的公共好友数量。
   • 使用集合的交集操作高效地计算公共好友。

3. 选择推荐的好友：

   • 如果有多个候选好友拥有相同数量的公共好友，选择编号最小的那个。
   • 如果没有可推荐的好友，返回 -1。

4. 时间复杂度优化：

   • 构建邻接表的时间复杂度为 O(m)。
   • 计算公共好友时使用集合交集操作，可将复杂度降低到 O(1) 对每对用户检查。

代码实现：

from collections import defaultdict

def get_recommended_friends(n, friendships):
    # 构建邻接表
    friends = defaultdict(set)
    for u, v in friendships:
        friends[u].add(v)
        friends[v].add(u)

    recommendations = [-1] * n  # 初始化推荐结果

    # 遍历每个用户
    for x in range(n):
        max_common = -1  # 记录最大公共好友数量
        recommended = -1  # 推荐好友编号

        # 检查所有可能的好友推荐
        for y in range(n):
            if y != x and y not in friends[x]:
                # 计算公共好友数量
                common_friends = len(friends[x] & friends[y])

                # 更新推荐好友
                if common_friends > max_common or (common_friends == max_common and y < recommended):
                    max_common = common_friends
                    recommended = y

        recommendations[x] = recommended  # 存储推荐结果

    return recommendations

# 测试示例
n = 5
friendships = [[0, 1], [0, 2], [1, 3], [2, 3], [3, 4]]
print(get_recommended_friends(n, friendships))  # 输出: [3, 2, 1, 0, 1]