C# Улучшенный алгоритм

Пример с использованием Except

var exclusions = new List<int>() { 1, 2, 3, 4 };
var newList = new List<int>() { 1, 2, 3, 4, 5, 56, 788, 9 };
IEnumerable<int>result = newList.Except(exclusions);

Ваш ответ - O (N ^ 2), потому что вам нужно искать в маленьком списке каждый элемент в большом списке. Возможно, вам повезет с использованием хэш-таблицы или отсортированного списка с двоичным поиском (в случае целых чисел / строк) и других способов уменьшить накладные расходы на поиск, которые, по крайней мере, приведут вас к O (N log N).

Обратите внимание: если размер маленького списка не похож на размер большого списка, ваше решение - O (N * M); вам нужно сначала оптимизировать обычно более крупный список. Если вы можете отсортировать первый список, это хороший выбор; если вам не разрешено изменять его, не забудьте отсортировать / хешировать второй список.

. Если не используется За исключением , и если вы хотите, чтобы ваше решение масштабировалось до больших списков, лучше всего было бы чтобы отсортировать второй список или создать из него хеш-таблицу, чтобы каждый элемент первого списка можно было легко идентифицировать во втором. (Так работает Кроме , более или менее.)

Я не верю, что опубликованный вами код работает. Стандартный массив не имеет метода contains. *

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

Как уже упоминалось, использование метода Except было бы более эффективным.

РЕДАКТИРОВАТЬ: Не видел, чтобы вы сказали C # 3.0. Моя вина. По-прежнему синтаксическая ошибка между items1 и items.

int[] items1={1,2,3,4}; 
List<int> newList = new List<int>() { 1, 2, 3, 4, 5, 56, 788, 9 };
newList.RemoveAll((int i) => { return items.Contains(i); });

1) Интервьюер ответил, что алгоритм, который я использовал, будет постепенно занимайте время, если предмет растет и попросил дать еще лучше и быстрее. Что было бы эффективным алгоритм?

Ваш items1 имеет длину m, а newlist имеет длину n. Поскольку вы выполняете линейный поиск по items1 для каждого элемента в newlist , ваше решение - O (n * m). С моей точки зрения, ваша реализация вполне приемлема, и нам, вероятно, не стоит беспокоиться об оптимизации до тех пор, пока она нам не понадобится.

Очевидно, однако, ее недостаточно для интервью. Хорошо, что "достаточно хорошо" для интервьюера? Кто знает. Теперь, если вы не возражаете против некоторого риска на собеседовании, вы можете попросить своего интервьюера более подробно рассказать о проблеме. Сообщите ему, что на скорость нашего кода влияет множество факторов и предположений, особенно выбор структуры данных:

• Предположим, вам требуется индексированный доступ к newList , а затем преобразование items1 в HashSet (с поиском O (1)) улучшит ваш алгоритм до O (n) времени, необходимого для перестроить массив.

• Предполагая, что newList - это «мешок» элементов, то есть нас не заботит порядок элементов в коллекции, а затем представляя newList хеш-набором позволяет нам удалить m элементов за время O (m).

• Предполагая, что нам нужно сохранить порядок вставки элементов в коллекцию, вы можете представить newList как LinkedList {T}, используя Словарь {T, LinkedListNode} в качестве таблицы поиска. Когда вы добавляете элемент в коллекцию, вы добавляете его в LinkedList, а затем добавляете вновь созданный узел в словарь. LinkedList сохраняет порядок вставки, а Словарь позволяет нам удалить m элементов за O (m) раз. Однако мы жертвуем индексированным доступом к коллекции.

• Предполагая, что newList хранит элементы в отсортированном порядке (это, похоже, не относится к предоставленному образцу кода, просто пошутите меня), большинство вариантов сбалансированные бинарные деревья удаляют m элементов за O (m log n), они также поддерживают обход отсортированного порядка O (n). Или, если вы в правильном настроении, пропускной список выполняет ту же работу, только глупее.

3) Он попросил меня привести пример они также поддерживают обход отсортированного порядка O (n). Или, если вы в правильном настроении, пропускной список выполняет ту же работу, только глупее.

3) Он попросил меня привести пример они также поддерживают обход отсортированного порядка O (n). Или, если вы в правильном настроении, пропускной список выполняет ту же работу, только глупее.

3) Он попросил меня привести пример для двустороннего закрытия? (Генерал, я осознает закрытие, что предназначено для Двустороннее закрытие ?, я ответил, что у меня есть когда-либо слышал этот термин, но он не

Я тоже никогда об этом не слышал, и Google, похоже, не показывает никаких соответствующих статей (кроме этой ветки, ни один из результатов на первых 5 страницах не относится к программированию или даже связан с компьютером). Интервьюер - идиот.