Напишите код, который позволяет найти минимальное расстояние (выражаемое количеством слов) между любыми двумя словами в файле

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

Достаточно ли будет O(n) времени?

Сколько памяти понадобится для решения?

Давайте считать, что порядок появления слов word1 и word2 не важен. Этот вопрос нужно согласовать с интервьюером. Если порядок слов имеет значение, нужно будет модифицировать приведенный далее код.

Чтобы решить эту задачу, достаточно будет прочитать файл только один раз. При этом мы сохраним информацию о том, где находились последние word1 или word2 в lastPosWord1 и lastPosWord2 и при необходимости обновляем значение min, а затем обновляем lastPosWord1. Аналогичным образом мы действуем и с word2. По окончании работы алгоритма в нашем распоряжении окажется правильное значение min (минимальное расстояние).

Приведенный далее код иллюстрирует этот алгоритм:

			public int shortest(String[] words, String word1, String word2) {
	int min = Integer.MAX_VALUE;
	int lastPosWord1 = -1;
	int lastPosWord2 = -1;
	for (int i = 0; i < words.lenght; i++) {
		String currentWord = words[i];
		if (currentWord.equals(word1)) {
			lastPosWord1 = i;
			// Закомментируйте 3 следующие строки, если порядок слов
			// имеет значение
			int distance = lastPosWord1 - lastPosWord2;
			if (lastPosWord2 >= 0 && min > distance) {
				min = distance;
			}
		} else if (currentWord.equals(word2)) {
			lastPosWord2 = i;
			int distance = lastPosWord2 - lastPosWord1;
			if (lastPosWord >= 0 && min > distance) {
				min = distance;
			}
		}
	}
	return min;
}
		

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

Существует несколько способов вычислить минимальную разницу между значениями из listA и listB. Давайте рассмотрим списки:

listA: {1, 2, 9, 15, 25}
listB: {4, 10, 19}

Можно объединить списки в один отсортированный список, но связать каждое значение с исходным списком. Эта операция выполняется «обертыванием» каждого значения в класс, у которого будет две переменные экземпляра: data (для хранения фактического значения) и listNumber.

list: {1a, 2a, 4b, 9a, 10b, 15a, 19b, 20a}

Расчет минимального расстояния превращается в поиск минимального расстояния между двумя последовательными числами, у которых разные теги списка. В этом случае решением будет 1 (расстояние между 9a и 10b).

Разбор задачи по книге «Карьера программиста. Как устроиться на работу в Google, Microsoft или другую ведущую IT-компанию»