Прежде всего: чтобы определить пересечение двух наборов, вам абсолютно необходимо просмотреть все записи хотя бы одного из двух наборов (чтобы выяснить, находится ли он в другом наборе).Вокруг нет магии, которая могла бы сказать вам, что менее чем за O (мин (размер (s1), размер (s2)) . Период.
Следующее, что нужно сказать интервьюеру:«1 миллион записей. Вы, должно быть, шутите. Это 2019 год. Любая приличная часть оборудования хрустит двумя миллионами менее чем за секунду».
Затем вы кратко упоминаете, что существуют различные встроенные способырешить эту проблему, а также различные сторонние библиотеки. Но вы избежите ошибки, которую допускают два других ответа: указание на библиотеку, которая вычисляет пересечение, равно вовсе что-то, что вы продаете как «решение» этогоВопрос.
Вы видите, что касается кодирования: интерфейс Java-набора имеет easy решение для этого: s1.retainAll(s2) вычисляет объединение двух наборов, так как удаляет все элементы из s1, которыене в s2.
Очевидно, вы должны упомянуть в интервью, что это изменит s1.
В случае, если требование не изменить s1 илиs2, ваше решениежизнеспособный путь, и нет ничего, что можно сделать с затратами времени выполнения.Если это все, вы можете вызвать size() для обоих наборов и итерировать тот, который имеет меньше записей.
В качестве альтернативы, вы можете сделать
Set<String> result = new HashSet<>(s1);
return result.retain(s2);
, но вВ конце вы должны перебрать один набор и для каждого элемента определить, находится ли он во втором наборе.
Но, конечно, реальный ответ на такие вопросы всегда всегда показывает интервьюеру, что вы в состоянии разбить проблему на различные ее аспекты.Вы обрисовываете основные ограничения, обрисовываете различные решения и обсуждаете их плюсы и минусы.Я, например, ожидал, что вы сядете и, возможно, напишите такую программу:
public class Numbers {
private final static int numberOfEntries = 20_000_000;
private final static int maxRandom = numberOfEntries;
private Set<Integer> s1;
private Set<Integer> s2;
@Before
public void setUp() throws Exception {
Random random = new Random(42);
s1 = fillWithRandomEntries(random, numberOfEntries);
s2 = fillWithRandomEntries(random, numberOfEntries);
}
private static Set<Integer> fillWithRandomEntries(Random random, int entries) {
Set<Integer> rv = new HashSet<>();
for (int i = 0; i < entries; i++) {
rv.add(random.nextInt(maxRandom));
}
return rv;
}
@Test
public void classic() {
long start = System.currentTimeMillis();
HashSet<Integer> intersection = new HashSet<>();
s1.forEach((i) -> {
if (s2.contains(i))
intersection.add(i);
});
long end = System.currentTimeMillis();
System.out.println("foreach duration: " + (end-start) + " ms");
System.out.println("intersection.size() = " + intersection.size());
}
@Test
public void retainAll() {
long start = System.currentTimeMillis();
s1.retainAll(s2);
long end = System.currentTimeMillis();
System.out.println("Retain all duration: " + (end-start) + " ms");
System.out.println("intersection.size() = " + s1.size());
}
@Test
public void streams() {
long start = System.currentTimeMillis();
Set<Integer> intersection = s1.stream().filter(i -> s2.contains(i)).collect(Collectors.toSet());
long end = System.currentTimeMillis();
System.out.println("streaming: " + (end-start) + " ms");
System.out.println("intersection.size() = " + intersection.size());
}
@Test
public void parallelStreams() {
long start = System.currentTimeMillis();
Set<Integer> intersection = s1.parallelStream().filter(i -> s2.contains(i)).collect(Collectors.toSet());
long end = System.currentTimeMillis();
System.out.println("parallel streaming: " + (end-start) + " ms");
System.out.println("intersection.size() = " + intersection.size());
}
}
Первое замечание: я решил запустить с 20 миллионами записей.Я начал с 2 миллионов, но все три теста будут работать намного ниже 500 мс.Вот распечатка для 20 миллионов на моем Mac Book Pro:
foreach duration: 9304 ms
intersection.size() = 7990888
streaming: 9356 ms
intersection.size() = 7990888
Retain all duration: 685 ms
intersection.size() = 7990888
parallel streaming: 6998 ms
intersection.size() = 7990888
Как и ожидалось: все пересечения имеют одинаковый размер (потому что я посеял генератор случайных чисел, чтобы получить сопоставимые результаты).
И сюрприз: модификация s1 на месте ... безусловно, самый дешевый вариант.Скорость потоковой передачи превосходит коэффициент , равный 10. Также обратите внимание: параллельная потоковая передача здесь происходит быстрее.При работе с 1 миллионом записей поток последовательный был быстрее.
Поэтому я изначально упомянул упоминание "1 миллион записей не является проблемой производительности".Это очень важное утверждение, поскольку оно говорит интервьюеру, что вы не из тех людей, которые тратят часы на микрооптимизацию несуществующих проблем с производительностью.