Amazon Interview Question
SDE1sCountry: United States
Interview Type: Phone Interview
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
{
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.
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} .
using multiply and modulo operators
sites.google.com/site/spaceofjameschen/home/array/remove-duplicates-in-prime-numbers----amazon
but if we keep on multiplying it will exceed size of long long(10^15).
Solution is not scalable.
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]+" ");
}
}
}
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.
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?
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.
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.
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
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);
}
}
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.
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);
}
Given that these are prime numbers.
- praneeth June 15, 2013Product = 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.