• Post Reply Bookmark Topic Watch Topic
  • New Topic

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

 
Saurabh Pillai
Ranch Hand
Posts: 541
  • Mark post as helpful
  • send pies
  • 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?

 
Paul Clapham
Sheriff
Posts: 22841
43
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • 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.
 
German Martinez
Greenhorn
Posts: 17
  • Mark post as helpful
  • send pies
  • 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.
 
Stephan van Hulst
Saloon Keeper
Posts: 7993
143
  • Mark post as helpful
  • send pies
  • 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.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!