Given a hashmap M which is a mapping of characters to arrays of substitute characters, and an input string S, return an array of all possible mutations of S (where any character in S can be substituted with one of its substitutes in M, if it exists). What is the time complexity? What is the space complexity? Can you optimize either? Example input: M = { f: [F, 4], b: [B, 8] } S = fab Expected output: [fab, Fab, 4ab, faB, FaB, 4aB, fa8, Fa8, 4a8]

Question

Accepted Answer

Given a hashmap M and an input string S, return an array of all possible mutations of S using M's substitutes.

Iterate through each character in S and get its substitutes from M
Use recursion to generate all possible combinations of substitutes for each character
Time complexity: O(n^m) where n is the average number of substitutes per character and m is the length of S
Space complexity: O(n^m) due to the number of possible combinations
Optimization: Use memoization to store previously computed combinations and reduce redundant computations

Top Facebook SDE interview questions & answers

Popular interview questions of SDE

Top HR questions asked in Facebook SDE