大厂offer？拿来吧你！网易有道笔试编程题特辑 – 有道技术沙龙博客

联系我们：有道技术团队助手：ydtech01 / 邮箱：ydtech@rd.netease.com 欢迎应届生同学们

来到2022年校招运动会

现在迎面向你们走来的

是网易有道代表队！

（传送门：http://hr.youdao.com/ ）

他们食堂好吃

他们从不内卷

今天，他们还带来了

10道笔试编程题

据说全做对的同学

都顺利地拿到了 offer！

同学们，请开始你们的 ~~bug~~

啊不

表演吧！

一、热身运动

1.1 找到重复数字

给定一个包含 n+1 个整数的数组 nums ，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设 nums 只有一个重复的整数，找出这个重复的数。

难度：一星
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 256MB，其他语言512MB
64bit IO Format: %lld

样例： 输入：[1,3,4,2,2] 返回：2

1.2 三角形面积

输入三个点的坐标，输出三个点组成的三角形的面积。（结果保留三位小数点并四舍五入）\

难度：一星
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 256MB，其他语言512MB
Special Judge, 64bit IO Format: %lld
知识点：计算几何

样例：

输入：12，-70，95，91，-72，35
输出：11119.500

二、伸展运动

2.1 分解自然数

一个自然数可以将它分解成若干个自然数相乘。现在给你一个指定的自然数n，请求出每种分解自然数之和的最小值是多少。

难度：二星
时间限制：C/C++ 5秒，其他语言10秒
空间限制：C/C++ 32MB，其他语言64M
64bit IO Format: %lld

样例：
输入：6 返回：5 说明：6分解为2 * 3，那么最小的和为2+3=5

2.2 恢复异常数

有一个一维整数数组 fuzzyArray，里面存储的是从 1 到 n 这 n 个数，不过是乱序存储；这时有一个位置的数字变成了 -1。请用最优的空间复杂度和时间复杂度求出这个异常数的位置和原来的值。\

难度：二星
时间限制：C/C++ 5秒，其他语言10秒
空间限制：C/C++ 256 MB，其他语言512 MB
64bit IO Format: %lld
知识点：测试开发、数组

样例：

输入： [2, -1, 3]
返回： [1,1]
说明： 异常数组原本应该是存储从 1 到 3 的数，不过是乱序的，但是实际数组是 [2, -1, 3]，说明数组 pos=1 的位置，原来的数字 1 变成了 -1，因此返回 [1, 1]

2.3 订单平均等待时间

有一个奶茶店，同一时间只能处理一个订单的制作，现有一个顾客订单列表 orders（二维数组），每个订单都包含两个元素：第一个元素表示订单到达的时间，orders 中订单按到达时间非递减顺序排列；第二个元素表示订单制作需要的时间；当顾客订单到达时，奶茶店一旦空闲就会开始制作该订单的奶茶。每一位顾客都会一直等待奶茶店完成他的订单。奶茶店会严格按照订单顺序处理订单。请你返回订单列表中所有顾客平均需要等待的时间。与标准答案误差在 10-5 范围以内，都视为正确。

难度：二星
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 256MB，其他语言512MB
Special Judge, 64bit IO Format: %lld
知识点：模拟

样例：

输入：[[1,2],[1,3],[4,3]]
返回： 4.00000
说明： 第一个订单在时刻1到达，奶茶店立即开始处理订单，在时刻3完成，第一位顾客需要等待的时间为 3-1=2；

第二个订单在时刻1到达，奶茶店正在处理第一个订单，第一个订单在时刻3完成并开始处理订单2，第二个订单在时刻6完成，第二位顾客需要等待的时间为 6-1=5；

第三个订单在时刻4到达，奶茶店正在处理第二个订单，第二个订单在时刻6完成并开始处理订单3，第三个订单在时刻9完成，第二位顾客需要等待的时间为 9-4=5；所以平均值为 (2+5+5)/3=4。

三、全身运动

3.1 数字与字母

给你一个仅包含数字和大写字母的字符数组，找到一个最长的子串，使得子串中包含相同个数的数字和字母。子串必须是原数组中连续的一部分。请你返回子串的长度，若没有这样的子串返回 0 。

难度：三星
时间限制：C/C++ 1 秒，其他语言 2 秒
空间限制：C/C++ 256 MB，其他语言512 MB
64bit IO Format: %lld
知识点：字符串处理

样例：

输入： [A,A,A]
返回： 0

3.2 木棍拼接

木工小王有一些长短不一的木棍，他想知道这些木棍能否拼接起来组成一个正方形。请写一个程序解决小王的疑惑。

说明： 1. 可将单根木棍作为正方形的一条边，也可将多根木棍拼接起来作为正方形的一条边。 2. 所有木棍必须使用，且每根木棍只能使用一次。

难度：三星
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32MB，其他语言64MB
64bit IO Format: %lld
知识点：dfs、剪枝

样例：

输入： [4，1，1，1]
返回： [false]
说明： 这四根木棍无法拼接成正方形

3.3 删除最短子数组使剩余数组有序

输入一个整数数组 array，请你删除一个子数组，使得 array 中剩下的元素是非递增的。子数组可以是原数组中连续的一个子序列，或者为空。请你返回这个最短的子数组的长度。

难度：三星
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 256MB，其他语言512MB
64bit IO Format: %lld
知识点：数组

样例：

输入： [5,4,3,7,8,2,1]
返回值： 2
说明： 删除的最短子数组是 [7,8]，长度是 2。剩余的元素为 [5,4,3,2,1]，为非递增。

四、跳跃运动

4.1 任务分配

在离线机器翻译系统中有时会一次接受到多个翻译句子的请求，这些句子的翻译时间可以按照长度预估为 jobs，jobs[i]表示第i个请求句子的翻译时间。系统会启动 k 个线程同时去处理这些翻译任务。为了减少响应时间，我们需要将这些翻译请求分配给不同的线程去处理，每个请求只能分配给一个线程，一个线程的处理时间为分配给它的所有请求句子翻译时间的和。系统的处理时间为所有线程翻译完分配任务的时间，你的目标是优化分配方式使得系统能尽快时间处理完所有请求。请计算出整个系统最短的处理时间。