These are solutions to the two algorithmic questions I was asked in my Microsoft Program Manger Intern interview
Convict’s Ransom Note
The solution I came up with was to create an array of length 26 that will represent counts of letters in the ransom note. For example, if the note contains 4 letter ‘a’s, index 0 will be set to 4. My solution was certainly influenced by UW CSE143’s Letter Inventory assignment. In addition to the array, I used a counter to represent the sum of the values of the array. After setting up this array and counter, I traversed through the magazine. To compare our note’s needs with the magazine’s letters. Here’s some pseudo code:
counter = 0
loop through letters of note{
increment corresponding index of the current letter by 1 and increment counter by 1
}end loop
loop through letters of magazine{
if value of corresponding index is greater than 0{
decrement value of corresponding index and counter, each by 1
if counter is 0, return true
}
}end loop
return false //did not find enough needed letters in magazine
Variation A- words instead of letters:
replace array with a Map with strings for keys and Integers for values
Variation B- allow homophones:
Create an interface that returns possible homophones when given a word.
in the algorithm, repalce
“if value of corresponding index is greater than 0{”
with
“get homophones for current word
loop through possible set of homophones and if the map contains one of them as a key, perform operation using that word”
Japanese Characters
The key to this problem is, starting from the end of the document and working backwards, to find the first position where you know a character ends. The correct way to do this is to find the first byte that starts with a 0 (ignoring the last byte), because a byte that begins with a 0 is either a one byte character or the last byte of a 2 byte character. From there, you can work backwards and discover if the last character is represented by 1 or 2 bytes.
The optimization comes from knowing that ignoring the last byte, all bytes before the key byte starting with a 0 start with a 1. Therefore, the number of bytes you looked over to get to the first byte that begins with a 0 determines whether the final character occupies 1 or 2 bytes.
