Amazon Interview Question SDE-2s
Country: India
I might be wrong but I think the curDecodeCount += last1; and curDecodeCount += last2; lines are switched.
I can't see why when str = "1234", it returns 3 which is wrong, there is no letter equivalent to "34"
This is a Fibonacci counting algorithm, advancing to the next number in Fibonacci series every time a digit equal to 1 or 2 is encountered, except the last digit. The input has to be parsed from the end. If there is a digit encountered other than 1 or 2, then no need to advance further in the Fibonacci series.
Lets say our input is 421122345
Substring Number of combinations
======= ===================
5 1
45 1
345 1
2345 2
22345 3
122345 5
1122345 8
21122345 13
421122345 13
What about "19191919"? Clearly, every 1 can be seen alone or as part of 19, so there is 2^4 = 16 ways to decode the string which is more than 8, the fibonacci number you would get using your algorithm.
What you have to do is find the correct fibonnaci number for consecutive blocks of 1s and 2s and then multiply those numbers. Also, when you encounter a 2, make sure the digit after is 6 or less ("27" can only be decoded one way).
djmclaugh: The Fibonacci count will still work as cannyzanny mentioned.
Good catch with 27, 28 and 29... I missed that... Thank you.
My logic, as is, will work for 19191919, but it wont work for 29292929. With my logic, it says number of ways to decode is 16, but in actual, its just 1.
public class HelloWorld{
public static int count=0;
public static void main(String []args){
getC("12",0);
System.out.println(count);
}
public static void getC(String str, int i)
{
if(str.length()==i)
{
count++;
return;
}
else if(i<str.length())
{
int d=0, c=str.charAt(i)-'0';
if(i+1<str.length())
d=str.charAt(i+1)-'0';
getC(str,i+1);
if(c<3 && d<7)
getC(str,i+2);
}
}
}
public class AlphabetMapping {
public static void main(String[] args) {
System.out.println(countMappings("111111"));
System.out.println(countMappings("1221"));
System.out.println(countMappings("123"));
}
private static int countMappings(String string) {
int count = 0;
for (int k = 0; k < string.length() - 1; k++) {
int part = Integer.parseInt(string.substring(k, k + 2));
if (part > 0 && part <= ALPHABET) {
count++;
count += subCount(string, k);
}
}
return ++count;
}
private static int subCount(String string, int k) {
int subCount = 0;
for (int q = k + 2; q < string.length() - 1; q++) {
int near = Integer.parseInt(string.substring(q, q + 2));
if (near > 0 && near <= ALPHABET) {
subCount++;
subCount += subCount(string, q);
}
}
return subCount;
}
private static final int ALPHABET = 26;
}
I solved it using a binary tree. Use toString() for a textual representation of the tree. Code in Python.
Time complexity: O(n)
Space complexity: O(n)
{{
class Node:
def getLeft(self):
return self.left
def getRight(self):
return self.right
def getVal(self):
return self.val
def __init__(self, v):
self.val = v
self.left = None
self.right = None
def add(self,v):
if(self.left == None):
self.left = Node(v)
else:
self.left.add(v)
if(self.right == None):
n = self.left.val * 10 + v
if(n <= 26):
self.right = Node(n)
else:
self.right.add(v)
def nLeafs(self):
if(self.left == None and self.right == None):
return 1
if(self.left != None and self.right != None):
return self.left.nLeafs() + self.right.nLeafs()
if(self.left != None):
return self.left.nLeafs()
if(self.right != None):
return self.right.nLeafs()
def toString(self,indent):
print "$%s%s" % (indent, self.val)
if(self.left != None):
self.left.toString(indent + " ")
if(self.right != None):
self.right.toString(indent + " ")
def buildtree(tree, n):
if(n % 10 == 0):
return
buildtree(tree, n / 10)
tree.add(n % 10)
number = 123
tree = Node('root')
buildtree(tree, number)
print "Number of ways: ", tree.nLeafs()
}}
I solved it using a binary tree. Use toString() for a textual representation of the tree. Code in Python.
Time complexity: O(n)
Space complexity: O(n)
class Node:
def getLeft(self):
return self.left
def getRight(self):
return self.right
def getVal(self):
return self.val
def __init__(self, v):
self.val = v
self.left = None
self.right = None
def add(self,v):
if(self.left == None):
self.left = Node(v)
else:
self.left.add(v)
if(self.right == None):
n = self.left.val * 10 + v
if(n <= 26):
self.right = Node(n)
else:
self.right.add(v)
def nLeafs(self):
if(self.left == None and self.right == None):
return 1
if(self.left != None and self.right != None):
return self.left.nLeafs() + self.right.nLeafs()
if(self.left != None):
return self.left.nLeafs()
if(self.right != None):
return self.right.nLeafs()
def toString(self,indent):
print "$%s%s" % (indent, self.val)
if(self.left != None):
self.left.toString(indent + " ")
if(self.right != None):
self.right.toString(indent + " ")
def buildtree(tree, n):
if(n % 10 == 0):
return
buildtree(tree, n / 10)
tree.add(n % 10)
number = 123
tree = Node('root')
buildtree(tree, number)
print "Number of ways: ", tree.nLeafs()
** Sorry for the multiple comments. Fixing indentation as it is important for Python.**
I solved it using a binary tree. Use toString() for a textual representation of the tree. Code in Python.
Time complexity: O(n)
Space complexity: O(n)
#!/user/bin/python
class Node:
def getLeft(self):
return self.left
def getRight(self):
return self.right
def getVal(self):
return self.val
def __init__(self, v):
self.val = v
self.left = None
self.right = None
def add(self,v):
if(self.left == None):
self.left = Node(v)
else:
self.left.add(v)
if(self.right == None):
n = self.left.val * 10 + v
if(n <= 26):
self.right = Node(n)
else:
self.right.add(v)
def nLeafs(self):
if(self.left == None and self.right == None):
return 1
if(self.left != None and self.right != None):
return self.left.nLeafs() + self.right.nLeafs()
if(self.left != None):
return self.left.nLeafs()
if(self.right != None):
return self.right.nLeafs()
def toString(self,indent):
print "$%s%s" % (indent, self.val)
if(self.left != None):
self.left.toString(indent + " ")
if(self.right != None):
self.right.toString(indent + " ")
def buildtree(tree, n):
if(n % 10 == 0):
return
buildtree(tree, n / 10)
tree.add(n % 10)
number = 123
tree = Node('root')
buildtree(tree, number)
print "Number of ways: ", tree.nLeafs()
static void PrintPossibleEncoding(string str, Dictionary<string, char> hashMap, List<char> stack, int index)
{
if (index == str.Length)
{
foreach (char a in stack)
Console.Write(a);
Console.WriteLine('\n');
return;
}
char temp;
temp = hashMap[str[index].ToString()];
stack.Add(temp);
PrintPossibleEncoding(str, hashMap, stack, index + 1);
stack.RemoveAt(stack.Count - 1);
if (index + 1 < str.Length)
{
string tempstr = str.Substring(index, 2);
temp = hashMap[tempstr];
stack.Add(temp);
PrintPossibleEncoding(str, hashMap, stack, index + 2);
stack.RemoveAt(stack.Count - 1);
}
}
Dynamic programming solution.
- m@}{ August 23, 2014/** * time: O(N) * space: O(1) */ int decodeCount(char[] arr){ int last1 = 0; int last2 = 1; for( int i = 0; i < arr.length; i++ ){ int curDecodeCount = 0; int num = arr[i] - '0'; if( num > 0 && num < 27 ){ curDecodeCount += last2; } if(i > 0){ num = (arr[i-1]-'0') * 10 + num; if( num > 0 && num < 27 ){ curDecodeCount += last1; } } last1 = last2; last2 = curDecodeCount; } return last2; }