Блог

В интервью мне задали этот вопрос

LinkedList A имеет {1,2,3,4,5,6}

LinkedList B имеет {1,3,5}

Мне нужно было написать метод, который возвращал бы обратно набор, который не содержит повторяющихся элементов в списках A и B

результат {2,4,6}

Я написал решение, которое будет выполнять итерацию по первому списку, и если оно не существует во втором списке, то добавьте его в HashSet. Но нужно решение, которое работает лучше, чем предложенный алгоритм.

Для решения этой проблемы не упоминается ограничение пространства.

Определенно хотелось бы решение с использованием JDK, но предпочел бы решение, основанное на алгоритме

Огромное спасибо

Стандартное решение — перебирать первый список и помещать все в хэш-таблицу. Это линейное время, поскольку вставка в хэш-таблицу является постоянным временем.

Затем выполните цикл по второму списку и посмотрите, существует ли каждый элемент в хэш-таблице. Если он существует, удалите его из таблицы. В противном случае добавьте этот элемент в новый список.

Теперь добавьте все, что осталось в хэш-таблице, в новый список.

Эта вторая операция также линейна, поскольку поиск и удаление также постоянны для хэш-таблиц. Таким образом, общий алгоритм является линейным.

Дело в зависимости от того, на какую должность вы проходите собеседование. Вероятно, их заинтересовала ваша логика. Одно из возможных решений — начать с простого метода:

 public Set<Integer> killDuplicates(LinkedList<Integer> a0, LinkedList<Integer> a1) {
        Set<Integer> common = new HashSet<Integer>();
        common.addAll(a0); //one could pass thru constructor, no matter
        common.retainAll(a1);
        Set<Integer> result = new HashSet<Integer>();
        result.addAll(a0);
        result.addAll(a1);
        result.removeAll(common);
        return resu<
    }
  

Но все же в некоторых случаях это может быть значительно медленным, и есть очень много способов повысить скорость этого кода.
Одним из возможных решений является использование специальных структур для быстрого пересечения множеств.

Сортировка хороша, но поскольку у нас есть данные в LL, она будет использовать сортировку слиянием (дополнительная память, написанная псевдокодом, но не стесняйтесь задавать вопросы):

 public Set<Integer> killDuplicatesSorted(...) {
    //sort a0
    //sort a1
    Iterator i0 = a0.getIterator();
    Iterator i1 = a1.getIterator();
    while (i0 != end amp;amp; i1 != end) {
        if (i0.current == i1.current) {
            //skip presented in both
            i0.moveNext();
            i1.moveNext();
        } else if (i0.current < i1.current) {
            result.add(i0.current);
            i0.moveNext();
        } else {
            result.add(i1.current);
            i1.moveNext();
        }
    }
    while (i0 != end) {result.add(i0.current); i0.moveNext();}
    while (i1 != end) {result.add(i1.current); i1.moveNext();}
    return resu<
}
  

     Integer[] a1 = {1,2,3,4,5,6};
    Integer[] a2 = {1,3,5,8};

    LinkedList<Integer> ll1 = new LinkedList(Arrays.asList(a1));
    LinkedList<Integer> ll2 = new LinkedList(Arrays.asList(a2));

    Set<Integer> set1 = new HashSet<Integer>(ll1);
    Set<Integer> set2 = new HashSet<Integer>(ll2);
    set1.removeAll(ll2);
    set2.removeAll(ll1);
    set1.addAll(set2);

    System.out.println(set1);
  

removeAll() — это вспомогательная операция, а addAll() — объединение множеств.

В Scala, как описано ранее, используется внутренняя карта, затем циклы

 scala> val x = (1 to 6).toList
x: List[Int] = List(1, 2, 3, 4, 5, 6)

scala> val y = (1 to 5 by 2).toList
y: List[Int] = List(1, 3, 5)

scala> val result = x.diff(y).toSet
result: scala.collection.immutable.Set[Int] = Set(2, 4, 6)