This week's giveaway is in the Testing forum.We're giving away four copies of TDD for a Shopping Website LiveProject and have Steven Solomon on-line!See this thread for details.
Win a copy of TDD for a Shopping Website LiveProject this week in the Testing forum!
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
• Campbell Ritchie
• Paul Clapham
• Ron McLeod
• Jeanne Boyarsky
• Tim Cooke
Sheriffs:
• Liutauras Vilda
• paul wheaton
• Henry Wong
Saloon Keepers:
• Tim Moores
• Tim Holloway
• Stephan van Hulst
• Carey Brown
• Frits Walraven
Bartenders:
• Piet Souris
• Himai Minh

# find out the duplicates in the given list of objects and Big O

Ranch Hand
Posts: 541
• Number of slices to send:
Optional 'thank-you' note:
Problem statement (AS IS): Write a program to find out the duplicates in the given list of objects. Explain the time complexity of your solution (Big O Notation)

Time complexity of getDuplicates method:

Let's assume that list has N elements.

- Collections.sort(input), O(N LogN)

O(N LogN) + O(1)
= O(N LogN)>

Saloon Keeper
Posts: 9265
78
• Number of slices to send:
Optional 'thank-you' note:
I wouldn't use a sort(). A HashMap with count for a value would be quicker.

Saurabh Pillai
Ranch Hand
Posts: 541
• Number of slices to send:
Optional 'thank-you' note:

Saurabh Pillai wrote:
Time complexity of getDuplicates method:

Let's assume that list has N elements.

- Collections.sort(input), O(N LogN)

O(N LogN) + O(1)
= O(N LogN)

Sorry I miscalculated this. It should be,

- Collections.sort(input), O(N LogN)
- for loop, O(N)

O(N LogN) + O(N) + O(1)
= O(N(LogN + 1))
= O(N LogN)

Saurabh Pillai
Ranch Hand
Posts: 541
• Number of slices to send:
Optional 'thank-you' note:

Carey Brown wrote:I wouldn't use a sort(). A HashMap with count for a value would be quicker.

This is how I have implemented it.

Carey Brown
Saloon Keeper
Posts: 9265
78
• Number of slices to send:
Optional 'thank-you' note:
Two tweaks I'd make to this. First, return List<String> instead of ArrayList<String>, always program to the interface if possible. And second, you are calling both contains() and get() when just calling get() and checking for null would suffice (and be more efficient).

Marshal
Posts: 27211
87
• Number of slices to send:
Optional 'thank-you' note:
You don't really need the Map with counts. The add(E) method of HashSet returns a boolean value which tells you whether you added a duplicate or not. All you need is something to count whichever boolean value means "duplicate".

But as for the OP: Yes, the sort is O(N log N), your evaluation of your code is correct. (Nothing in the question you posted asked you to find the most time-efficient implementation of the requirements.)

Carey Brown
Saloon Keeper
Posts: 9265
78
• Number of slices to send:
Optional 'thank-you' note:

Paul Clapham wrote:You don't really need the Map with counts. The add(E) method of HashSet returns a boolean value which tells you whether you added a duplicate or not. All you need is something to count whichever boolean value means "duplicate".

If you return a Set<String> this would work, but if your return a List<String> then ["one","one","one"] would return a List with "one" in there twice. (unless I'm misunderstanding you)

Carey Brown
Saloon Keeper
Posts: 9265
78
• Number of slices to send:
Optional 'thank-you' note:

Saurabh Pillai wrote:

In Java-8 this could be replaced with

Paul Clapham
Marshal
Posts: 27211
87
• Number of slices to send:
Optional 'thank-you' note:
I interpreted "find out the duplicates" to mean counting them. Possibly that was a careless reading of the question.

Sheriff
Posts: 22645
123
• Number of slices to send:
Optional 'thank-you' note:
But you can still use it:

 We don't have time to be charming! Quick, read this tiny ad: Free, earth friendly heat - from the CodeRanch trailboss https://www.kickstarter.com/projects/paulwheaton/free-heat