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 easy difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Duolingo.

What role is this question designed for?

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

Implement String Encryption and Decryption

Company: Duolingo

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: easy

Interview Round: Technical Screen

Implement an encryption service for lowercase words. You are given: - `keys`: a list of distinct lowercase characters. - `codes`: a list of strings where `codes[i]` is the encrypted representation of `keys[i]`. - `dictionary`: a list of valid lowercase words. A character can be encrypted only if it appears in `keys`. To encrypt a word, replace each character with its mapped code and concatenate the results. If any character in the word has no mapping, the word cannot be encrypted. Implement a class with the following methods: ```text Constructor(keys, codes, dictionary) ``` Initializes the encryption mapping and stores the dictionary. ```text encrypt(word) -> string ``` Returns the encrypted string for `word`. If `word` contains an unmapped character, return an empty string. ```text decrypt(ciphertext) -> list[string] ``` Returns all words from `dictionary` whose encrypted form is exactly equal to `ciphertext`. Unlike a version that returns only the count of matching dictionary words, this method must return the actual matching words. Notes: - Multiple characters may map to the same code. - Preserve dictionary words in their original order in the returned list. - You may assume inputs are valid unless otherwise stated.

Quick Answer: This question evaluates understanding of string encoding and mapping, including handling non-bijective character-to-code relationships and performing dictionary-based reverse lookups for decryption.

Implement the behavior of an encryption service for lowercase words. You are given: - `keys`: a list of distinct lowercase characters, represented as 1-character strings. - `codes`: a list of strings where `codes[i]` is the encrypted representation of `keys[i]`. - `dictionary`: a list of valid lowercase words. A character can be encrypted only if it appears in `keys`. To encrypt a word, replace each character with its mapped code and concatenate the results. If any character in the word has no mapping, the word cannot be encrypted. For this challenge, write a function `solution(keys, codes, dictionary, operations, arguments)` that initializes the encryption service once using `keys`, `codes`, and `dictionary`, then processes each operation in order: - If `operations[i] == 'encrypt'`, then `arguments[i]` is a word. Append its encrypted string to the result, or `''` if the word contains an unmapped character. - If `operations[i] == 'decrypt'`, then `arguments[i]` is a ciphertext. Append a list of all words from `dictionary` whose encrypted form is exactly equal to that ciphertext. Important notes: - Multiple characters may map to the same code. - Return decrypt results in the original dictionary order. - If a dictionary word contains an unmapped character, it can never appear in any decrypt result.

Constraints

1 <= len(keys) == len(codes) <= 26
All entries in `keys` are distinct lowercase letters represented as 1-character strings
0 <= len(dictionary) <= 10^4 and 0 <= len(operations) == len(arguments) <= 10^4
1 <= len(codes[i]) <= 10
The total length of all dictionary words and all operation arguments is at most 2 * 10^5

Examples

Input: (['a', 'b', 'c', 'd'], ['ei', 'zf', 'ei', 'am'], ['abcd', 'acbd', 'adbc', 'badc', 'dacb', 'cadb', 'cbda', 'abad'], ['encrypt', 'decrypt', 'encrypt', 'decrypt'], ['abcd', 'eizfeiam', 'badc', 'eiam'])

Expected Output: ['eizfeiam', ['abcd', 'abad'], 'zfeiamei', []]

Explanation: `encrypt('abcd')` becomes `ei + zf + ei + am = 'eizfeiam'`. Both `'abcd'` and `'abad'` encrypt to `'eizfeiam'`, so the decrypt query returns them in dictionary order. `'badc'` encrypts to `'zfeiamei'`. No dictionary word encrypts to `'eiam'`.

Input: (['a', 'b'], ['x', 'yy'], ['ab', 'ba', 'aa', 'ab', 'c'], ['encrypt', 'encrypt', 'decrypt', 'decrypt'], ['abc', 'ba', 'xyy', ''])

Expected Output: ['', 'yyx', ['ab', 'ab'], []]

Explanation: `'abc'` cannot be encrypted because `'c'` has no mapping, so the result is `''`. `'ba'` becomes `'yyx'`. The ciphertext `'xyy'` matches both occurrences of `'ab'`, and duplicates must be preserved. No dictionary word encrypts to the empty string.

Input: (['a', 'b', 'c'], ['m', 'm', 'n'], ['a', 'b', 'c', 'ab', 'ba', 'ac'], ['decrypt', 'encrypt', 'decrypt'], ['m', 'ac', 'mm'])

Expected Output: [['a', 'b'], 'mn', ['ab', 'ba']]

Explanation: Both `'a'` and `'b'` map to `'m'`, so decrypting `'m'` returns `['a', 'b']`. `'ac'` encrypts to `'mn'`. The ciphertext `'mm'` matches `'ab'` and `'ba'`.

Hints

Build a direct mapping from each character in `keys` to its encrypted code so that encrypting one word is just a linear scan.
For fast decryption, encrypt every dictionary word once up front and group words by their ciphertext. Then each decrypt query becomes a hash map lookup.

Quick Overview

This question evaluates understanding of string encoding and mapping, including handling non-bijective character-to-code relationships and performing dictionary-based reverse lookups for decryption.