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

30 minutes interview with a member of the team. After a short introduction, I had to solve a problem.

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`).  

Proposed solution:
Transform bank to set for efficient lookup. BFS.