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

30-minute interview with a team member. After a brief introduction, I was asked to solve the following problem:

You are given two 8-character strings composed of A, G, C, or T (start and end). You are also given bank, which contains mutations of the string. Find the minimum number of mutations needed to transform start into end, where a mutation is defined as the change of a single character. Each mutation must be included in bank. If no path exists, return -1. Note that start is considered a valid mutation even if it is not present 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:
`python
start = 'ACCCCCCC', end = 'AAAACCCC', bank = ['AACCCCCC', 'AAAACCCC']
Output: -1
There is no path where all mutations are in `bank` ('AAACCCCC' is missing).

My proposed solution involved converting bank into a set for efficient lookup and using Breadth-First Search (BFS).