Amazon Interview Question
SDE-2sCountry: United States
void findCount_iter(const std::string& str, int currIndex, char currChar, int& count)
{
if (str.size() == currIndex)
{
// Only if we have a valid string, increment the count
if (currChar == 'c')
{
++count;
}
return;
}
// Possibly including the current char
if (str[currIndex] == currChar)
{
findCount_iter(str, currIndex + 1, currChar, count);
}
else if (str[currIndex] == currChar + 1)
{
findCount_iter(str, currIndex + 1, currChar + 1, count);
}
// Skipping the current char
findCount_iter(str, currIndex + 1, currChar, count);
}
int findCount(const std::string& str)
{
int count = 0;
findCount_iter(str, 0, 'a' - 1, count);
return count;
}
public static int CountSequences(string input)
{
char[] chars = input.ToCharArray();
int count = 0;
CountSequences(chars, 0, 'a', ref count);
return count;
}
//abcabc
private static void CountSequences(char[] chars, int startIndex, char lookupChar, ref int count)
{
if (lookupChar > 'c') return;
for (int currentIndex = startIndex; currentIndex < chars.Length; currentIndex++)
{
if (chars[currentIndex] == lookupChar) //found a match
{
if (lookupChar == 'c')
{
count++;
}
else
{
CountSequences(chars, currentIndex + 1, (char)(lookupChar + 1), ref count);
}
CountSequences(chars, currentIndex + 1, lookupChar, ref count);
}
}
}
The O(n) idea is to use dynamic programming. If letter is 'a' and you know the number of valid strings ending in 'a' for characters up to position i, the new number is 2n+1 because you keep all strings up to position i (n), you add this 'a' to all previous strings (+n) and you can have this char as a separate string (+1).
With a similar thinking
nBs = 2 nBs + nAs
nCs = 2 nCs + nBs
E.g.
a b c a b c
1 1 1 3 3 3 nAs
0 1 1 1 5 5 nBs
0 0 1 1 1 7 nCs
This problem can be done by recursive or iterative way.
Recursive way is very inefficient as it can be of the order of O(n2) plus a lot of method stacks gets created.
Iterative solution is best solution that gets over in O(n) times. Its given as below.
Its some one wants to know more about how its calculated then he can email me at teji.catia@gmail.com:
public class IterativeSeq {
public static void main(String[] args){
IterativeSeq t= new IterativeSeq();
System.out.println("output="+t.CountSeq("abcabcaabbcc"));
}
public static int CountSeq(String input){
int acount=0, bcount=0, ccount=0;
char[] chars = input.toCharArray();
for(int i=chars.length-1; i>=0;i--){
if(chars[i]=='c'){
ccount++;
}else if(chars[i]=='b'){
bcount=((int)Math.pow(2,ccount)-1)+(bcount*2);
}else if(chars[i]=='a'){
acount=bcount+(2*acount);
}
}
return acount;
}
}
This problem can be resolved in either recursive or iterative way.
Recursive way is very inefficient as it may take O(n^2) or more and causes many method stacks being built upon.
Iterative solution is best with guaranteed O(n) running time. Its a below.
If someone wants to know about how formula is derived. He can mail me at teji.catia@gmail.com.
public class IterativeSeq {
public static void main(String[] args){
IterativeSeq t= new IterativeSeq();
System.out.println("output="+t.CountSeq("abcabcaabbcc"));
}
public static int CountSeq(String input){
int acount=0, bcount=0, ccount=0;
char[] chars = input.toCharArray();
for(int i=chars.length-1; i>=0;i--){
if(chars[i]=='c'){
ccount++;
}else if(chars[i]=='b'){
bcount=((int)Math.pow(2,ccount)-1)+(bcount*2);
}else if(chars[i]=='a'){
acount=bcount+(2*acount);
}
}
return acount;
}
}
- Surya February 25, 2017