Here is the interview question prompt, presented for reference.

As we ease our way into the course, we'll want to start with the basic data structures and their operations. However, don't be fooled how fundamental these things are!

Interviewers will often test you on things that are deceptively easy. We saw this in Reverse a String, and will see more in future challenges. But sometimes you might get tested on a concept that, while a bit trivial, is really useful in day to day software engineering.

One of those things is `array manipulation`

, or basically doing things to an `array`

that creates some kind of transformation.

Can you write a function that **takes two arrays as inputs** and returns to us their intersection? We can call the method `intersection`

. Let's return the intersection of the two inputs in the form of an array. As a reminder, the definition of an `intersection`

of two sets `A`

and `B`

is *the set containing all elements of A that also belong to B (or equivalently, all elements of B that also belong to A)*.

Note that all elements in the final result should be unique. Here's one example:

```
const nums1 = [1, 2, 2, 1];
const nums2 = [2, 2];
intersection(nums1, nums2);
// [2]
```

And here's another one:

```
const nums1 = [4,9,5];
const nums2 = [9,4,9,8,4];
intersection(nums1, nums2);
// [9, 4]
```

- Length of the array <=
`100000`

- The values in the array will be in the range
`-1000000000`

and`1000000000`

- Expected time complexity:
`O(n+m)`

where`n`

and`m`

are the lengths of the array. - Expected space complexity:
`O(max(n,m))`

.

You can see the full challenge with visuals at this link.

**Challenges**
• Asked over 3 years ago by Jake from AlgoDaily

haha what's up?

oh my gosh

Why the solution using `Set`

is `O(n)`

?

There are 2 inputs so we should have `n`

and `m`

, no?

Assume that `n`

is the size of *nums1*, and `m`

is *nums2*. We traverse nums2 with `filter()`

and in every iteration we traverse nums1 with `has()`

. So shouldn't it be `O(m*n)`

?

Correct me if I'm wrong, but I think I've found the answer:

*"Set objects must be implemented using [mechanisms] that, on average, provide access times that are sublinear on the number of elements in the collection"*

If I understand correctly, implementing `Set`

with *Disjoint Sets* data structure, for example, the complexity of `has()`

is `O(1)`

. Constructing the set from *nums1* with the `Set`

constructor is `O(n)`

.

(Look here for more details).

So we have *m* operations of `O(1)`

after constructing the set from *nums1*. That gives us complexity of `O(n+m)`

, which is roughly `O(n)`

assuming that *n* is the larger input.

oh my gosh

haha what's up?

`Set`

is `O(n)`

?

There are 2 inputs so we should have `n`

and `m`

, no?

Assume that `n`

is the size of *nums1*, and `m`

is* nums2*. We traverse nums2 with `filter()`

and in every iteration we traverse nums1 with `has()`

. So shouldn't it be `O(m*n)`

?

*"Set objects must be implemented using [mechanisms] that, on average, provide access times that are sublinear on the number of elements in the collection"*

If I understand correctly, implementing `Set`

with *Disjoint Sets* data structure, for example, the complexity of `has()`

is `O(1)`

. Constructing the set from *nums1* with the `Set`

constructor is `O(n)`

.

(Look here for more details).

So we have *m* operations of `O(1)`

after constructing the set from *nums1*. That gives us complexity of `O(n+m)`

, which is roughly `O(n)`

assuming that *n* is the larger input.

same for the [...filteredSet] i.e. the '...'?

can someone please explain what the (n) => set.has(n) part does?

That line consist of two parts. The filter returns a new array after a certain condition is passed. In this case >set.has(n). The has() method of a set returns true if a certain element is present in a set

Java & C++ solution, please?

[deleted]

[deleted]

Hi, the Java solution is already present, please change your language to Java to see. C++ will be coming soon!

It's a callback function passed to the Array.prototype.filter( ) method that is called sequentially on each element in the nums2 array. The n is a temp variable that holds each element in turn and is passed to Set.prototype.has( ) that returns a Boolean: true if the set contains n and false if not.

a python solution using dictionary:

def intersection (list1, list2):

# convert lists to dict

dict1 = {}

dict2 = {}

result = []

for item in list1:

dict1[item] = dict1.get(item, 0) + 1

for item in list2:

dict2[item] = dict2.get(item, 0) + 1

for key in dict1.keys():

if dict2.get(key, 0) > 0:

result.append(key)

return result

but the `(nums2.indexOf(num)`

is taking O(m), m = len(nums2) right?

and also the outer loop is going till len(nums1).

isn't it O(n*m)?

A python solution using a set since we are looking for values in both arrays but not how many times the occur .

1. We will put all the numbers from nums1 array inside the set ( Since sets only contain unique values,any duplicate will not be added)

2. We loop through the second array (nums2) and check the set (the lookup time for set is O(1) ), if it contains the current value in nums2 , we add it to the results array and delete it from the set.

3. Return the result array

The time complexity for this is O(n) . We have two seperate loops one for nums1 and the other for nums2

```

def intersection(nums1, nums2):

# fill this in

ans=set()

result=[]

for num in nums1:

ans.add(num)

for num in nums2:

if num in ans:

result.append(num)

ans.remove(num)

return result

Hi all! Thank you for your work guys!

- I would like to make some comments on testing. JUnit assertEquals expects parameters in the following order: 1. Expected 2. Actual

In your tests you put it vice versa which is not correct.

- Also in the arrayIntersection problem in the proposed tests you compare arrays via assertEquals which is not correct as it compares arrays by reference (and they cannot be identical).

You have to use assertArrayEquals().

Thanks!

Hi all, this is Rahat from AlgoDaily. Thank you all for pointing out the limitations in the lesson. I am now going to reference each points here.

@Leon, you are right in your answer! The complexity of almost all single operations (insertion, deletion, lookup) in most modern programming languages are `O(1)`

. And building a set out of array takes `O(n)`

(n=length of array).

And the final time complexity of this problem will be `O(n+m)`

.

And, `[...filteredSet]`

is a spread operator. It can be used to convert a set to an array.

`(n) => set.has(n)`

: This part is actually a lambda function. You can think this of a "portable" function, which takes a parameter `n`

, and returns boolean of whether `n`

is in the set or not.

@abrar, You are right. That solution was actually `O(n*m)`

and we fixed it now.

@George, We will update the assertions soon. But, here `assertArrayEquals`

will also not work. Because there is no instruction given on how the intersection array should be ordered, we much check the equality without the order. We will update this soon.

Also, we will be adding multiple languages for all problems in the platform. We are working on it and hope it will be added soon.

Thanks to everyone once again.