Amazon Interview Question for Software Developers


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)

- Alex April 10, 2019 | Flag Reply
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)

- ayugoel92 April 17, 2019 | Flag
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;
}

- AlexandrYegorov May 06, 2019 | Flag Reply
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?

- sai May 23, 2019 | Flag Reply
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))));
	}

}

- muesmat May 29, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

- Anonymous April 25, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

- Anand April 25, 2019 | Flag Reply
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;
  }
}

- Mike L May 04, 2019 | Flag Reply


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