byteattack
BAN USERWorking:
Initialize the combinations with each letter for the first digit
letter_combination.extend([[letter] for letter in letters])
Then for each additional digit
for letter in letters:
x = combi[:]
x.append(letter)
letter_combination.append(x)
this will create a copy of the combination in the list of combinations (without modifying the original. Also note we remove the existing one here
letter_combination.remove(combi)
we remove this because
combination = a b c
if next digit it 3 then
remove A
create a copy of A (ie x)
then append d e f to A one by one and add it to list
thus letter_combination becomes
ad ae af b c
then remove b and repeat
ad ae af bd be bf
and so on..
Python Without Recursion
def phone_number(number):
keypad = {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']}
letter_combination = []
for digit in number:
if digit == 1:
letters = []
else:
letters = keypad[digit]
if not letter_combination:
# initialize the combination with the letters of first digit
letter_combination.extend([[letter] for letter in letters])
continue
else:
for combi in letter_combination[:]:
letter_combination.remove(combi)
for letter in letters:
x = combi[:]
x.append(letter)
letter_combination.append(x)
print letter_combination
Take N elements (first elements from N lists), make them a Heap (logN) i.e N * log N)
Then Remove the items one by one (again a logN operation) -> logN + Log N-1 - log 2 ~ O(logN) N times.
Till now it is total NlogN Then this will be done K times
= O(KN logN)
This question was asked to me for a Google SRE Phone screen Interview 2 years back. The solution uses 1 hashmap and 3 passes.
- byteattack May 18, 2014Create a copy of the link list (without considering the random pointer) while you do that fill the hashmap with Key = Original Node Value = New Node
Second pass go over both the linked (new and original) again
then go over hashmap and use the value to fill up the random pointer position in the new list.