## Accenture Interview Question Software Engineer / Developers

• 0

how you will find duplicate number in an array.
let's suppose a[]={1,23,40,50,40,93}

Country: India
Interview Type: Written Test

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

1. perform sorting (merge, quick sort ...etc)
2. compare current value and previous one

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

time complexity is more , is it not possible with xor tricks?

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

Simple answer: no, it's not possible with XOR tricks.

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

Xor tricks work when you know some range i.e array size is n+1 and the numbers are in between 1 to n all like that. otherwise if the random number is there then you wont be able to find any answer using xor.

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

* U can use a hashmap if extra memory is allowed and range is not specified ...
* If range is given use a bit vector instead of a Map

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

``````package com.careercup;

import java.util.HashSet;

public class FindDuplicateUsingMaps {

public static HashSet<Integer> getDuplicates(int[] givenArray)
{
HashSet<Integer> v=new HashSet<Integer>();
HashSet<Integer> hs=new HashSet<Integer>();

for(int a: givenArray)
{
{
}
}
return v;

}

public static void main(String[] args)
{
int[] givenArray={0,1,1,2,4,1,1,1};
HashSet<Integer> v= getDuplicates(givenArray);
for(int duplicates: v)
{
System.out.println(duplicates);
}
}
}``````

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

Time complexity is: Theta(n)
Space complexity: O(n)

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

Use a hashtable to keep track of all numbers in the array. key and value will have the number. If you try to insert duplicate you will get exception and that is our duplicate number. Time complexity: o(n) ; space complexity o(n)

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

It would had become so much more efficient and convenient to do this had the array been that of a set of characters or if the range of the numbers were given.

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

no range is given , array can contain random number.

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

then sorting and comparing is all i can think of. Hopefully someone here will come up with a better solution.

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

thanks
if range is given then we can xor the array element with the index and get the answer .But here i have one doubt
if a[5]={0,1,1,2,4} range is (0-4) then how we find out the repeated number.

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

if suppose the range is (0-4) like you are saying, then we create an integer array of size 5, call it finalArray. Initialize the array to 0s for each index. Now iterate through the given array. First number is 0. Mark finalArray[0]=1, similarly go making the 0s into 1s. When we reach a point when when the finalArray[index] value is already 1, then that is the repeated number.

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

and space complexity of this approach is "n".
correct me if i m wrong.

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

and one more thing how can we do this problem using xor .

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

if you mean 'n' when n is the size of the given array, then no. The array size may be 300. But the given range may be [0-30]. So the size of the binary array we make will be only 31. Actually this approach is best when the array is a set of characters. We can make an array of size 26(number of english alphabets). However for small given rages it can be effectively used. If the range is from 1 to 1 million then using this method would be useless.

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

``````package com.careercup;

public class FindDuplicates {

public static int[] getDuplicates(int[] givenArray, int range)
{
int i=0;
int[] binaryArray=new int[range+1];
int[] arrayOfDuplicates= new int[range+1];

for(int b:givenArray)
{
if(binaryArray[b]==1)
{
arrayOfDuplicates[i]=b;
i++;
binaryArray[b]=2;
}
else if(binaryArray[b]==0)
{
binaryArray[b]=1;
}
}
int[] arrayOfDuplicates1=new int[i];
for(int m=0;m<i;m++)
{
arrayOfDuplicates1[m]=arrayOfDuplicates[m];
}

return arrayOfDuplicates1;
}

public static void main(String[] args)
{
int[] givenArray={0,1,1,2,4};
int range=4;
int[] arrayOfDuplicates= getDuplicates(givenArray,range);
for(int duplicates: arrayOfDuplicates)
{
System.out.println(duplicates);
}
}
}``````

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

this code is for only when the range is given.

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

Time complexity: Theta(n)
Space complexity: O(1)

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

I think we can first find the max number in the array, for example it is k, the time complexity is O(n).
Then we can use an array of size k, just like the way commented above to count the number of each number's appearance, the time complexity is O(n).
Finally, scan the array to find which is larger than 1, got it! The time complexity is also O(n).

So, 3 steps, O(n) time complexity, O(k) space complexity

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

How can be the time complexity equals to o(n).
first you find out the maximum number i.e access the complete array,then you again fill the array with numbers , and then search the repeated number.
i guess in this case the time complexity is greater than o(n).

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

Hmm, I think this may work not so efficiently when the given array is like {1, 65535}, this will make the count array very sparse. But if we require O(n) time complexity, I think there are no better ways, just to sacrifice the space. We can use bit array to minimize the sacrifice.

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

suppose 'k' is too large, this will cause a huge space complexity. The array might be something like {1,1,1crore}. We should use this only when k is a small number. Also we are forgetting, there maybe be negative integers too. So when the given range is [0-small_number] then we can use the approach u are mentioning.

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

Each step is O(n), and they are independence steps， so in all is 3*O(n)（maybe，the prefix is a constant）, still O(n). It will not become O(nlgn) or O(n^2).

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

If there are negative integers, we should use hashmap instead.

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

@onpduo: your approach makes no sense to me. Maybe I'm not understanding you.

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

Build a binary tree.. and if a duplicate element was there, then element cannot be inserted..
however larger the range..
Time complexity:O(n lgn)
Space Complexity: O(n)

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

So it is a binary search tree? When you insert a number into this tree, you need to search from root, just a little bit like insertion sort, thus the time complexity is larger than O(n).

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

it depends on input...
for the best case:
while inserting 2nd and 3rd element it is O(1)
while inserting 4th to 7th element it is O(2)
so its just O(lg n) .. it is not O(n)

average case and worst case: O(nlgn)

in the worst case: for 2nd element it has to traverse only 1 element
for 3rd element , to traverse only 2 elements
we cant say this as O(n^2)

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

This is a bad solution because if you're going to have O(NlogN) complexity, you might as well do something like sort 2 arrays and then compare them sequentially. This will have a much lower constant factor and will use less space, by a constant factor.

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

``````void removeduplicate(int a[],int n)
{
merge_sort(a,n);
for(int i=0;i<n;i++)
{
if(a[i]==a[i+1])
{
cout<<"\n duplicate found";
cout<<a[i];

}
else
continue;
}
}``````

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

How about using a bitset ?

``````private static int dup(int[] arr) {
BitSet bitSet = new BitSet(arr.length);
for (int i=0; i<arr.length; i++) {
if (bitSet.get(arr[i]) == true) {
return arr[i];
} else {
bitSet.set(arr[i]);
}
}
return -1; // -1 means no dups, can use some random number too
}``````

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

wastage of space is high.

for the input {1,1000}
bitSet.length() = 1001
bitSet.size() = 1024

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

Bitset's only appropriate when the range of values is small.

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

It depends on what is more important. If the maximum speed was needed I would create a very big array of bools:

``````array[]={1,23,40,50,40,93}
visited[] = new Array(2^32)
for element in array
if(visited[element])
visited[element] = true
else
print "Duplicate is found"``````

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

Oops, I meant

``if(!visited[element])``

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

but an array of size 2^32 is a lot of space. Imagine the given array is {1,2} then look at the space wastage.

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

It takes a long time to loop over an array of size 2^32. And what if they're 64 bit integers?

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book walking you through every aspect of getting a job at a top tech company, while focuses on software engineering interviews.

### 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.