powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Итератор по 3ем спискам
13 сообщений из 13, страница 1 из 1
Итератор по 3ем спискам
    #37695758
abc_da
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Добрый день, хочу поделиться с вами тестовым заданием, которое я на днях получил.

Дано 3 List'а положительных целых чисел, упорядоченных по возрастанию. При этом каждое число на все 3 списка содержится в единственном экземпляре(если в 1ом списке есть 3-ка, значит, в других 2х списках ее нет). Проиллюстрирую примером:
List1 = 2, 4, 10, 14, 20
List2 = 3, 7, 11, 12
List3 = 5, 6, 9, 18, 25, 40

Задача: реализовать итератор(метод GetNext), который будет возвращать следующее по порядку возрастания число на все 3 List'а. Сливать List'ы в один нельзя, итератор должен работать с тремя List'ами отдельно.

Результат для данного примера:
GetNext(): 2
GetNext(): 3
GetNext(): 4
GetNext(): 5
GetNext(): 6
GetNext(): 7
GetNext(): 9
GetNext(): 10
GetNext(): 11
GetNext(): 12
GetNext(): 14
GetNext(): 18
GetNext(): 20
GetNext(): 25
GetNext(): 40


Выглядит не слишком сложно, мною была предложена следующая реализация итератора:
Код: java
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
	// индексы текущих элементов.
	private int i1,i2,i3;

	public Integer GetNext() {

		Integer next1 = (i1 < list1.size()) ? list1.get(i1) : Integer.MAX_VALUE;
		Integer next2 = (i2 < list2.size()) ? list2.get(i2) : Integer.MAX_VALUE;
		Integer next3 = (i3 < list3.size()) ? list3.get(i3) : Integer.MAX_VALUE;
		
		
		// min(next1, next2, next3)
		Integer next = Math.min(next1, Math.min(next2, next3));
		
		if(next.equals(Integer.MAX_VALUE)) {
			throw new NoSuchElementException();
		} else if(next.equals(next1)) {
			i1++;
		} else if(next.equals(next2)) {
			i2++;
		} else if(next.equals(next3)) {
			i3++;
		}
		
		return next;
	}



Но посмотрев на нее программист потенциального работодателя даже не захотел со мной разговаривать, без объяснения причин. Соответственно, у меня вопрос к знатокам:
Существует более изящное решение приведенной мной задачи? Поделитесь своими соображениями, пожалуйста).
...
Рейтинг: 0 / 0
Итератор по 3ем спискам
    #37695806
Фотография ZyK_BotaN
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
abc_da,

а как List-е реализована операция взятия i-го элемента?
если не О(1), то твое решение плохо.
тебе нужно было итераторами воспользоваться.
...
Рейтинг: 0 / 0
Итератор по 3ем спискам
    #37695825
abc_da
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Условия задачи о реализации List'а ничего не говорят.

Можно подробнее про итераторы?
...
Рейтинг: 0 / 0
Итератор по 3ем спискам
    #37695827
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Здесь трудно что-то определённо сказать. Как имплементируется List - непонятно.
Действительно если это список - то луче брать его через итератор а не через
индекс. И как-то странно используется .equals(). Возможно эту часть
надо было как-то по другому реализовать. И можно было попробовать
на 1 итерации накапливать индекс наименьшего, чтобы на последующих
делать меньше проверок. Вообще этот исходник (и задание) - предмет
спора. Не суть даже важно как ты написал. Очень мало разработчиков
напишут это одинаково. На собеседовании важнее доказать свою правоту
и свою точку зрения на постановку.

Вообще не стоит переживать из за такого работодателя. Видно что
он очень торопился уйти в отказ без объяснений. А значит и для тебя
не очень ценен.
...
Рейтинг: 0 / 0
Итератор по 3ем спискам
    #37695834
Фотография Яростный Меч
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
abc_daУсловия задачи о реализации List'а ничего не говорят.т.е. мы не можем предположить, что есть быстрый доступ по индексу. Надо просто сравнивать (и сохранять) текущие значения итераторов для каждого списка, а не индексы.
...
Рейтинг: 0 / 0
Итератор по 3ем спискам
    #37695841
abc_da
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
mayton,

Мои чувства не задеты, задето моё любопытство. Дело в том, что я не вижу другого(принципиально) подхода к решению этой задачи. Но у меня с алгоритмами туго, вот я и спрашиваю, мало ли кто придумает изящное решение.
...
Рейтинг: 0 / 0
Итератор по 3ем спискам
    #37695845
Фотография Яростный Меч
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
abc_da,

