Saurabh Pillai

Ranch Hand

Posts: 541

posted 1 month ago

Below is my take,

Time Complexity

Let's say Set has N elements.

- for loop, O(N)

- contains and add method, O(1)

O(N) + O(1) =

Time Complexity

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) =

**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?

posted 1 month ago

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.

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

posted 1 month ago

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.

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

posted 1 month ago

No, it happens via a hash table lookup operation, which is constant time.

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.

*The mind is a strange and wonderful thing. I'm not sure that it will ever be able to figure itself out, everything else, maybe. From the atom to the universe, everything, except itself.*