Алгоритм для определения того, являются ли 2 массива непересекающимися

Question

Дайте рандомизированный ожидаемый алгоритм линейного времени с использованием идеальных хеш-функций, который определяет , являются ли два массива A [1..n] и B [1..n] непересекающимися, т.е. ни один элемент из A также не является элементом B.

Может ли кто-нибудь показать мне, как это сделать или даже начать думать об этом?

Answer 1

for element in a: 
    hasha{element} = 1 

for element in b: 
    if hasha{element} == 1: 
    print element "found in both" 

Время: O (LEN (а) + Len (б))