дело не в изяществе, а в том, что ты list.get(i) использовал, что в случае реализации на основе связного списка ну совсем некстати.
...
Рейтинг: 0 / 0
Итератор по 3ем спискам
    #37695854
abc_da
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Ок, теперь я, наконец, понял о чем идет речь). Спасибо.
...
Рейтинг: 0 / 0
Итератор по 3ем спискам
    #37695870
Фотография Usman
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
abc_da,

Код: java
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
static int[] L1 = { 2, 4, 10, 14, 20 };
static int[] L2 = { 3, 7, 11, 12 };
static int[] L3 = { 5, 6, 9, 18, 25, 40 };	

public static void GetNext() {
	for (int n = 0, i1 = 0, i2 = 0, i3 = 0; i1 < L1.length || i2 < L2.length || i3 < L3.length; n++) {
		if (i1 < L1.length && L1[i1] == n) { out.format("L1[%d] = %d\n", i1, L1[i1]); i1++; }
		if (i2 < L2.length && L2[i2] == n) { out.format("L2[%d] = %d\n", i2, L2[i2]); i2++; }
		if (i3 < L3.length && L3[i3] == n) { out.format("L3[%d] = %d\n", i3, L3[i3]); i3++; }
	}
}
...
Рейтинг: 0 / 0
Итератор по 3ем спискам
    #37695940
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Усман. В задании сказано об уникальности элементов но ничего о их диапазонах.
Usman
Код: java
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
static int[] L1 = { 2, 4, 10, 14, 20, 536870911 };
static int[] L2 = { 3, 7, 11, 12, 1073741823};
static int[] L3 = { 5, 6, 9, 18, 25, 40, 2147483647 };	

public static void GetNext() {
	for (int n = 0, i1 = 0, i2 = 0, i3 = 0; i1 < L1.length || i2 < L2.length || i3 < L3.length; n++) {
		if (i1 < L1.length && L1[i1] == n) { out.format("L1[%d] = %d\n", i1, L1[i1]); i1++; }
		if (i2 < L2.length && L2[i2] == n) { out.format("L2[%d] = %d\n", i2, L2[i2]); i2++; }
		if (i3 < L3.length && L3[i3] == n) { out.format("L3[%d] = %d\n", i3, L3[i3]); i3++; }
	}
}
...
Рейтинг: 0 / 0
Итератор по 3ем спискам
    #37695966
Фотография Usman
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonВ задании сказано об уникальности элементов но ничего о их диапазонах. Так и есть.
Вы имели ввиду долгий перебор/сравнение при длинных интервалах? <- кстати, о времени выполнения алгоритма тоже ничего не сказано
Давайте оптимизировать вместе :)
...
Рейтинг: 0 / 0
Итератор по 3ем спискам
    #37695968
abc_da
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Usman,

У вас не совсем итератор получился, цикл должен быть внешним по отношению к вызову метода GetNext(), но подход вполне себе нестандартный :).

Кстати, вот вариант с использованием итераторов:
Код: java
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
	// текущие значения итераторов
	private Integer v1, v2, v3;

	public Integer next() {
		v1 = (v1 == null && iterator1.hasNext()) ? iterator1.next() : v1;
		v2 = (v2 == null && iterator2.hasNext()) ? iterator2.next() : v2;
		v3 = (v3 == null && iterator3.hasNext()) ? iterator3.next() : v3;
		
		// min(next1, next2, next3)
		Integer v12 = min(v1, v2);
		Integer next = min(v12, v3);
		
		if (next == null) {
			throw new NoSuchElementException();
		} else if (next.equals(v1)) {
			v1 = null;
		} else if (next.equals(v2)) {
			v2 = null;
		} else if (next.equals(v3)) {
			v3 = null;
		}

		return next;
	}




Для интересующихся прикладываю к сообщению проект на java для Eclipse, в котором содержится 2 реализации итератора и Test case, иллюстрирующий, что LinkedList.get() для данной задачи - это действительно очень плохо).
У меня выдает вот такие цифры при длинне каждого списка ~35000 чисел:
авторList approx size: 50000 - 30%
Iterating over ArrayList implementation...
IndexIterator: 67msec
ValueIterator: 23msec

Iterating over LinkedList implementation...
IndexIterator: 21252msec
ValueIterator: 16msec
...
Рейтинг: 0 / 0
Итератор по 3ем спискам
    #37695970
abc_da
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
UsmanВы имели ввиду долгий перебор/сравнение при длинных интервалах? <- кстати, о времени выполнения алгоритма тоже ничего не сказано


Действительно
...
Рейтинг: 0 / 0
13 сообщений из 13, страница 1 из 1
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Итератор по 3ем спискам
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]