Google Interview Question
SDE-3sCountry: United States
def get_all_possible_words(list_numbers):
def extend_words(words, letters):
res = []
for letter in letters:
for word in words:
res.append(word + letter)
return res
mapping = {
0: [""],
1: [""],
2: ["a", "b", "c"],
3: ["d", "e", "f"],
4: ["g", "h", "i"],
5: ["j", "k", "l"],
6: ["m", "n", "o"],
7: ["p", "q", "r", "s"],
8: ["t", "u", "v"],
9: ["w", "x", "y", "z"]
}
return reduce(extend_words, map(lambda x: mapping[x], list_numbers))
print get_all_possible_words([5, 2, 3])
def calcount(count, number):
array = [0 for i in range(number+1)]
array[0] = 0
array[1] = 1
array[2] = 2
array[3] = 4
if(number == 4):
array[4] = 8
if(count>number):
array += [0 for i in range(number+1, count+1)]
print(array)
for i in range(number+1, count+1):
for j in range(1,number+1):
array[i] += array[i-j]
print(array[i])
print(array[count])
return array[count]
def KeypadToStrings(keypadString):
keymap = {i: 4 if i in [7,9] else 3 for i in range(2,10)}
first = keypadString[0]
count = 1
totalcount = 1
for i in range(1, len(keypadString)):
if (keypadString[i] == first):
count += 1
else:
totalcount *= calcount(count, int(keymap[int(first)]))
print(first, count, totalcount)
first = keypadString[i]
count = 1
print(first, count, totalcount)
totalcount *= calcount(count, int(keymap[int(first)]))
print(totalcount)
def main():
keypadString = "234544447748"
KeypadToStrings(keypadString)
main()
Dictionary question - javascript solution
function matches(input, dict) {
var result = [];
for (let i of dict) {
var temp = [];
var count = 0;
var matchFound = checkPrefix([i], input);
if (matchFound) {temp.push(i); count += i.length}
while (matchFound && count <= input.length) {
var currString = input.substring(count);
matchFound = checkPrefix(dict, currString)
if (!matchFound) break;
temp.push(matchFound);
count += matchFound.length
}
if (count == input.length) result.push(temp.join(' '));
}
return result;
}
function checkPrefix(dict, word2) {
if (!dict.length || !word2.length) return false;
for (let i of dict) {
var result = '';
for (let j = 0; j < i.length; j++) {
if (i[j] != word2[j]) break;
result += i[j]
}
if (result == i) return result;
}
return false;
}
public class MobileNumberPadProblem {
static final Map<Integer, List<String>> PAD = new HashMap<>();
static {
PAD.put(0, Arrays.asList("".split(" ")));
PAD.put(1, Arrays.asList("a b c".split(" ")));
PAD.put(2, Arrays.asList("d e f".split(" ")));
PAD.put(3, Arrays.asList("g h i".split(" ")));
PAD.put(4, Arrays.asList("j k l".split(" ")));
PAD.put(5, Arrays.asList("m n o".split(" ")));
PAD.put(6, Arrays.asList("p q r".split(" ")));
PAD.put(7, Arrays.asList("s t u".split(" ")));
PAD.put(8, Arrays.asList("v w x".split(" ")));
PAD.put(9, Arrays.asList("y z".split(" ")));
}
private static List<String> formWords(int[] arr, int i) {
if (i == arr.length - 1)
return new ArrayList<>(PAD.get(arr[i]));
List<String> l = formWords(arr, i + 1);
int size = l.size();
for (int j = 0; j < size; j++) {
String s = l.remove(0);
for (String x : PAD.get(arr[i])) {
l.add(x + s);
}
}
return l;
}
}
- josbimosbi December 25, 2016