Home OA回顾 之 CPU进程分配问题
Post
Cancel

OA回顾 之 CPU进程分配问题

Posted Jun 24, 2024   PageView:
By Ziheng Chen
11 min read

关于OA回顾

这个系列旨在记录参加过的一些日本互联网公司的OA原题。考虑到私密性等问题，文中只会记录题目的内容而不会指明该题来自于哪一家公司。

题目概述

  • 现有一个双核处理器，以及一系列进程，各个进程在任意一个处理器上所需花费的运算时间被依次保存在数组times中。
  • 此外，存在一个锁存器（latch），其初始状态下位于处理器0中（假设两个处理器编号分别为0和1）。
  • 该锁存器的工作机制如下：
    • 将待处理序列中最靠前的进程分配给处理器0或1
      • 如果分配给当前锁存器所处的处理器，则锁存器跳转至另一处理器。
      • 反之，则继续保持在原地不跳转。
    • 进程分配的决策依据为：在所有进程分配完成后，当前所处的处理器的总运算时长能够最大化。
  • 求：分配完成后两个处理器各自的总运算时长。

限制条件：

  • 1 <= times.length <= 10 ^ 5

例:

1
2
3
4
5

Input: times = [10, 21, 10, 21, 10]
Output: [41, 31]

Input: times = [1, 2, 3, 4]
Output: [5, 5]

解释一下这里示例中给出的结果是怎么得到的。对于第一个示例，初始状态下锁存器位于处理器0中，此时它有两个选择

  • 将第一个进程分配给处理器1，锁存器自身位置不变
  • 将第一个进程分配给处理器0，锁存器跳转至处理器1

锁存器位置发生转变可以理解为一种将选择的主动权交出去的行为。对于这里的情形，如果在第一个进程就将主动权交给对面，那么后续存在的时长21的进程就不一定能够被分配到当前的处理器了。按照这个主动权交替的思想，该进程序列的分配结果如下表所示：

进程进程时长锁存器位置处理器0处理器1下一轮锁存器位置
01000100
12102101
21011001
32110210
41001001
时长总和  4131 

思路 & 代码实现

这个问题如果按照正常的顺序去思考会感觉相当复杂，因为每一步选择都会衍生出更多的可能，并且牵扯到锁存器处于不同视角下的相互博弈。因此，从最后的结果进行反推或许是一个比较可行的方案。对于这个问题，使用反推的好处在于，最后一步的选择是非常明晰的，锁存器只需要将这最后一个进程分配给当前所在的处理器即可。

在此基础上我们可以进行对上一步的反推。在每一步选择中最多只有两种可能：进程被分配给处理器0或处理器1。因此只需要结合当前锁存器所处的位置以及做出两种选择后的优劣，便可以得到当前情况下的最优解。

解法一：记忆化搜索

创建一个用于记录每一步选择后各个处理器总运算时长的递归函数dfs()，给它传递两个参数i和latch。i表示当前处理的进程的序列号，也即times这个数组的索引；latch表示当前锁存器的位置，也即0或1。函数返回两个结果，表示的是当锁存器位于处理器latch，且处理完第i个进程后两个处理器各自的总运算时长。此时我们可以写出最后一步时的结果：

1
2
3
4
5
6

def solution(times):
    n = len(times)

    def dfs(i, latch):
        if i == n - 1:
            return (times[i], 0) if latch == 0 else (0, times[i])

当所处进程不是最后一个时，可以通过递归调用函数获取下一个进程分配完成后的反推结果。注意该结果有两种状态，也即锁存器的两种可能的位置。

1
2

time00, time01 = dfs(i+1, 0)
time10, time11 = dfs(i+1, 1)

此处time01表示，锁存器位于处理器0并完成分配后，处理器1的总运算时长。剩下三个变量名同理。根据这些结果，进行当前这一步的反推，同样也是分为两种情况：

  • 当前锁存器位于处理器0时

    比较两种分配选择的优劣。

    • 将进程分配给当前所在的处理器，此时两个处理器的总运算时长分别为time10 + times[i]，time11。（注：因为在当前这一步进程被分配给了处理器0，因此锁存器在下一个状态时已经跳转至处理器1，所以要和dfs(i+1, 1)的结果进行加和）
    • 将进程分配给另一个处理器，此时两个处理器的总运算时长分别为time00，time01 + times[i]。

    比较两种情况下处理器0的总运算时长。（因为此时假设锁存器位于处理器0，一切为了它的运算时长最大化）

    1
