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!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
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
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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)
- duplicates.add(a);, for HashSet add is constant O(1)

O(N LogN) + O(1)
= O(N LogN)>
 
Saloon Keeper
Posts: 9265
78
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I wouldn't use a sort(). A HashMap with count for a value would be quicker.
 
Saurabh Pillai
Ranch Hand
Posts: 541
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Saurabh Pillai wrote:
Time complexity of getDuplicates method:

Let's assume that list has N elements.

- Collections.sort(input), O(N LogN)
- duplicates.add(a);, for HashSet add is constant O(1)

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)
-- duplicates.add(a);, for HashSet add is constant O(1)

O(N LogN) + O(N) + O(1)
= O(N(LogN + 1))
= O(N LogN)
 
Saurabh Pillai
Ranch Hand
Posts: 541
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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.



Time Complexity: about O(N)
 
Carey Brown
Saloon Keeper
Posts: 9265
78
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Saurabh Pillai wrote:


In Java-8 this could be replaced with

 
Paul Clapham
Marshal
Posts: 27211
87
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I interpreted "find out the duplicates" to mean counting them. Possibly that was a careless reading of the question.
 
Sheriff
Posts: 22645
123
Eclipse IDE Spring VI Editor Chrome Java Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
reply
    Bookmark Topic Watch Topic
  • New Topic