Forums Register Login

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

+Pie Number of slices to send: Send
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?

+Pie Number of slices to send: Send
 

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.
+Pie Number of slices to send: Send
 

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.
+Pie Number of slices to send: Send
 

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.
Grow your own food... or this tiny ad:
a bit of art, as a gift, that will fit in a stocking
https://gardener-gift.com


reply
reply
This thread has been viewed 318 times.
Similar Threads
Comparing two collections...
equals() vs inheritance
TreeSet - Object input and output
HashSet and equals()
why treeset does not implement equals and hashcode
More...

All times above are in ranch (not your local) time.
The current ranch time is
Mar 28, 2024 02:16:29.