## Amazon Interview Question for Software Developers

• 0
of 0 votes

Team: India
Country: India
Interview Type: Written Test

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

(N-2)*2^(N-3)

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

This formula will give a redundant count for a string with all b
Ex N = 4
actual unique strings : abbb, bbbb, bbba
strings considered form above formula : abbb, bbbb, bbba, bbbb
(2*(2^1))=4)

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

Well, it seems there is no right and easy solution so far.
I do believe it is possible to think of a nice and easy solution.
How many strings of 'a's and 'b's we can make? It is 2^(N) where N is the length of the string and 2 is a number of different symbols.
How many strings with "bbb" in them? We reduce the length of the string by 3(it is 2^(N-3)) and put "bbb" into all possible position into each such strings. How many positions? N-3+1 = N-2;
So, it is the initial formula from the first answer - (N-2)*2^(N-3). Now we have to handle the duplicates.
When do we have a duplicate? Then we insert "bbb" before "b" symbol in the string - the next insertion will give us the same result. How many times we insert before "b"? Half of the total number of insertion (there is the same number of insertions before "a" and before "b"). So, each insertion before "a" and after "a" give the different unique combinations, and insertion before "b" and after "b" gives the same unique combination. So, all we need to do is to multiply the formula by 3/4.
The resulting formula is (3/4)(N-2)*2^(N-3).
The general version is (3/4)(N-b+1)2^(N-b) where b is the length of "bb..bbb" string.
The code in C/C++

int GetNumberOfString(int N, int b)
{
return (3*N-3*b+3)*(pow(2, N-b))/4;
}

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

(N-2)*2^(N-3) - 1

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

(N-2)*2^(N-3) - 1 (for redundant count )

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

It looks like that solution from the above is not right...
let's assume that n is length of a word and q is number of consequent numbers.
for n = 6 and q = 3 we should consider following cases ('_' is a place where could be rather 'A' or 'B'):
1. BBB___ --> 8 different cases. --> 8 unique cases. --> 2^(n - q)
2. _BBB__ --> 8 different cases, but 4 is similar to case 1. --> 4 unique cases. --> 2^(n - q - 1)
3. __BBB_ --> 8 different cases, but 4 is similar to case 2. --> 4 unique cases. --> 2^(n - q - 1)
4. ___BBB --> 8 different cases, but 4 is similar to case 3. --> 4 unique cases. --> 2^(n - q - 1)

amount of shifts with amount of unique cases that equals to 2^(n - q - 1) is (n - q)

and 20 unique cases in total.

so, it means that total number of cases is 2^(n - q) + (n - q)*2^(n - q - 1) == (n - q + 2)*2^(n - q - 1)

so implementation is the following:

``````/**
* Count number of strings of length N with following properties:
*
* A. Consists of char 'A' and 'B' only.
* B. There is at least one occurrence of 3 consecutive Bs.
*/
public class StringWithProperties {

private final long modulo = 1000000007L;

long getNumberOfStringsByModuloWithLength(int n, int q) {
if (n < q) {
return 0L;
}

long expectedNumber = n - q + 2;

if (n - q - 1 >= 0) {
for (int i = 0; i < n - q - 1; i++) {
expectedNumber <<= 1;
expectedNumber %= modulo;
}
} else {
expectedNumber >>= 1;
expectedNumber %= modulo;
}

return expectedNumber;
}
}``````

Add a Comment
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.

Learn More

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

Learn More

### Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

### Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More