Задачка для собеседования : ArrayList vs LinkedList / Java / Sql.ru

Добро пожаловать в форум, Guest >> Войти \| Регистрация \| Поиск \| Правила \|			В избранное \| Подписаться
Все форумы / Java

Топик располагается на нескольких страницах: [1] 2 3 4 5 6 7 8 9 10 .. 38 вперед Ctrl→

Задачка для собеседования : ArrayList vs LinkedList [new]
Atum1 Member Откуда: СПБ Сообщений: 1834	Всем добрый день! Часто читаю в форумах что на собеседованиях задают вопросы из области : "Расскажите про ArrayList vs LinkedList" И если с теорией http://habrahabr.ru/post/162017/ у всех более менее все гладко , то вот с практикой возникают вопросы : Предлагаю такую задачку для решения и обсуждения : Есть список, (очередь элементов) нужно из него получить другой список (отсортировать элементы в другом порядке) : Пример простой : x(1),x(2),...,x(n) => x(1), x(n-1), x(2), x(n-2)... 1) Нужно написать код для Queue , LinkedList , ArrayList . 2) Без использования дополнительного списка (массива) - делать перестановки в этом же списке, массиве. 3) Оценить время, производительность , эффективность.
14 ноя 13, 11:34 [15126582] Ответить \| Цитировать Сообщить модератору

Re: Задачка для собеседования : ArrayList vs LinkedList [new]

Blazkowicz
Member

Откуда:
Сообщений: 24443

Atum1
то вот с практикой возникают вопросы :

С практикой тоже все просто. ArrayList в 99% случаев быстрее. То есть, чтобы LinkedList работал быстрее, нужно подогнать условия задачи под реализацию каждой из коллекций. В практике такого не встречается.

Atum1
1) Нужно написать код для Queue , LinkedList , ArrayList .

Queue это интерфейс а не реализация. Что мерять собрались?

14 ноя 13, 11:38 [15126636] Ответить | Цитировать Сообщить модератору

Re: Задачка для собеседования : ArrayList vs LinkedList [new]

Atum1
Member

Откуда: СПБ
Сообщений: 1834

Blazkowicz
С практикой тоже все просто

Нужен код для каждой реализации , вопрос на знание методов коллекций !

   List list = Arrays.asList("1", "2", "3", "4", "5");
   ArrayList<String> ain = new ArrayList<String>(list);
   LinkedList<String> lin = new LinkedList<String>(list);
   Queue<String> qin = new  LinkedList<String>(list);

14 ноя 13, 11:52 [15126771] Ответить | Цитировать Сообщить модератору

Re: Задачка для собеседования : ArrayList vs LinkedList [new]

Blazkowicz
Member

Откуда:
Сообщений: 24443

Atum1
Нужен код для каждой реализации

Queue это реализация?

Atum1
, вопрос на знание методов коллекций !

А документация на что?

Atum1
LinkedList<String> lin = new LinkedList<String>(list); Queue<String> qin = new LinkedList<String>(list);

Ожидается что эти двое как-то отличаются по производительности?

14 ноя 13, 11:55 [15126791] Ответить | Цитировать Сообщить модератору

Re: Задачка для собеседования : ArrayList vs LinkedList [new]

Atum1
Member

Откуда: СПБ
Сообщений: 1834

Blazkowicz
Queue это реализация? Ожидается что эти двое как-то отличаются по производительности?

Интерфейс. Будем точными.

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

Queue и LinkedList имеют разные методы, требуется решить задачу - используя методы Queue , потом используя методы LinkedList , которых нет в интерфейсе Queue.

14 ноя 13, 12:00 [15126828] Ответить | Цитировать Сообщить модератору

Re: Задачка для собеседования : ArrayList vs LinkedList [new]

Atum1
Member

Откуда: СПБ
Сообщений: 1834

Blazkowicz

Blazkowicz , Сколько Вам нужно времени чтобы написать такой алгоритм ?

Для проверки :

 List list1 = Arrays.asList("1");
 List list2 = Arrays.asList("1", "2");
 List list3 = Arrays.asList("1", "2", "3", "4", "5");
 List list4 = Arrays.asList("1", "2", "3", "4", "5", "6");

14 ноя 13, 12:07 [15126897] Ответить | Цитировать Сообщить модератору

Re: Задачка для собеседования : ArrayList vs LinkedList [new]

mesier
Member

Откуда: Новокузнецк ► СПб
Сообщений: 1038

Atum1
Есть список, (очередь элементов) нужно из него получить другой список (отсортировать элементы в другом порядке) : Пример простой : x(1),x(2),...,x(n) => x(1), x(n-1), x(2), x(n-2)...

А x(n) куда делся?

14 ноя 13, 12:20 [15127017] Ответить | Цитировать Сообщить модератору

Re: Задачка для собеседования : ArrayList vs LinkedList [new]

Atum1
Member

Откуда: СПБ
Сообщений: 1834

mesier

