Microsoft Interview Experience — Part 2 (Solution in Swift)

Microsoft Interview Experience — Part 2 (Solution in Swift)

1. Given a dictionary, a method to do a lookup in the dictionary and a M x N board where every cell has one character. Find all possible words that can be formed by a sequence of adjacent characters.

Note that we can move to any of 8 adjacent characters, but a word should not have multiple instances of the same cell.

Input: dictionary[] = [ “seed”, “weed”,“need”,“ate”,“tend”,“rent”]
       boggle[3][3]   = [[“r”,”w”,”e”], [“t”,”e”,”d”], [“s”,”a”,”n”]]

Output:  ["weed", "tend", "seed", "ate", "need"]

Solution:

Info Note:
1. Insert and search costs for Trie: O(string_length), however the memory requirements of Trie is O(ALPHABET_SIZE * string_length * N)
2. DFS time complexity is proportional to the total number of vertexes and edges of the graph visited. In our case, there are N*M vertexes, soO(N*M)

2. Given a digit sequence, count the number of possible decodings of the given digit sequence. Let 1 represent ‘A’, 2 represents ‘B’, etc.

An empty digit sequence is considered to have one decoding. It may be assumed that the input contains valid digits from 0 to 9 and there are no leading 0’s, no extra trailing 0’s and no two or more consecutive 0’s.

Time Complexity: O(n)
Auxiliary space: O(1)

Input:  digits[] = "121"
Output: 3
// The possible decodings are "ABA", "AU", "LA"

Input: digits[] = "1234"
Output: 3
// The possible decodings are "ABCD", "LCD", "AWD"

Solution: