«

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

laredotornado wrote:
> 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.

--
Lew

>laredotornado wrote:
>> 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.

Peter Duniho <> wrote:
>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);
}
--
Mark Rafn <http://www.dagon.net/>

laredotornado wrote:
> 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

On Wed, 18 Nov 2009 10:07:34 -0800 (PST), laredotornado
<> wrote, quoted or indirectly quoted someone
who said :

>
>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 Canadian Mind Products
http://mindprod.com
Finding a bug is a sign you were asleep a the switch when coding. Stop debugging, and go back over your code line by line.

On Wed, 18 Nov 2009 10:31:19 -0800, Peter Duniho
<> wrote, quoted or indirectly quoted
someone who said :

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

--
Roedy Green Canadian Mind Products
http://mindprod.com
Finding a bug is a sign you were asleep a the switch when coding. Stop debugging, and go back over your code line by line.

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() );
}
}