Amazon Interview Question for SDE1s


Country: United States
Interview Type: Phone Interview




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

Given that these are prime numbers.

Product = 1;
i=0;
j=0;
until end of array:
{
if Product % array[i] == 0
skip;
else
{
Product = Product * array[i];
array[j] = array[i];
j++;
}
i++
}

The only challenging part is how to store the product. My idea is to main a product array. Whenever overflow occurs in one index, store it in the next. Every time you have to traverse this product array to check if the element already encountered.

- praneeth June 15, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Nice one praneeth. Your algorithm seems to fix the array by removing duplicates in-place. correct?

I guess you can have some savings with the below modification.

if Product % array[i] == 0
Product = Product/(array[i] * array[i])
skip
else
{

- Murali Mohan June 15, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Let's say all the products in the array overflow, in that case your product array will be almost as big as the input array. Consequently, the algorithm will run in O(n^2) time.
The sure shot way of ensuring O(n) time complexity is to fall back to hash-map solution whenever an overflow occurs.

- Epic_coder June 16, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is not working for following input array of prime numbers: {2 3 3 5 6 6} as output is coming {2 3 5 -1 -1 -1} .

- neeraj October 08, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

i apologize and i need to take my comment back. posted in wrong way.

- neeraj October 08, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

using multiply and modulo operators
sites.google.com/site/spaceofjameschen/home/array/remove-duplicates-in-prime-numbers----amazon

- Anonymous June 15, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

very simple

- Anonymous June 15, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

but if we keep on multiplying it will exceed size of long long(10^15).
Solution is not scalable.

- Anonymous June 15, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

can you please put algorithm in words ..

- ashwitha93 June 16, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

James, plz explain your algorithms in words instead of just giving your site URL.

- Murali Mohan June 17, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Not any different from Praneeth's solution. This is not scalable.

- Murali Mohan June 17, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

import java.io.*;
import java.util.Arrays;

public class array1	{
	
	public static void removeDuplicates(int [] primeNum)	{
		int tail=1;
		int checker=primeNum[0];
		for (int i=1;i<primeNum.length;i++)	{
			
			if(checker%primeNum[i]==0)	{
				continue;
			}
			checker=checker*primeNum[i];
			primeNum[tail]=primeNum[i];
			tail++;
			}
		Arrays.fill(primeNum, tail, primeNum.length, -1);
	}
	
	public static void main(String args[])	{
		int [] primeNum={2,3,5,5,2,7,11,23};
		for(int i=0;i<primeNum.length;i++)	{
			System.out.print(primeNum[i]+" ");
		}
		removeDuplicates(primeNum);
		System.out.println("After removing:");
		for(int i=0;i<primeNum.length;i++)	{
			System.out.print(primeNum[i]+" ");
		}
		
		
	}
}

- Sibendu Dey June 21, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

We can do it by making BST and adding elements to it and if the element with the key already exists in the BST then simply ignores that and take the next input.

- sharma.jayesh52 June 14, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Why do you want to use BST for that? Why not just sort the array? Or use hash map to detect duplicates? Why aren't you leveraging the fact that all the elements are prime numbers?

- Epic_coder June 14, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Agree hash map will be better approach,but even then we aren't using the fact that input is prime number?

- sharma.jayesh52 June 15, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

13 59 23 47 3 59 53 13 19 23 3 7 suppose this is the array
take an hash table set the (ceil of the square root of the number)=1, so no two prime number will share the same hash index
so the size of the hash table will be reduced to square root of max number in the array which is better to take a hash of max number size.

- Anonymous June 14, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

5 and 7 will have the same hash index

- Is_it? June 15, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

13 59 23 47 3 59 53 13 19 23 3 7 suppose this is the array
take an hash table set the (ceil of the square root of the number)=1, so no two prime number will share the same hash index
so the size of the hash table will be reduced to square root of max number in the array which is better to take a hash of max number size.

- Anonymous June 14, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

We can create an integer array of huge size,
for(i=0;i<10000;i++)
array[i]=0;
for(i=0;i<n;i++)
{
array[a[i]]=1;
}
the indices where array[] is 1, put that back in the array

- Anonymous June 15, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

why not insert into map and find the key count..... though this takes extra space it is lot faster..

- Aditya Vemuri June 15, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

We can use simple hashing on numbers provides O(n) solution

- Debasis Jana June 15, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

we can do sorting which would be O(nlogn) and we can check for duplicates na????

- ram rs June 15, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

class DupliatePrimeNumberRemover
    {
        public int[] remove(int[] array)
        {
            if(array == null || array.Length < 2) return array;
            int accu = 1;

            List<int> res = new List<int>();
            foreach (int v in array) {
                if (accu % v == 0) {
                    continue;
                }

                accu = accu * v;
                res.Add(v);
            }

            return res.ToArray();
        }

        public void test() {
            int[] primeArray = { 2, 3, 5, 7, 11, 13,13, 17, 19, 23, 31, 37, 41 };

            var res = remove(primeArray);
            AssertHelper.areEqual(res.Length, primeArray.Length - 1);

            res = remove(null);
            AssertHelper.areEqual(res, null);

            var array = new int[1] { 2 };
            res = remove(array);
            AssertHelper.areEqual(res.Length, array.Length);
            AssertHelper.areEqual(res[0], array[0]);

            array = new int[4] { 2, 3, 5, 2 };
            res = remove(array);
            AssertHelper.areEqual(res.Length, array.Length - 1);
        }
    }

- roger wang June 15, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

We can use counting sort also that in o(n) time

- Anonymous June 15, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use a HashSet<Integer>, insert all the elements, print them out.

O(N)

- zbesst June 16, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think just sort the array in O(n) time by counting sort and then check for duplicates

- vgeek June 16, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

traverse through the array.. keep multiplying all the element, and before mulitplying check whether that product is divisible by the element or not, if yes that element is duplicate.

boolean checkPrime(int []arr, int length) {
  for (int i = 0; i < length; i++) {
    int duplicate[length] = {0};
    int j = 0;
    int product = 1;
     if (product % arr[i] == 0 ) {
        duplicate[j++] = arr[i];
      } else {
         product = product * arr[i];
      }
   }
   if ( j == 0 ) {
      return false;
   } else {
     return true;
   }
}

duplicate will contain all the duplicate prime number.

- sjain June 16, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>
#define max 20
main()
{
    int p=1,prime[max],i=0,n;
    scanf("%d",&n);  //n->number if input elements
    while(i!=n)
    {
        printf("enter the prime:");
        scanf("%d",&prime[i]);
        if(p%prime[i]==0)
        {
            printf("duplicate:%d\n",prime[i]);
            i++;
        }
        else
        {
            p=p*prime[i];
            i++;
        }

    }
}

- blaster November 14, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

dup[] contains all duplicate elements......

#include<stdio.h>
#define max 20
main()
{
    int p=1,prime[max],i=0,n,j=0,dup[max];
    scanf("%d",&n);  //n->number if input elements
    while(i!=n)
    {
        printf("enter the prime:");
        scanf("%d",&prime[i]);
        if(p%prime[i]==0)
        {
            printf("duplicate:%d\n",prime[i]);
            dup[j]=prime[i];
            i++;j++;
        }
        else
        {
            p=p*prime[i];
            i++;
        }

    }
    i=j;
    do
    {
    printf("\t%d",dup[j-i]);
    i--;
    }while(i!=0);
}

- blast November 14, 2013 | 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