|
|
|
Итератор по 3ем спискам
|
|||
|---|---|---|---|
|
#18+
Добрый день, хочу поделиться с вами тестовым заданием, которое я на днях получил. Дано 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. Но посмотрев на нее программист потенциального работодателя даже не захотел со мной разговаривать, без объяснения причин. Соответственно, у меня вопрос к знатокам: Существует более изящное решение приведенной мной задачи? Поделитесь своими соображениями, пожалуйста). ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.03.2012, 18:49 |
|
||
|
Итератор по 3ем спискам
|
|||
|---|---|---|---|
|
#18+
abc_da, а как List-е реализована операция взятия i-го элемента? если не О(1), то твое решение плохо. тебе нужно было итераторами воспользоваться. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.03.2012, 19:37 |
|
||
|
Итератор по 3ем спискам
|
|||
|---|---|---|---|
|
#18+
Условия задачи о реализации List'а ничего не говорят. Можно подробнее про итераторы? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.03.2012, 19:48 |
|
||
|
Итератор по 3ем спискам
|
|||
|---|---|---|---|
|
#18+
Здесь трудно что-то определённо сказать. Как имплементируется List - непонятно. Действительно если это список - то луче брать его через итератор а не через индекс. И как-то странно используется .equals(). Возможно эту часть надо было как-то по другому реализовать. И можно было попробовать на 1 итерации накапливать индекс наименьшего, чтобы на последующих делать меньше проверок. Вообще этот исходник (и задание) - предмет спора. Не суть даже важно как ты написал. Очень мало разработчиков напишут это одинаково. На собеседовании важнее доказать свою правоту и свою точку зрения на постановку. Вообще не стоит переживать из за такого работодателя. Видно что он очень торопился уйти в отказ без объяснений. А значит и для тебя не очень ценен. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.03.2012, 19:53 |
|
||
|
Итератор по 3ем спискам
|
|||
|---|---|---|---|
|
#18+
abc_daУсловия задачи о реализации List'а ничего не говорят.т.е. мы не можем предположить, что есть быстрый доступ по индексу. Надо просто сравнивать (и сохранять) текущие значения итераторов для каждого списка, а не индексы. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.03.2012, 19:57 |
|
||
|
Итератор по 3ем спискам
|
|||
|---|---|---|---|
|
#18+
mayton, Мои чувства не задеты, задето моё любопытство. Дело в том, что я не вижу другого(принципиально) подхода к решению этой задачи. Но у меня с алгоритмами туго, вот я и спрашиваю, мало ли кто придумает изящное решение. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.03.2012, 20:02 |
|
||
|
Итератор по 3ем спискам
|
|||
|---|---|---|---|
|
#18+
abc_da, дело не в изяществе, а в том, что ты list.get(i) использовал, что в случае реализации на основе связного списка ну совсем некстати. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.03.2012, 20:11 |
|
||
|
Итератор по 3ем спискам
|
|||
|---|---|---|---|
|
#18+
Ок, теперь я, наконец, понял о чем идет речь). Спасибо. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.03.2012, 20:15 |
|
||
|
Итератор по 3ем спискам
|
|||
|---|---|---|---|
|
#18+
abc_da, Код: java 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.03.2012, 20:30 |
|
||
|
Итератор по 3ем спискам
|
|||
|---|---|---|---|
|
#18+
Усман. В задании сказано об уникальности элементов но ничего о их диапазонах. Usman Код: java 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.03.2012, 21:27 |
|
||
|
Итератор по 3ем спискам
|
|||
|---|---|---|---|
|
#18+
maytonВ задании сказано об уникальности элементов но ничего о их диапазонах. Так и есть. Вы имели ввиду долгий перебор/сравнение при длинных интервалах? <- кстати, о времени выполнения алгоритма тоже ничего не сказано Давайте оптимизировать вместе :) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.03.2012, 21:57 |
|
||
|
Итератор по 3ем спискам
|
|||
|---|---|---|---|
|
#18+
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. Для интересующихся прикладываю к сообщению проект на 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 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.03.2012, 21:59 |
|
||
|
|

start [/forum/topic.php?fid=16&tid=1342387]: |
0ms |
get settings: |
8ms |
get forum list: |
11ms |
check forum access: |
2ms |
check topic access: |
2ms |
track hit: |
181ms |
get topic data: |
8ms |
get forum data: |
2ms |
get page messages: |
36ms |
get tp. blocked users: |
2ms |
| others: | 207ms |
| total: | 459ms |

| 0 / 0 |
