第一轮
You have a huge array of integers containing only 0’s and 1’s. Write an algorithm that finds the number of 1’s found in the array in a specific range .
Method: howManyOnesInRange(int start, int end)
Example: array = [0,1,1,1,0,0]
howManyOnesInRange(0,3) should return 3.
Can you do it better than O(n) ?
第二轮
An engineer came up with an encoding mechanism that converts words into numbers like so:
mad -> 1314 (13 for m because its the 13th letter in the alphabet, and so on.) Now, he realized that this encoding mechanism is not great because a particular encoded string can be decoded into multiple words.
For example, ’ mad ’ can also be decoded into: acad (looking at the digits: 1,3,1,4)
Write an algorithm that given an encoding string of digits (eg. 1314), return the number of possible words that it can be decoded into.
method: int countDecodings(String encodedString)
input: String encodedString (eg.1314)
output: Integer representing the number of possible words that you can make out of the input.