Atum1
Есть список, (очередь элементов) нужно из него получить другой список (отсортировать элементы в другом порядке) : Пример простой : x(1),x(2),...,x(n) => x(1), x(n-1), x(2), x(n-2)...

А x(n) куда делся?

подумайте :)

такой ряд был бы слишком простой :

x(1),x(2),...,x(n) => x(1), x(n), x(2), x(n-1)...

14 ноя 13, 12:24 [15127057] Ответить | Цитировать Сообщить модератору

Re: Задачка для собеседования : ArrayList vs LinkedList [new]
mesier Member Откуда: Новокузнецк ► СПб Сообщений: 1038	Звучит как "додумайте". )) Последний член больше не нужен (как скрипач)? Или что? У меня преподаватель был в институте, он категорически отказывался на консультациях решать задачи, написанные на листочке. Говорит, вдруг ты в одном символе ошибся, а я мучайся потом.. Так вот, мне кажется это как раз тот случай!
14 ноя 13, 12:46 [15127274] Ответить \| Цитировать Сообщить модератору

Re: Задачка для собеседования : ArrayList vs LinkedList [new]

Atum1
Member

Откуда: СПБ
Сообщений: 1834

mesier
У меня преподаватель был в институте, он категорически отказывался на консультациях решать задачи, написанные на листочке. Говорит, вдруг ты в одном символе ошибся, а я мучайся потом..

Зачем листочек? Перед Вами компьютер с Вашей любимой IDE :)

14 ноя 13, 13:03 [15127464] Ответить | Цитировать Сообщить модератору

Re: Задачка для собеседования : ArrayList vs LinkedList [new]
Andrew1411 Member Откуда: Москва Сообщений: 401	А зачем решать такие задачи? Что бы показать, что выбранная коллекция для этой задачи неоптимальна? В .Net подфоруме, пару месяцев назад один тип носился, в каждой теме твердил что связанный список быстрее всех остальных коллекций (бедняга, наверно тоже увидел лишь одну задачу). Я к чему это все, либо составляейте справочник типового решения разных задач на разных коллекциях - тогда поможете начинающим в выборе коллекции под задачу (а так же дадите "списать" решение под неудобный вариант использования коллекции), либо закопайте тему поглубже. Справочник, оформляйте как FAQ, либо вообще отдельным сайтом, с указанием ссылки.
14 ноя 13, 13:58 [15128115] Ответить \| Цитировать Сообщить модератору

Re: Задачка для собеседования : ArrayList vs LinkedList [new]
schwa Member Откуда: IT gulag Сообщений: 7634	in-place O(n^2) для arraylist O(n^3) для linkedlist не in-place O(n) arraylist. O(n^2) linkedlist. Queue в этой задаче делать нечего.
14 ноя 13, 14:32 [15128556] Ответить \| Цитировать Сообщить модератору

Re: Задачка для собеседования : ArrayList vs LinkedList [new]

Atum1
Member

Откуда: СПБ
Сообщений: 1834

schwa
in-place O(n^2) для arraylist O(n^3) для linkedlist не in-place O(n) arraylist. O(n^2) linkedlist. Queue в этой задаче делать нечего.

Отлично! Оценки есть ! Остался код !

Для затравки решение на Хаскель

http://ideone.com/JiG0Ut

Жду на java :)

14 ноя 13, 15:26 [15129128] Ответить | Цитировать Сообщить модератору

Re: Задачка для собеседования : ArrayList vs LinkedList [new]

Сергей Арсеньев
Member

Откуда:
Сообщений: 4113

Atum1
Пример простой : x(1),x(2),...,x(n) => x(1), x(n-1), x(2), x(n-2)...

Я правильно понял из
1,2,3,4
получить
1,3,2,2
и это называется сортировка?

14 ноя 13, 16:00 [15129434] Ответить | Цитировать Сообщить модератору

Re: Задачка для собеседования : ArrayList vs LinkedList [new]
Озверин Member Откуда: Ростов-на-Дону Сообщений: 4785	Atum1, я может чего то не понимаю, но это в самом деле сортировка?
14 ноя 13, 16:34 [15129779] Ответить \| Цитировать Сообщить модератору

Re: Задачка для собеседования : ArrayList vs LinkedList [new]
ivanra Member Откуда: Сообщений: 844	Если это не сортировка, а перестановка элементов, то связанный однозначно быстрее O(n²) arraylist. O(n) linkedlist.
14 ноя 13, 16:42 [15129839] Ответить \| Цитировать Сообщить модератору

Re: Задачка для собеседования : ArrayList vs LinkedList [new]
Atum1 Member Откуда: СПБ Сообщений: 1834	Сергей Арсеньев, Задача из одной последовательности получить другую по формуле. x(1),x(2),...,x(n) => x(1), x(n-1), x(2), x(n-2),..., x(n) Для 1,2,3,4 => 1,3,2,4
14 ноя 13, 16:43 [15129840] Ответить \| Цитировать Сообщить модератору

Re: Задачка для собеседования : ArrayList vs LinkedList [new]

Atum1
Member

