Expedia Interview Question
Software Engineer / DevelopersCountry: India
First solution is to create a hash table of Integer size. 0- 2pow 32 and initialize it by 0, whenever you get any no. check the value at that position, if it is 0, it is only the first time we have encountered that no. increment it and proceed.
This would have the Time Complexity as O(1) but has space contraints.
Implement a better way to make it Space efficient as well.
I think the time complexity with solution is O(n) because you have to traverse the entire array to print out all the duplicates. Space is your bitvector size.
Ohh... I missed this.
I mean you would be fed an stream of numbers(which goes in million) and with every no. you get you have to print if the no. is actually a duplicate.
Sorry My Bad.
what if we take two arrays the other array would be of size of the maximum number in the first array +1 as soon as a number is encountered the location corresponding to this element in the second array is incremented.
I hope i am clear
we can do it like this,
int nLength = array.Length();
for ( int nIndex = 0; nIndex < nLength; nIndex++ ) {
while ( arr[i] != i && arr[i] != arr[arr[i]] ) {
swap(arr[i], arr[arr[i]] );
}
}
for ( int nIndex = 0; nIndex < nLength; nIndex++ ) {
if ( arr[i] != i )
print(arr[i]);
}
Its obvious, that we need to go through all numbers atleast once to find out the duplicates.
If extra space is ok, use hashsets. they store unique elements:
int array[] = { 1, 2, 3, 6, 4, 1, 7, 8, 9, 3, 2, 2, 5, 3, 4, 3, 6, 4 };
Set<Integer> uniqueNums = new HashSet<Integer>(array.length);
Set<Integer> duplicates = new HashSet<Integer>();
for (int i = 0; i < array.length; i++)
{
if (uniqueNums.contains(array[i]))
{
//numbers can be duplicate more then twice, so store unique again
duplicates.add(array[i]);
}
else
{
uniqueNums.add(array[i]);
}
}
System.out.println("Duplicates: " + duplicates);
If no extraspace, then have to compromise of time. Sorting and finding out is the only key
You need not to use contains as purpose of contains can be fulfilled by add operation as it will return false for duplicates and interviewer is only asking for printing the duplicates so you need not to store the duplicates in another hashset( assuming that we need not to worry about the duplicates of duplicates here.)
using Hash table is not right approach when we have million of numbers,.,,,,,think
- Anonymous October 01, 2012