Интервью: списки пересечения с ограниченной памятью

Question

Вам даны два набора целых чисел, размеры M и N с M

Answer 1

Используя алгоритм сортировки на месте , чтобы сначала отсортировать оба списка.

Как только оба M и N отсортированы, вычисление пересечения похоже на гонку. Поместите два маркера a и b в начале каждого списка. Делайте эти шаги, пока какой-либо маркер не достигнет конца списка. В псевдокоде:

until a > M.size or b > N.size
    if M[a] < N[b]
        a++
        continue
    if N[b] < M[a]
        b++
        continue
    print M[a] // common element
    // Advance both indexes to avoid infinite loop
    a++
    b++

При наличии достойного алгоритма сортировки на месте сложность этого будет O(nlogn).

Answer 2

Я думаю, что для этой цели можно использовать набор битов. Набор битов использует только один бит на целое число.Надеюсь это поможет.

BitSet b=new BitSet();//set 1 with {10,20,30}
BitSet c=new BitSet();//set 2 with {20,30,1,2}
b.set(10);
b.set(20);
b.set(30);
c.set(20);
c.set(30);
c.set(1);
c.set(2);
b.and(c);
System.out.println(b);//{20, 30}

Answer 3

для каждой части k / 2 в M

 for each k/2 subpart of N 
        sort the M-subpart & N-subpart
        find intersection of both the subparts 
        search each element of the result and store it if it already not

присутствует

Answer 4

взять K / 2 элементов из M и K / 2 элементов из N. Сортировать M-подмножество и N-подмножество.Теперь пересечение тривиально.Запишите пересечение, отбросьте элементы пересечения, запишите левые элементы.Продолжите со всеми другими частями K / 2 M и N. Теперь у вас есть некоторые общие элементы в третьем файле и некоторые частично отсортированные списки.Теперь для каждого K / 2 (за вычетом удаленных элементов) списков M и N сравните их, чтобы эффективно найти пересечение.

(Вы также можете добавить дополнительные раунды слияния 2 M-подмножеств и N-подмножеств в скоростьпересечение вверх).

Ура!

---

Пример выполнения:

Ok let's take 2 lists of 9 integers with values between 0 and 9.
These lists will be
4 2 5 1 9 2 9 0 2
and
4 7 4 0 8 6 2 6 5
(generated by rand())

So we take two sublists : 
4 2 5 and 4 7 4

Let's sort them using quicksort
4 2 5
i   j <- two pointers
pivot = [0] = 4

increase i until it's greater than pivot = 4
i and j now points to 5
decrease j until it's smaller than pivot = 4
j points to 2
i is greater than j, thus except for pivot, the list is sorted.
Swap [0] and [j] to finish sorting
2 4 5.

Except for pivot + i + j, no extra allocation was needed (For 3 elements it's hard to believe, see any quicksort applet to have a better understanding).
Thus, from an algorithmic point of view, pivot + i + j are constant and can be neglected (in fact you would do memory - algorithm size to have the real K).

Do the same for the second set
(4 4 7)

Now with two pointers to the lists initialized to the start of the sublists, compare the pointed values.
2 - 4
Increase first sublist's pointers
4 - 4
Equal -> a first common element, remove them from list [2 5] and [4 7]
5 - 4
Increase second pointer
5 - 7
Increase first pointer
End of this sublists.

Dump this to original lists.
Do this for any other sublists
[1 9 2] and [0 8 6] -> [1 2 9] [0 6 8] -> no intersection
[9 0 2] and [2 6 5] -> [0 9 E] [5 6 E] -> [2]

Now we have : 
[2 5 E 1 2 9 0 9 E] and [4 7 E 0 6 8 5 6 E] with E for empty elements.
Now compare subsets with other subsets (sorted) (excepted for already processed sets (same index))
[2 5 E] with [0 6 8] and [6 5 E] -> becomes [2 E E] and [0 6 8] [6 E E]  (intersection [5])
Then
[1 2 9] with [4 7 E] and [6 E E] -> [1 2 9] and [4 7 E] [6 E E] (no intersection)
Then
[0 9 E] with [4 7 E] and [0 6 8] -> [9 E E] and [4 7 E] [6 8 E] (intersection [0])
End : 
[2 E E 1 2 9 9 E E] [4 7 E 6 8 E 6 E E] with common elements [4 2 5 0]

Answer 5

1. Разделить N на n частей L (L
2. Одновременно читать число М, сравнивать это число со всеми числами в текущей части
3. Если вы найдете совпадение, запишите его в файл

Answer 6

Соединение с вложенным циклом займет минимум памяти. Для каждой строки в файле 1 вы загружаете каждую строку в файле 2 и сравниваете ее. Тогда, я думаю, вы отметите попадания в файле 1.

В зависимости от размеров файлов может быть более эффективно сначала отсортировать один из файлов (что можно сделать с минимальным объемом памяти). Многое зависит от объема памяти, с которым вам приходится играть.