How to tell if an a date occurs multiple times in an array/collection

[laredotornado]

Hi,

I have an array of Calendar objects. How can I tell if any of the
object's values in the array occurs more than once (e.g. two objects
with values "01-01-1999 9:00 AM")? If it is easier, I can convert the
Calendar[] array to some other type of collection.

Thanks, - Dave

 

[Lew]

I have an array of Calendar objects.  How can I tell if any of the
object's values in the array occurs more than once (e.g. two objects
with values "01-01-1999 9:00 AM")?  If it is easier, I can convert the
Calendar[] array to some other type of collection.

If you load the data into a 'Set <Calendar>' you cannot have any
duplicates.

Set <Calendar> calends =
new HashSet <Calendar> ( Arrays.asList( getArrayOfCalendars() ));

You can iterate over the array and load the counts into a
'Map <Calendar, Integer>'.

Map <Calendar, Integer> counts =
new HashMap <Calendar, Integer>
( getArrayOfCalendars() .length * 4 / 3 );
for ( Calendar calend : getArrayOfCalendars() )
{
Integer k = counts.get( calend );
counts.put( calend, (k == null? 1 : k + 1) );
}
for ( Map.Entry <Calendar, Integer> entry : counts.entrySet() )
{
if ( entry.getValue() > 1 )
{
System.out.println( "Duplicates found for "+ entry.getKey() );
}
}

This should be about O(n) for performance.

 

[Dagon]

I have an array of Calendar objects. How can I tell if any of the
object's values in the array occurs more than once (e.g. two objects
with values "01-01-1999 9:00 AM")? If it is easier, I can convert the
Calendar[] array to some other type of collection.

Heh, it's been a long time since I've seen this interview question. I have a
secret hope that it's a real problem, but it seems unlikely.

I'm going to assume that you care about millisecond precision, but do not care
about what non-Date data (like timezone) the Calendar contains. Thus, I'll
compare the getTimeInMillis() rather than just using .equals() or doing
something more complicated to truncate to minutes as your example shows.

The usual "most-efficient" approach would be to sort the data and then
look for consecutive duplicates.

That's most efficient only if you don't want to allocate additional space.
If you don't mind having a separate data structure, it's more efficient
to build a hash as you check for duplicates.

O(n) for a hash-based solution, O(n * logn) for the sort.

A less efficient alternative is to examine each element and search the
array for a duplicate. But that's O(n^2) instead of O(n log n). You'd
only want to do it that way if your collection is extremely small or for
some reason sorting (optionally copying before) the data was impossible.

Build the search as you go. something like:

Map<Long, Calendar> calendars = new HashMap<Long, Calendar>();
for (Calendar c : calendarArray) {
long calValue = c.getTimeInMillis();
if (calendars.containsKey(calValue)) {
// you have a duplicate! Do whatever you must!
}
calendars.put(calValue, c);
}

 

[Arne Vajhøj]

I have an array of Calendar objects. How can I tell if any of the
object's values in the array occurs more than once (e.g. two objects
with values "01-01-1999 9:00 AM")? If it is easier, I can convert the
Calendar[] array to some other type of collection.

Set is probably the solution.

But the implementation will depend a bit on what you consider same
value.

same second, timezone does not matter
same millisecond, timezone does not matter
same second, same timezone
same millisecond, same timezone
same second localtime
same millisecond localtime

Arne

 

[Roedy Green]

I have an array of Calendar objects. How can I tell if any of the
object's values in the array occurs more than once (e.g. two objects
with values "01-01-1999 9:00 AM")? If it is easier, I can convert the
Calendar[] array to some other type of collection.

An array is probably the most convenient and fast format.

Just do a sort with Arrays.sort so the dups will be side by side.

then scan down the array comparing current with prev marking dups as
null.

Track how many are left. Allocate an array that big and copy non-nulls
into it.

see http://mindprod.com/jgloss/sort.html

 

[Roedy Green]

The usual "most-efficient" approach would be to sort the data and then
look for consecutive duplicates.

Another approach is to use a HashSet. Fill the set, it will
automatically eliminate dups then extract the set as an array.
The code for this is simpler, but I suspect it is slower.

 

[Teraposa Lunodas]

Do this

Set <Calendar> calends =
new HashSet <Calendar> ( Arrays.asList( getArrayOfCalendars() ));

You can iterate over the array and load the counts into a
'Map <Calendar, Integer>'.

Map <Calendar, Integer> counts =
new HashMap <Calendar, Integer>
( getArrayOfCalendars() .length * 4 / 3 );
for ( Calendar calend : getArrayOfCalendars() )
{
Integer k = counts.get( calend );
counts.put( calend, (k == null? 1 : k + 1) );
}
for ( Map.Entry <Calendar, Integer> entry : counts.entrySet() )
{
if ( entry.getValue() > 1 )
{
System.out.println( "Duplicates found for "+ entry.getKey() );
}
}