Implement Checksums and Feature Rollout Evaluation
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
Complete the following two coding tasks in a 90-minute online assessment. An AI coding assistant may be available, but the submitted code must pass the provided unit tests.
## Task 1: Build an email verification string
Implement a function such as `buildVerificationString(email, verification, k)`.
You are given:
- `email`: a string containing only lowercase letters and the characters `:`, `/`, and `.`.
- `verification`: a non-empty string used as a lookup table.
- `k`: a positive integer chunk size.
Use the following character weights:
- `a = 1, b = 2, ..., z = 26`
- `: = 27`
- `/ = 28`
- `. = 29`
Process `email` from left to right in consecutive chunks of size `k`. The final chunk may contain fewer than `k` characters. For each chunk:
1. Compute its checksum as the sum of the weights of its characters.
2. Convert the checksum to an index using `checksum % verification.length`, with zero-based indexing.
3. Append `verification[index]` to the answer.
Return the concatenation of all selected verification characters.
## Task 2: Evaluate a feature rollout with dependencies
Implement or repair a feature rollout evaluator for deciding whether a user should receive a new feature.
You are given existing model classes similar to:
- `User`
- `country`
- `platform`, either `android` or `ios`
- `version`, an integer version for that platform
- `enabledFeatures`, the set of features already enabled for the user
- `FeatureRule`
- `allowedCountries`, a set of countries in which the feature may be enabled
- `minAndroidVersion`
- `minIosVersion`
- `ResultDecision`
- `enabled`: boolean
- `reason`: string explaining the decision
You are also given:
- `targetFeature`: the feature being evaluated.
- `rolloutFeatures`: the set of features being rolled out in this batch.
- A dependency text file describing feature dependencies.
- A parser skeleton and an `evaluate` function skeleton that contain bugs.
### Required evaluation order
For `targetFeature`, check the following in order:
1. Country eligibility.
- If the user's country is not allowed, the result must be `enabled = false` with a country-specific rejection reason.
2. Platform version eligibility.
- If the user is on Android, their version must be at least `minAndroidVersion`.
- If the user is on iOS, their version must be at least `minIosVersion`.
- If the platform/version check fails, return `enabled = false` with a platform-specific rejection reason.
3. Combined rejection.
- If both country and platform checks fail, return a special combined country-and-platform rejection reason, rather than returning only one of the two individual reasons.
4. Dependency checks.
- Dependency checks must happen only after the country and platform checks pass.
- If country or platform eligibility fails, do not inspect or evaluate dependencies.
Use the provided sets and helper data structures for allowed countries and supported platforms. Do not replace them with hard-coded values that may differ from the tests.
### Dependency file parsing
The dependency file contains one feature per line in a format such as:
`featureName: dependencyA, dependencyB, dependencyC`
Rules:
- Empty dependency lists are allowed.
- Whitespace around feature names and dependency names should be ignored.
- Multiple dependencies must be parsed as separate strings, not as one combined string.
For example, the line:
`checkout: login, payments`
must parse as:
`checkout -> [login, payments]`
not:
`checkout -> ["login, payments"]`.
### Dependency evaluation rules
A dependency is satisfied if either:
- It is already in `user.enabledFeatures`, or
- It is included in `rolloutFeatures` and all of its own dependencies can also be satisfied during this rollout batch.
A dependency is missing if it is neither already enabled nor present in `rolloutFeatures`. In that case, return `enabled = false` with a missing-dependency reason that identifies the missing feature.
Your implementation must handle at least the following cases:
1. A feature with exactly one dependency.
2. A feature whose dependency is also being rolled out in the same batch.
3. A simple two-feature cycle, such as `A -> B` and `B -> A`.
4. A feature that depends on another feature that is part of a cycle.
5. A longer cycle, such as `A -> B -> C -> D -> A`, while correctly identifying the first repeated feature in the current recursion path.
6. A longer cycle while listing every feature involved in the cycle in the rejection reason.
For a detected cycle, return `enabled = false` with a cycle reason such as:
`CYCLE: A -> B -> C -> D -> A`
where the listed features correspond to the cycle found in the current dependency traversal.
If all country, platform, and dependency checks pass, return `enabled = true` with a success reason such as `ENABLED`.
Quick Answer: This question evaluates string processing, checksum computation with modular indexing, parsing of dependency data, and business-logic evaluation for feature rollouts, including conditional eligibility checks and dependency resolution.
Part 1: Build an Email Verification String
Given an email-like string, a verification lookup string, and a chunk size k, build a verification string by scanning the email from left to right in chunks of size k.
Character weights are:
- 'a' to 'z' -> 1 to 26
- ':' -> 27
- '/' -> 28
- '.' -> 29
For each chunk:
1. Compute the checksum as the sum of the weights of its characters.
2. Compute index = checksum % len(verification).
3. Append verification[index] to the answer.
The last chunk may contain fewer than k characters. Return the concatenation of all chosen verification characters.
Constraints
- 0 <= len(email) <= 10^5
- 1 <= len(verification) <= 10^5
- 1 <= k <= 10^5
- email contains only lowercase letters and the characters ':', '/', '.'
Examples
Input: ('abcde', 'wxyz', 2)
Expected Output: 'zzx'
Explanation: Chunks are 'ab', 'cd', 'e'. Their checksums are 3, 7, 5. Mod 4 gives indices 3, 3, 1, so the answer is 'z' + 'z' + 'x'.
Input: ('a:/.', 'pqrs', 2)
Expected Output: 'pq'
Explanation: Chunks are 'a:' and '/.'. Weights are 1+27=28 and 28+29=57. Mod 4 gives 0 and 1.
Input: ('', 'abc', 3)
Expected Output: ''
Explanation: Edge case: an empty email has no chunks, so the result is an empty string.
Input: ('zzz', 'ab', 5)
Expected Output: 'a'
Explanation: Edge case: k is larger than the string length, so there is one chunk. Its checksum is 78, and 78 % 2 = 0.
Hints
- Create a helper that maps each allowed character to its weight.
- Process the string in steps of k using a loop like range(0, len(email), k).
Part 2: Evaluate a Feature Rollout with Dependencies
Implement a rollout evaluator for deciding whether a user should receive a target feature.
Your function receives flattened user and rule data instead of model classes.
Evaluation order for target_feature:
1. Country eligibility
2. Platform version eligibility
3. Combined rejection if both country and platform fail
4. Dependency checks only if both checks above pass
Country rules:
- If user_country is not in allowed_countries, reject.
Platform rules:
- If user_platform == 'android', then user_version must be at least min_android_version.
- If user_platform == 'ios', then user_version must be at least min_ios_version.
Return reasons exactly as follows:
- Success: 'ENABLED'
- Country-only failure: 'COUNTRY_NOT_ALLOWED: <country>'
- Android version failure: 'ANDROID_VERSION_TOO_LOW'
- iOS version failure: 'IOS_VERSION_TOO_LOW'
- Combined country + platform failure: 'COUNTRY_AND_PLATFORM_NOT_ALLOWED'
- Missing dependency: 'MISSING_DEPENDENCY: <feature>'
- Cycle: 'CYCLE: A -> B -> ... -> A'
Dependency input:
- dependency_lines is a list of strings.
- Each line has the form 'feature: dep1, dep2, dep3'.
- Empty dependency lists are allowed, for example 'login:'.
- Ignore surrounding whitespace around feature names and dependency names.
- Split multiple dependencies into separate names.
Dependency rules:
- A dependency is satisfied if it is already in enabled_features.
- Otherwise, it must appear in rollout_features and all of its own dependencies must also be satisfied.
- If a dependency is neither enabled nor in rollout_features, return a missing-dependency failure.
- If dependency traversal finds a cycle in the current recursion path, return the cycle reason using the first repeated feature in that path.
Important: Do not inspect dependencies at all if country or platform eligibility fails.
Constraints
- 1 <= len(target_feature) <= 100
- user_platform is either 'android' or 'ios'
- 0 <= user_version <= 10^9
- 0 <= len(enabled_features), len(allowed_countries), len(rollout_features) <= 10^4
- 0 <= len(dependency_lines) <= 10^4
- Each dependency line contains at most one ':'
- Feature names do not contain ':' or ','
- Each feature appears at most once on the left side of dependency_lines
Examples
Input: ('US', 'android', 12, ['login'], ['US', 'CA'], 10, 14, 'checkout', ['checkout', 'payments'], ['checkout: login, payments', 'payments: '])
Expected Output: (True, 'ENABLED')
Explanation: The user is eligible. 'login' is already enabled, and 'payments' is in the rollout batch with no dependencies. This also checks correct parsing of multiple dependencies and an empty dependency list.
Input: ('US', 'ios', 16, [], ['US'], 10, 15, 'checkout', ['checkout'], ['checkout: login'])
Expected Output: (False, 'MISSING_DEPENDENCY: login')
Explanation: The user is eligible, but 'login' is neither already enabled nor included in the rollout batch.
Input: ('US', 'android', 13, [], ['US'], 10, 15, 'search', ['search', 'A', 'B'], ['search: A', 'A: B', 'B: A'])
Expected Output: (False, 'CYCLE: A -> B -> A')
Explanation: The target feature depends on 'A', and 'A' and 'B' form a cycle.
Input: ('CA', 'ios', 17, [], ['CA', 'US'], 10, 15, 'A', ['A', 'B', 'C', 'D'], ['A: B', 'B: C', 'C: D', 'D: A'])
Expected Output: (False, 'CYCLE: A -> B -> C -> D -> A')
Explanation: This is a longer cycle. The rejection reason must list every feature in the detected cycle.
Input: ('FR', 'android', 8, [], ['US', 'CA'], 10, 15, 'A', ['A', 'B'], ['A: B', 'B: A'])
Expected Output: (False, 'COUNTRY_AND_PLATFORM_NOT_ALLOWED')
Explanation: Edge case: both country and platform checks fail, so the function must return the combined rejection reason and must not inspect dependencies.
Hints
- Check country and platform first, and only start DFS dependency checking if both pass.
- Use DFS with a recursion path list plus a map from feature to its position in the path to build exact cycle messages.