How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Take-home Project rounds at Google.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Google during technical interviews.

Solve checksum and dependency debugging tasks

Quick Overview

This question evaluates skills in string processing, modular arithmetic-based checksum computation and mapping, plus debugging of feature enablement logic that involves configuration parsing, dependency resolution, and cycle detection.

Solve checksum and dependency debugging tasks

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Take-home Project

The online assessment contained two coding tasks. 1. **Build a validation string from checksums** You are given: - a lowercase string `s` - a validation string `validation_chars` - an integer `k` Partition `s` into consecutive substrings of length `k`. You may assume `s.length` is a multiple of `k`. Assign each character a value using its zero-based alphabet index (`a = 0`, `b = 1`, ..., `z = 25`). For each length-`k` substring: - compute the checksum as the sum of its character values - compute `checksum % validation_chars.length` - use that result as an index into `validation_chars` - append the selected character to the output Return the final validation string. 2. **Debug feature enablement with dependencies** You are given an existing implementation that reads feature definitions from a text file. Each feature may specify: - allowed countries - a minimum OS version - a list of dependent features The runtime input includes: - a user's country - a user's OS version - a set of pre-enabled features - a set of requested features A requested feature can be enabled only if: - the user's country is allowed for that feature - the user's OS version satisfies the feature's minimum version requirement - all of its dependencies are enabled, either because they were already pre-enabled or because they can also be validly enabled - the dependency graph contains no cycles The task is to debug and fix the code so that it correctly determines which requested features can be enabled and correctly rejects invalid requests, including cyclic dependencies.

Quick Answer: This question evaluates skills in string processing, modular arithmetic-based checksum computation and mapping, plus debugging of feature enablement logic that involves configuration parsing, dependency resolution, and cycle detection.

Part 1: Build a Validation String from Checksums

You are given a lowercase string s, a non-empty string validation_chars, and an integer k. Split s into consecutive substrings of length k. You may assume len(s) is a multiple of k. For each substring: 1. Convert each character to its zero-based alphabet index: a = 0, b = 1, ..., z = 25. 2. Compute the checksum as the sum of those values. 3. Compute checksum % len(validation_chars). 4. Use that result as an index into validation_chars and append the selected character to the answer. Return the final validation string.

Constraints

0 <= len(s) <= 10^5
1 <= len(validation_chars) <= 10^5
1 <= k <= 10^5
len(s) is a multiple of k
s contains only lowercase English letters

Loading coding console...

Examples

Input: ('abcd', 'wxyz', 2)

Expected Output: 'xx'

Explanation: 'ab' -> 0+1=1 -> index 1 -> 'x'; 'cd' -> 2+3=5 -> 5%4=1 -> 'x'.

Input: ('zzzz', 'abc', 2)

Expected Output: 'cc'

Explanation: Each block 'zz' has checksum 25+25=50. Since 50%3=2, each block contributes 'c'.

Input: ('leetcode', 'abcde', 4)

Expected Output: 'dd'

Explanation: 'leet' sums to 38 and 'code' sums to 23. Both give index 3 when taken modulo 5.

Input: ('', 'abc', 2)

Expected Output: ''

Explanation: An empty input string has no blocks, so the result is also empty.

Part 2: Determine Which Requested Features Can Be Enabled

You are given feature definitions and a user's runtime information. Each feature definition contains: - countries: the list of allowed countries - min_version: the minimum OS version required - dependencies: other features that must be enabled first A requested feature can be enabled if: 1. The user's country is in that feature's allowed countries. 2. The user's OS version is at least the feature's min_version. 3. Every dependency is already in pre_enabled, or can itself be enabled by the same rules. 4. Dependency resolution does not encounter a cycle. If a dependency name does not exist in the feature definitions, treat that dependency as invalid. Return the requested features that can be enabled, in the same order they appear in requested. Auto-enabled dependencies should not be included in the result unless they were explicitly requested. Important: Features listed in pre_enabled are treated as already active and satisfy dependency checks immediately.

Constraints

0 <= number of features <= 10^4
0 <= total number of dependency edges <= 5 * 10^4
0 <= user_os_version <= 10^9
Feature names are unique strings
requested contains unique feature names
pre_enabled contains unique feature names

Examples

Input: ({'core': {'countries': ['US', 'CA'], 'min_version': 1, 'dependencies': []}, 'chat': {'countries': ['US'], 'min_version': 2, 'dependencies': ['core']}, 'video': {'countries': ['US'], 'min_version': 3, 'dependencies': ['chat']}}, 'US', 3, [], ['chat', 'video'])

Expected Output: ['chat', 'video']

Explanation: 'core' can be enabled automatically, so both requested features are valid.

Input: ({'core': {'countries': ['US', 'CA'], 'min_version': 1, 'dependencies': []}, 'chat': {'countries': ['US'], 'min_version': 2, 'dependencies': ['core']}, 'pay': {'countries': ['GB'], 'min_version': 4, 'dependencies': []}}, 'US', 3, [], ['chat', 'pay'])

Expected Output: ['chat']

Explanation: 'chat' is valid. 'pay' is invalid because the user is not in an allowed country and also does not meet the minimum OS version.

Input: ({'A': {'countries': ['US'], 'min_version': 1, 'dependencies': ['B']}, 'B': {'countries': ['US'], 'min_version': 1, 'dependencies': ['A']}, 'C': {'countries': ['US'], 'min_version': 1, 'dependencies': []}}, 'US', 1, [], ['A', 'C'])

Expected Output: ['C']

Explanation: 'A' and 'B' form a cycle, so 'A' cannot be enabled. 'C' has no dependencies and is valid.

Input: ({'auth': {'countries': ['CA'], 'min_version': 10, 'dependencies': []}, 'dashboard': {'countries': ['US'], 'min_version': 1, 'dependencies': ['auth']}}, 'US', 1, ['auth'], ['dashboard'])

Expected Output: ['dashboard']

Explanation: 'auth' is already pre-enabled, so it satisfies the dependency immediately.

Input: ({'base': {'countries': ['US'], 'min_version': 1, 'dependencies': []}}, 'US', 5, [], [])

Expected Output: []

Explanation: With no requested features, the result is empty.

Hints

Model feature dependencies as a directed graph.
Use DFS with memoization and a visiting state to detect cycles and avoid recomputing the same feature repeatedly.