## Amazon Interview Question for Software Developers

• 0

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.
0
of 0 vote

Is this question should not be solved using recursion (like we do in permutations of a string however, with additional conditions) or the interviewer expect only the formula from us?

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

``````import java.math.BigInteger;

public class Solution {

public static void main(String[] args) {

System.out.println(new Solution().count(10)); // = 520

/*
* N = 500
* Result = 3273390607896141870013189696827599152216642046043064789483291368096133796404674554883270092325904157150886684127560071009217256545885393053328843506427
*/
System.out.println(new Solution().count(500));
}

BigInteger count(int N) {

if (N < 3)
return new BigInteger("0");

int x_1 = 2;
int x_2 = 4;
int x_3 = 7;

for (int i = 4; i <= N; i++) {
int temp = x_1 + x_2 + x_3;

x_1 = x_2;
x_2 = x_3;
x_3 = temp;
}

BigInteger e = new BigInteger("2");
return (e.pow(N).subtract(new BigInteger(String.valueOf(x_3))));
}

}``````

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

We can apply BFS here. We can start from bbb and then for every iteration we will have four different strings like: bbb+'a', 'a'+bbb, 'b'+bbb, bbb+'b'. As last two strings are same we will only add one in the queue. Now we can keep on iterating until our N becomes 0.

This problem is similar problem like step numbers.

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

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.