Всем добрый день!

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

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

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

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

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

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

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

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

Blazkowicz

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

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

mesierAtum1 Есть список, (очередь элементов) нужно из него получить другой список (отсортировать элементы в другом порядке) :
Пример простой :
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)...

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

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

schwain-place

O(n^2) для arraylist
O(n^3) для linkedlist

не in-place

O(n) arraylist.
O(n^2) linkedlist.

Queue в этой задаче делать нечего.

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

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

http://ideone.com/JiG0Ut

Жду на java :)

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

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

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

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)

Ну наконец-то.. )
Ура! Появилось первое решение для ArrayList vs LinkedList

http://ideone.com/W3oqDP

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


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

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

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

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


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