## Amazon Interview Question

• 0

Country: India
Interview Type: Phone Interview

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

``````Divide the numbers into 3 groups:
A = { x | x % 3 == 0}, P = |A|
B = { x | x % 3 == 1}, Q = |B|
C = { x | x % 3 == 2}, R = |C|

To pick 2 numbers whose sum is a multiple of 3 we can:
(1) pick 2 from A which have C(P,2) cases
(2) pick 1 from B, and 1 from C, which has Q*R cases

To pick 3 numbers whose sum is a multiple of 3 we can:
(1) pick 3 from A, which has C(P,3) cases
(2) pick 3 from B, which has C(Q,3) cases
(3) pick 3 from C, which has C(R,3) cases
(4) pick 1 from A, 1 from B, and 1 from C, which has P*Q*R cases``````

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

Good.

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

``````This solution does not take negative numbers into account. You need to add the following:
D = { x | x % 3 == -1 }, S = |D|
E = { x | x % 3 == -2 }, T = |E|

and

for duples
(3) pick 1 from D and 1 from E...

for triples
(5) pick 3 from D...
(6) pick 3 from E...
(7) pick 1 each from A, D and E...``````

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

@Westake Could you please explain your terminalnogy.. its difficult for me to understand.
Please give solve a example for finding doublet.

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

It's an excellent idea to partition the set based on the above mentioned properties.

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

Elegant and concise !!
In this question, though, we can only choose an element once, so nC2 or m*n won't really be applicable, but the idea is still very much relevant. Thanks!

Also, how much overhead are we expecting in all the set operations?

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

The question asks for "maximum" number of duplets/triplets and also specifies that number included once cannot be used again. Considering this, I would modify the solution provided by "Westlake" as below:

``````Divide the numbers into 3 groups:
A = { x | x % 3 == 0}, P = |A|
B = { x | x % 3 == 1}, Q = |B|
C = { x | x % 3 == 2}, R = |C|

To maximize count, we should try to have as may duplets as possible:
Number of duplets from set A = int(P/2) ; combine pairs of elements of A
Number of duplets from Set B,C = min(Q, R) ; combine one element of B with one element of C

If Q>R, then there will be left over elements in Q and viceversa; These can be combined as triplets
Number of triplets = int(abs(Q-R)/3)
Any other left over elements of A, B, C cannot be combined to a multiple of 3 anymore.

Max count = int(P/2) + min(Q,R) + int(abs(Q-R)/3)``````

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

very nicely explained its gives us a complete solution

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

In addition to the DP solution , I think we can also use this:

consider this class:

``````class number implements Comparator {
int value;
int count;

public int compareTo(number obj) {
if (obj == count)
return 0

return obj < count ? -1 : 1;
}
}``````

and have a HashMap like this

``HashMap <int, number> values = SortedMap<int, number>()``

and store the values in this hashMap as you iterate through the array, this will automatically sort the elements as you store them in the HashMap, upon completion, you can easily check
if the count of the elements is enough that they are multiples of 3 or not.

Using the HashMap will give us the O(1) access time.

P.S. You can obivously make the class 'number' more robust if you give your own implementations of the hashCode and equals method to avoid collisions in case of very large datasets.

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

Here is some C# code I put together. It's probably not the most efficient, but it works.

``````// the array
int[] values = { 1, 6, 1, 7, 9, 25, 76, 3, 23, 86 };

// count of duples
int count = 0;

// find duples
for (LinkedListNode<int> i = valuesList.First; i != null; i = i.Next)
{
for (LinkedListNode<int> j = i.Next; j != null; j = j.Next)
{
if ((i.Value + j.Value) % 3 == 0)
{
// we found one so increment the count, and remove the
// values from the list
++count;
valuesList.Remove(j);
//remove j first then save i.Next so we don't lose our place
valuesList.Remove(i);
i = k;
}
}
}

// find triples
for (LinkedListNode<int> i = valuesList.First; i != null; i = i.Next)
{
for (LinkedListNode<int> j = i.Next; j != null; j = j.Next)
{
for (LinkedListNode<int> k = j.Next; k != null; k = k.Next)
{
if ((i.Value + j.Value + k.Value) % 3 == 0)
{
// we found one so increment the count, and remove the
// values from the list
++count;
valuesList.Remove(j);
valuesList.Remove(k);
//remove j and k first then save i.Next so we don't lose our place
valuesList.Remove(i);
i = k;
}
}
}
}``````

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

Looks like the problem for DP.

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

why to go for DP unnecessary , i think we can do in generally linear time using boolean hash map as mentioned above:
below is not actual code,but i think it should work ...please comment guys..

``````bool map[3] = {false};
for(i=0;i<size;i++)
map[i%3]++;
//in case of doublets
first_count = map[0]/3;
second_count  = min(map[1],map[2]);
return first_count+second_count;
//in case of triplets
first_count = map[0]/3 + map[1]/3 + map[2]/3;
second_count = min(map[0]-map[0]/3,map[1]-map[1]/3,map[2]-map[2]/3);
return first_count + second_count;``````

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.