Откуда: СПБ
Сообщений: 1834

ivanra
Если это не сортировка, а перестановка элементов, то связанный однозначно быстрее O(n²) arraylist. O(n) linkedlist.

Отлично! Нужен код. На любом известном Вам языке программирования .
Идеально на java.

Еще раз - есть последовательность элементов x(1),x(2),...,x(n)
нужно на ее основании получить последовательность с другим порядком - такой же длинны .

Но чтобы :
1) первый и последний элементы ее были на своих местах, x(1) ... x(n)
2) Остальные чередовались x(1), x(n-1), x(2), x(n-2) , x(3) , x(n-3) ... x(n)

14 ноя 13, 16:48 [15129879] Ответить | Цитировать Сообщить модератору

Re: Задачка для собеседования : ArrayList vs LinkedList [new]

Blazkowicz
Member

Откуда:
Сообщений: 24443

ivanra
Если это не сортировка, а перестановка элементов, то связанный однозначно быстрее O(n²) arraylist. O(n) linkedlist.

В идеальной сферической ЭВМ в вакууме?

14 ноя 13, 16:51 [15129909] Ответить | Цитировать Сообщить модератору

Re: Задачка для собеседования : ArrayList vs LinkedList [new]

mesier
Member

Откуда: Новокузнецк ► СПб
Сообщений: 1038

Atum1

Еще раз - есть последовательность элементов x(1),x(2),...,x(n)
нужно на ее основании получить последовательность с другим порядком - такой же длинны .

Но чтобы :
1) первый и последний элементы ее были на своих местах, x(1) ... x(n)
2) Остальные чередовались x(1), x(n-1), x(2), x(n-2) , x(3) , x(n-3) ... x(n)

Ну наконец-то.. )

14 ноя 13, 17:29 [15130218] Ответить | Цитировать Сообщить модератору

Re: Задачка для собеседования : ArrayList vs LinkedList [new]

Atum1
Member

Откуда: СПБ
Сообщений: 1834


Ну наконец-то.. )

Ура! Появилось первое решение для ArrayList vs LinkedList

http://ideone.com/W3oqDP

14 ноя 13, 17:50 [15130364] Ответить | Цитировать Сообщить модератору

Re: Задачка для собеседования : ArrayList vs LinkedList [new]

mayton
Member

Откуда: loopback
Сообщений: 38815

Atum1
Отлично! Оценки есть ! Остался код ! Для затравки решение на Хаскель http://ideone.com/JiG0Ut Жду на java :)

Решил блеснуть интеллектом?

Так слушай. Никто линкед-лист не сортирует. Нет в природе такой постановки.
В тех структурах данных где LL действительно существует, он вспомогательный
(LRU/MRU) и линкует обычно листовые узлы деревьев. Это его главное применение.

Любые попытки сортировать (и поддерживать в ражнированом порядке LL)
вызывают опухоль мозга у всего software. Структуры данных нужно
использовать в правильных use-cases а не др@чиtь их.

Прости модератор.

14 ноя 13, 18:12 [15130494] Ответить | Цитировать Сообщить модератору

Re: Задачка для собеседования : ArrayList vs LinkedList [new]

Atum1
Member

Откуда: СПБ
Сообщений: 1834

mayton
Так слушай. Никто линкед-лист не сортирует.

Мы не говорим о классической сортировке - где одно больше другого или меньше.

Будьте внимательны - мы говорим , если хотите о шафлере, который выстраивает коллекцию в определенном порядке.
был порядок x(1),x(2),...,x(n) стал x(1), x(n-1), x(2), x(n-2) ,..., x(n)

14 ноя 13, 18:20 [15130541] Ответить | Цитировать Сообщить модератору

Re: Задачка для собеседования : ArrayList vs LinkedList [new]

Atum1
Member

Откуда: СПБ
Сообщений: 1834

mayton

Так слушай. Никто линкед-лист не сортирует. Нет в природе такой постановки.
В тех структурах данных где LL действительно существует, он вспомогательный
(LRU/MRU) и линкует обычно листовые узлы деревьев. Это его главное применение.

Любые попытки сортировать (и поддерживать в ражнированом порядке LL)
вызывают опухоль мозга у всего software. Структуры данных нужно
использовать в правильных use-cases .

Есть конкретная задача - Вам нужно применив ваши знания коллекций решить ее и дать оценку вашего решения.

14 ноя 13, 18:22 [15130555] Ответить | Цитировать Сообщить модератору

Re: Задачка для собеседования : ArrayList vs LinkedList [new]
super-code Member Откуда: Сообщений: 244	Atum1, я решил на C# :) сложность ArrayList - N^2, LinkedList - N
14 ноя 13, 18:43 [15130664] Ответить \| Цитировать Сообщить модератору

Топик располагается на нескольких страницах: [1] 2 3 4 5 6 7 8 9 10 .. 38 вперед Ctrl→

Все форумы / Java

Ссылка на сообщение

Ссылка (включая название темы)

Ссылка (URL)