Question 1

Google Drive Folder Hierarchy Sync

In the Google Drive architecture, a folder hierarchy is maintained where folders can be nested within one another, folders 1 to n. Each folder has a specific access level, represented by an integer.

A hierarchy is considered "Synced" when the absolute difference between the access levels of any two directly connected folders, a parent and its child, is at most 1.

Due to a recent update, some folders have had their access levels changed. To maintain security integrity and ensure the hierarchy is "Synced", you must increase the access levels of other folders.

Your goal is to find the minimum total increase in access levels required to make the entire folder hierarchy "Synced".

Note: You can only increase access levels; you cannot decrease them.

Example

Consider the following hierarchy tree:

The optimal way to sync it is:

• Increase 2 access levels of folder 3
• Increase 1 access level of folder 2
• Increase 3 access levels of folder 1

After these additions, the hierarchy tree becomes synced, and the minimum number of access level increase required is:

2 + 1 + 3 = 6

Function Description

Complete the function findMinIncrease in the editor with the following parameters:

int tree_nodes: the total number of folders in the hierarchy tree
int tree_from[tree_nodes - 1]: one end of each edge
int tree_to[tree_nodes - 1]: the other end of each edge
int access_levels[tree_nodes]: the access level of each folder

Returns

long: the minimum number of access level increase required to sync the hierarchy tree

Constraints

1 ≤ tree_nodes ≤ 2 * 10^5
0 ≤ access_levels[i] ≤ 10^9

Sample Case 0

Sample Input For Custom Testing

STDIN        FUNCTION
-----        --------
5 4      ->  tree_nodes = 5, m = 4
1 2      ->  tree_from = [1, 2, 2, 3], tree_to = [2, 3, 4, 5]
2 3
2 4
3 5
5        ->  access_levels[] size tree_nodes = 5
1        ->  access_levels[] = [1, 5, 7, 8, 3]
5
7
8
3

Sample Output

10

Explanation

Following are the optimal changes that will make the given hierarchy tree synced using minimum increase of access levels:

• Increase 2 access levels for folder 2
• Increase 5 access levels for folder 1
• Increase 3 access levels for folder 5

After performing the above 3 operations, the hierarchy tree is synced. Access levels increased:

2 + 5 + 3 = 10

Question 2

Google Docs Mobile Feature Rollout

Google Docs rolls out new mobile features gradually. A feature can only be enabled for a user if:

• The user meets basic eligibility requirements such as supported country and minimum OS version.
• All required feature dependencies are satisfied.

Some features depend on other features. A feature must not be enabled unless all of its dependencies are enabled first, either because they were already enabled or because they are also being enabled in the same rollout request.

The current rollout script is buggy. It enables features for ineligible users and ignores dependency constraints.

Your task is to fix this behavior.

For each user and each requested feature, determine whether the feature should be enabled.

For every decision, return a clear and correct reason when a feature cannot be enabled.

Inputs

Feature dependency definitions

File:

data/features.txt

Each line defines a feature and its dependencies.

Format:

A -> B means feature A depends on feature B
A -> B,C means feature A depends on features B and C
D means feature D has no dependencies

Dependencies are strict. All listed dependencies must be satisfied.

Users to evaluate

Input file:

data/users.jsonl

Format:

one JSON object per line

Each user record includes:

• User identifiers and platform details
• A list of features already enabled for the user
• A list of features requested in the current rollout

Example:

{"user_id":"u1","country":"US","platform":"ANDROID","android_version":12,"enabled_features":["C","D"],"feature_requests":["A","B"]}
{"user_id":"u2","country":"IN","platform":"ANDROID","android_version":12,"enabled_features":[],"feature_requests":["B"]}
{"user_id":"u3","country":"FR","platform":"IOS","ios_version":16,"enabled_features":["C"],"feature_requests":["A"]}

Output

File:

data/results.jsonl

Output one JSON object per input user, in the same order.

Each output object must include:

• user_id
• results: an array with one entry per requested feature

Output rules:

If a feature is enabled, return:

{"feature":"<name>","enabled":true}

If a feature is disabled, include a reason field:

{"feature":"<name>","enabled":false,"reason":"<REASON_CODE>"}

Example:

{"user_id":"u1","results":[{"feature":"A","enabled":false,"reason":"DEPENDENCY_NOT_ENABLED:B"}]}

Decision Logic and Evaluation Order

Feature evaluation must follow the rules below in strict order.

Once a rule blocks a feature, no further checks should be applied.

Step 1: Basic user eligibility

These checks apply to all requested features.

Supported countries

Allowed countries:

US
IN
ES

If the user’s country is not supported:

Reason: COUNTRY_NOT_SUPPORTED

Minimum OS version

For Android:

• Minimum supported version is Android 10
• If not met, reason:

ANDROID_TOO_OLD

For iOS:

• Minimum supported version is iOS 15
• If not met, reason:

IOS_TOO_OLD

If both country and OS checks fail:

Reason: COUNTRY_AND_OS_NOT_SUPPORTED

Only if all eligibility checks pass, should dependency evaluation begin.

Step 2: Feature dependency checks

A requested feature can be enabled only if all of its dependencies satisfy one of the following:

• The dependency is already present in enabled_features
• The dependency is also present in feature_requests and can be enabled in the same evaluation batch

Important constraints:

• The system must not automatically enable dependencies that were not explicitly requested.
• Dependency checks must be recursive.
• Dependencies must be enabled in the correct order.

If a required dependency is not enabled:

• Disable the feature
• Reason format:

DEPENDENCY_NOT_ENABLED:<dependency_name>

• Report the first missing dependency encountered.

Example:

• If A depends on B and B depends on C:
  • C must be enabled before B
  • B must be enabled before A

Cycle handling

If the dependency graph contains a cycle, the affected feature can never be enabled.

Example:

• A depends on B
• B depends on A

In this case:

• Disable the feature
• Reason:

CYCLE_DETECTED

我们也有代面试，面试辅助，OA代写等服务助您早日上岸~