Given two (huge) sets, what is an efficient way to find their intersection?

Question

grk · Accepted Answer

hey can you please share the answer with us? 
I have 2 ans: 
1. sort both the sets and iterate to find intersections. (nlogn)
2. use hash. (n)

Please let me know if it could be done in a better way. 
Thanks!

PB · Answer

I think "huge" is an indication that using a hash set approach would be untenable, the idea being that you'd run out of RAM. The n log n approach seems correct to me.

Nani · Answer

Dont u think nlogn is larger than n since in data structures, the base of the log is always 2

person · Answer

he meant untenable in space. in time of course you cannot beat the hash

Amazon

Amazon Interview Question

Interview Answers

Want the inside scoop on your own company?

Bowls

Followed companies

Job searches