CS-OA cs-vo Faang

[TikTok] AMS GradAssessment 2024 Start – 9

本周的Tik Tok的OA 2,3题基本送分,第二题选A,第一题比较难,下面分析一下较难的几道题

1. Resource Allocation Matrix

A supercomputing facility uses a highly efficient operating system for various intensive computations ranging from weather prediction to drug discovery. The system is designed to handle many tasks that require a fixed set of resources - R1, R2, R3, and R4. A recent increase in computational demand led to a deadlock in the system. The current state of the system's resource allocation matrix is shown:

ProcessAllocation R1Allocation R2Allocation R3Allocation R4Max R1Max R2Max R3Max R4

The total number of instances of each resource type is 5.

Based on the information provided, what is the state of the system?


  • The system is in a safe state and can satisfy requests from all processes.
  • The system is in an unsafe state and cannot satisfy requests from all processes.
  • The system is in a deadlock state with no possibility of progress.
  • The system's state cannot be determined from the information given.

分析: 从所给的资源分配矩阵中,我们需要确定系统是否处于安全状态。为此,我们首先计算系统中每种资源的剩余数量,然后检查是否所有进程的最大需求都能得到满足。




4.Channel Rating

Background: The data analysts at ByteDance are analysing some popular channels on Xigua Video. A channel has a collection of n videos, where the number of views of the i-th video is represented by the array element views[i].

Algorithm Description: The data analysts have built an algorithm that calculates the rating of the channel in the following way:

  • The rating of the channel is the number of special subarrays of the array views of length at least 3 such that the bitwise XOR of the first and last elements of the subarray is equal to the bitwise XOR of all the other elements within the subarray.

Note: A subarray is a contiguous sequence of elements within an array.

Task: Given a channel with n videos and an array views, find the rating assigned to the channel. Since the answer can be large, return it modulo (10^9 + 7).

Example: Given n = 4 and views = [0, 3, 6, 5]. All the subarrays of length greater than or equal to 3 are explained below:

SubarrayXOR of BorderXOR of Non-BorderIs Special?
[0, 3, 6](0 xor 6) = 63No
[3, 6, 5](3 xor 5) = 66Yes
[0, 3, 6, 5](0 xor 5) = 5(3 xor 6) = 5Yes

Hence, the rating of the channel is 2.

分析: 题目的主要目的是找到一个特殊子序列的总数,该子序列满足以下条件:子序列的第一个和最后一个元素的XOR与子序列中其他元素的XOR之和相等。


  1. 对于每一个可能的子序列,计算第一个和最后一个元素的XOR。
  2. 同时,也计算该子序列中其他元素的XOR之和。
  3. 比较两个XOR的结果。如果它们相等,则该子序列是特殊的。



Leave a Reply

Your email address will not be published. Required fields are marked *