Header logo.
Tonghe's Notes

A bug in CRA and time complexity of list and set operations

Here are a few things I noticed in week 7.

I was creating a React app using create-react-app and ran into this error:

You are running 'create-react-app' 4.0.3, which is behind the latest release (5.0.0).

After googling around I saw a workaround by installing v5 locally.

Yet a better workaround is:

npx create-react-app@5.0.0 app-name

Update on Feb 24

Should have read the thread more closely, because clearing npx cache should do: npx clear-npx-cache.

I was reading Ace the Data Science Interview and there's a chapter about coding.

One easy coding problem reads:

Given two arrays, write a function to get the intersection of the two.

I guess to show your ingenuity, you are not supposed to use sets, which are native to Python.

The most naïve idea is to run a doubly nested for loop to check each item in arr_n against each item in arr_m. That way, the time complexity would be O(n*m).

A twist on this idea is to run a for loop to iterate through the shorter array (arr_n) and check if arr_n[i] exists in the longer array (arr_m). By doing so, the time complexity is also O(n*m) because the average case time complexity to find an item in arr_m is O(m). (I had mistakenly thought checking existence of an item costs O(1).)

A simpler solution is using sets. The official solution given in the book first converts the two arrays to sets. Then checks which items in the shorter set exist in the longer set by doing this:

[x for x in set_n if x in set_m] (time complexity O(n))

The time complexity of this solution in total is O(n) + O(m + n), because converting lists to sets costs O(n) too, and we have two arrays here. Less than O(n*m).

At first I wondered why they didn't directly use set intersection. I guess that's because converting the resulting set back to a list would cost another O(len(intersection)).