2
3
4

      if latch == 0:
      if time10 + times[i] > time00:
          return time10 + times[i], time11
      return time00, time01 + times[i]

  • 当前锁存器位于处理器1时

    只需注意优化视角位于处理器1，其他逻辑相同。

    1
2
3
4

      if latch == 1:
      if time01 + times[i] > time11:
          return time00, time01 + times[i]
      return time10 + times[i], time11

至此，递归函数构建完毕。题目要求的结果为初始状态dfs(0, 0)下的运算时长，同时为了减少重复计算，可以使用cache装饰器添加一个记忆化模块。综合下来，完整的解法为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

from functools import cache

def solution(times):
    n = len(times)

    @cache
    def dfs(i, latch):
        if i == n - 1:
            return (times[i], 0) if latch == 0 else (0, times[i])

        time00, time01 = dfs(i+1, 0)
        time10, time11 = dfs(i+1, 1) 
        
        if latch == 0:
            if time10 + times[i] > time00:
                return time10 + times[i], time11
            return time00, time01 + times[i]
        else:
            if time_01 + times[i] > time11:
                return time00, time01 + times[i]
            return time_10 + times[i], time11

    return dfs(0, 0)

由于每个dfs函数内都需要递归调用自身两次，所以整体时间复杂度为 $O(2^n)$，还需要进行进一步优化。

解法二：动态规划

基于上述思路，每一步的计算事实上只会存在两种状态，再加上反推计算不会影响已经完成的计算结果，因此只需要用一个数组保存已有的状态就可以避免大量的重复计算了。这里建立一个DP数组dp，参照dfs函数中的参数设置，进行如下的状态定义：

  • dp[i][j][k]：处理的进程索引为i，锁存器位于处理器j时，处理器k的最大运算时长。其中j和k的取值均为0或1。

完成这一步后，剩余的逻辑与解法一完全相同。大致流程如下：

  • 初始化
    1
2
3
4

      n = len(times)
  dp = [[[(0, 0), (0, 0)]] for _ in range(n)]
  dp[-1][0] = time[-1], 0
  dp[-1][1] = 0, time[-1]
  • 反推计算
    1
2
3
4
5
6
7
8
9
10
11

      for i in range(n-2, -1, -1):
        
      if dp[i+1][1][0] + times[i] > dp[i+1][0][0]:
          dp[i][0] = dp[i+1][1][0] + times[i], dp[i+1][1][1]
      else:
          dp[i][0] = dp[i+1][0][0], dp[i+1][0][1] + times[i]
        
      if dp[i+1][0][1] + times[i] > dp[i+1][1][1]:
          dp[i][1] = dp[i+1][0][0], dp[i+1][0][1] + times[i]
      else:
          dp[i][1] = dp[i+1][1][0] + times[i], dp[i+1][1][1]

最终完整代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

def solution(times):
    n = len(times)
    dp = [[[(0, 0), (0, 0)]] for _ in range(n)]
    dp[-1][0] = time[-1], 0
    dp[-1][1] = 0, time[-1]

    for i in range(n-2, -1, -1):
        if dp[i+1][1][0] + times[i] > dp[i+1][0][0]:
            dp[i][0] = dp[i+1][1][0] + times[i], dp[i+1][1][1]
        else:
            dp[i][0] = dp[i+1][0][0], dp[i+1][0][1] + times[i]
        
        if dp[i+1][0][1] + times[i] > dp[i+1][1][1]:
            dp[i][1] = dp[i+1][0][0], dp[i+1][0][1] + times[i]
        else:
            dp[i][1] = dp[i+1][1][0] + times[i], dp[i+1][1][1]

    return dp[0][0]

经过优化，该解法的整体时间复杂度来到了 $O(n)$ 。

Study notes, OA
online assessment recursion dynamic programming
This post is licensed under CC BY 4.0 by the author.
Recently Updated
Contents

Windows系统下Docker的环境配置

OA回顾 之 去重后的最大字典序子序列