Найдите вставленный элемент в списке

#algorithm

#алгоритм

Вопрос:

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

Если у вас есть 2 списка

Список listB

Каждый из них имеет размер 1000 и содержит одинаковые элементы 1 — 1000. Если элемент N добавлен в список B, как вы можете определить значение этого элемента?

Я ответил правильно, сказав вычесть listB из listA, а остаток будет значением.

Затем он сказал, что, если у нас просто будет список B после добавления N . Как бы вы определили добавленное значение?

Я не смог ответить на это!!!! Я должен это знать, но я просто не могу об этом думать. Подсказка, которую он дал, заключалась в том, чтобы сделать что-то подобное, как я сделал в первой задаче.

Есть предложения?

1. Являются ли элементы {1,2,3 …. 1000}?

2. «размер 1000 и содержит одинаковые элементы от 1 до 1000»: означает ли это, что каждый список содержит каждое значение от 1 до 1000 ровно один раз, или это означает, что каждый список содержит 1000 элементов, каждый элемент находится в диапазоне от 1 до 1000, два списка содержат одинаковые элементы (возможно, нетв том же порядке), но могут быть ошибки? Если последний, то без наличия listA или возможности увидеть listB до добавления N, то, очевидно, невозможно узнать, какой элемент был добавлен в listB последним. Если первое, то проблема проста, например. просто вычтите 500500 из суммы элементов listB.

3. betterexplained.com/articles/…

Ответ №1:

Вы можете исключать XOR для обоих списков, и все, что является новым (N), у вас будет. Это ответ на первый вопрос.

Ответ №2:

Суммировать A в sumA . Вставьте новый элемент. Теперь суммируйте список в sumB . Вычесть sumA из sumB . Альт — это музыкальный инструмент.

1. Я знаю первый, но я не знаю второго. Сейчас у меня есть только listB.

2.Я понял вопрос, который вы не сохраняете listA и listB не различаете. Но вы должны что-то помнить, иначе это невозможно. Итак, суммируйте listA перед добавлением элемента, запомните сумму, затем суммируйте listB после добавления элемента. Кроме того, что сказал @SteveJessop — вы должны знать по формату вопроса, какова сумма listA .

Ответ №3:

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

Если список добавляет новый элемент, добавляя его, вы знаете, что новый элемент будет последним элементом в списке.

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

Если вы вставляете элемент в список, вы точно знаете, где находится элемент, потому что вы указали местоположение.

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

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

Ответ №4:

Учитывая, что большая часть того, что я делаю, основана на SQL:

 select * 
from listb b
left outer join lista a on (a.id = b.id)
where (a.id is null)