Validate a Bijective Substitution Cipher

Question

The candidate is asked to validate whether a given substitution cipher is bijective, meaning each character in the input maps uniquely to a character in the output and vice versa.

Codemia · Accepted Answer

To validate a bijective substitution cipher, we need to ensure that each character in the input string maps to a unique character in the output string and that no two characters in the input map to the same character in the output. This can be achieved using two hash maps (dictionaries) to track the mappings in both directions.

1. Initialize two dictionaries: `map_input_to_output` and `map_output_to_input`.
2. Iterate through the characters of the input and output strings simultaneously.
3. For each character pair, check if the mappings exist in both dictionaries. If they do not exist, create them. If they do exist but do not match, return false.
4. If all pairs are validated, return true.

Here is the Python code implementation:
```python
def is_bijective(input_str, output_str):
    if len(input_str) != len(output_str):
        return False
    map_input_to_output = {}
    map_output_to_input = {}
    for char_input, char_output in zip(input_str, output_str):
        if char_input in map_input_to_output:
            if map_input_to_output[char_input] != char_output:
                return False
        else:
            map_input_to_output[char_input] = char_output
        if char_output in map_output_to_input:
            if map_output_to_input[char_output] != char_input:
                return False
        else:
            map_output_to_input[char_output] = char_input
    return True
```

The time complexity of this algorithm is O(n), where n is the length of the input strings, as we are iterating through the characters once. The space complexity is also O(n) due to the storage required for the two dictionaries.

Consider edge cases such as empty strings, strings of different lengths, and strings with special characters. An empty input and output should return true, as there are no mappings to validate. If the lengths differ, return false immediately.

1. `is_bijective('abc', 'xyz')` should return True.
2. `is_bijective('aabb', 'xxyy')` should return True.
3. `is_bijective('abc', 'xyzz')` should return False.
4. `is_bijective('abc', 'xyzx')` should return False.

Validate a Bijective Substitution Cipher

Remitly

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Approach

Algorithm

Submit Your Answer

Remitly Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string