Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Java Новый топик    Ответить
Топик располагается на нескольких страницах: [1] 2 3 4 5 6 7 8 9 10 .. 46   вперед  Ctrl→
 Задачка для собеседования : ArrayList vs LinkedList  [new]
Atum1
Member

Откуда: СПБ
Сообщений: 1851
 		Всем добрый день!

Часто читаю в форумах что на собеседованиях задают вопросы из области :
"Расскажите про 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

Откуда: СПБ
Сообщений: 1851
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

Откуда: СПБ
Сообщений: 1851
Blazkowicz
Queue это реализация?

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


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

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

Queue и LinkedList имеют разные методы, требуется решить задачу - используя методы Queue , потом используя методы LinkedList , которых нет в интерфейсе Queue.
14 ноя 13, 12:00    [15126828]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
Atum1
Member

Откуда: СПБ
Сообщений: 1851
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

Откуда: Новокузнецк ► СПб
Сообщений: 1048
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

Откуда: СПБ
Сообщений: 1851
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

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

Откуда: СПБ
Сообщений: 1851
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
Сообщений: 7637
 		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

Откуда: СПБ
Сообщений: 1851
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

Откуда:
Сообщений: 4118
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

Откуда: Ростов-на-Дону
Сообщений: 5183
 		Atum1,

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

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

Откуда: СПБ
Сообщений: 1851
 		Сергей Арсеньев,

Задача из одной последовательности получить другую по формуле.

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

Откуда: СПБ
Сообщений: 1851
ivanra
Если это не сортировка, а перестановка элементов, то связанный однозначно быстрее
O(n2) 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(n2) arraylist.
O(n) linkedlist.

В идеальной сферической ЭВМ в вакууме?
14 ноя 13, 16:51    [15129909]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
mesier
Member

Откуда: Новокузнецк ► СПб
Сообщений: 1048
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

Откуда: СПБ
Сообщений: 1851
Ну наконец-то.. )

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

http://ideone.com/W3oqDP
14 ноя 13, 17:50    [15130364]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
mayton
Member

Откуда: loopback
Сообщений: 44901
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

Откуда: СПБ
Сообщений: 1851
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

Откуда: СПБ
Сообщений: 1851
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 .. 46   вперед  Ctrl→
Все форумы / Java Ответить