Microsoft | SWE I | Oct 2024 | Technical Screening [Passed]

Round 1

Questions: You are given two 8-characters long strings made of A, G, C or T (start and end). You are also given bank, that contains mutations of the string. You have to find the minimum number of mutations to get from start string to end, considering a mutation as the edition of 1 character. For every step, the mutation should be included in bank. If there is no path, return -1. start is considered a valid mutation even if it does not appear in bank.

Example 1:

start = 'ACCCCCCC', end = 'AAAACCCC', bank = ['AACCCCCC', 'AAACCCCC', 'AAAACCCC']
Output: 3
Mutations: ACCCCCCC -> AACCCCCC -> AAACCCCC -> AAAACCCC. All mutations are in `bank`.

Example 2:

start = 'ACCCCCCC', end = 'AAAACCCC', bank = ['AACCCCCC', 'AAAACCCC']
Output: -1
There is no path such that all mutations are in `bank` ('AAACCCCC' is not in `bank`).