## Amazon Interview Question for SDE-2s

• 0

Country: India

Comment hidden because of low score. Click to expand.
6
of 6 vote

Dynamic programming solution.

``````/**
* 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;
}``````

Comment hidden because of low score. Click to expand.
-2

When str = "1234", it returns 3 which is wrong.

Comment hidden because of low score. Click to expand.
0

I might be wrong but I think the curDecodeCount += last1; and curDecodeCount += last2; lines are switched.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

I can't see why when str = "1234", it returns 3 which is wrong, there is no letter equivalent to "34"

Comment hidden because of low score. Click to expand.
0

It is correct, str="1234" is 3 only.... ABCD, LCD, AWD,
34 does not represent any character.
This is correct implementation.

Comment hidden because of low score. Click to expand.
1
of 1 vote

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

Comment hidden because of low score. Click to expand.
0

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).

Comment hidden because of low score. Click to expand.
0

for 19191919 you get 16 following the fibonacci algorithm

9 1
19 2
919 2
1919 4

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

The dynamic programming solution above is also excellent.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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);
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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;

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

if(self.left == None):
self.left = Node(v)
else:

if(self.right == None):
n = self.left.val * 10 + v
if(n <= 26):
self.right = Node(n)
else:

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)

number = 123

tree = Node('root')
buildtree(tree, number)

print "Number of ways: ", tree.nLeafs()
}}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

if(self.left == None):
self.left = Node(v)
else:

if(self.right == None):
n = self.left.val * 10 + v
if(n <= 26):
self.right = Node(n)
else:

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)

number = 123

tree = Node('root')
buildtree(tree, number)

print "Number of ways: ", tree.nLeafs()``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

** 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

if(self.left == None):
self.left = Node(v)
else:

if(self.right == None):
n = self.left.val * 10 + v
if(n <= 26):
self.right = Node(n)
else:

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)

number = 123

tree = Node('root')
buildtree(tree, number)

print "Number of ways: ", tree.nLeafs()``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Perm(n) = Perm(n-1) +charat(n)

eg: Perm(235) = Perm(23) + 5
= [Perm(2) +3 ] +5
=2 + 3 + 5
= (2,3) (23) + 5
= (2,3,5) (2,35) (23,5)
= bce , invalid, we

Comment hidden because of low score. Click to expand.
0
of 0 vote

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()];
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];
PrintPossibleEncoding(str, hashMap, stack, index + 2);
stack.RemoveAt(stack.Count - 1);
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

BXKGJjxkgm xkkxkif zhoxjg Gk jv gkvk gmvkxjjgc ckj fjfiiffiififiidifixfxjf

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.