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

data structure that can store all the different numbers from two separated streams

 
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: Design and implement a data structure that can store all the different numbers from two separated streams. Implement two methods 1) intersection() 2) union()

Below is my take,


Time Complexity intersection method:

Let's say Set has N elements.
- for loop, O(N)
- contains and add method, O(1)

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


Time Complexity union method:

Let's say Set1 has N elements and Set2 has M elements.

- Set<Integer> union = new HashSet<Integer>(s1);   O(N)
- union.addAll(s2); O(M)

O(N) + O(M) = O(N + M)  Is this correct?

 
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

Saurabh Pillai wrote:Problem Statement: Design and implement a data structure that can store all the different numbers from two separated streams...



That seems a bit strange to me. Normally when you design a data structure, your design depends on how the data structure is going to be used. It rarely if ever depends on where the data is coming from.

And your Problem Statement doesn't go on to say anything about how it's going to be used. All it does is to provide the names of two methods, again not saying anything about what they are supposed to do.
 
Greenhorn
Posts: 17
  • 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 intersection method:

Let's say Set has N elements.
- for loop, O(N)
- contains and add method, O(1)

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



I'm no sure. Contains method in s2.contains(a) has to explore all the s2 set searching for a. How it is done? I don't know. it can be secuentially or it can be a binary tree search, I'm guessing it's the second one.
 
Saloon Keeper
Posts: 13843
312
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

German Martinez wrote:I'm no sure. Contains method in s2.contains(a) has to explore all the s2 set searching for a. How it is done? I don't know. it can be secuentially or it can be a binary tree search, I'm guessing it's the second one.


No, it happens via a hash table lookup operation, which is constant time. HashSet.contains() takes roughly the same amount of time every time, regardless of how many elements are in the set.
 
Those who dance are thought mad by those who hear not the music. This tiny ad plays the bagpipes:
Free, earth friendly heat - from the CodeRanch trailboss
https://www.kickstarter.com/projects/paulwheaton/free-heat
reply
    Bookmark Topic Watch Topic
  • New Topic