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

Откуда: loopback
Сообщений: 40558
Atum1
Есть конкретная задача - Вам нужно применив ваши знания коллекций решить ее и дать оценку вашего решения.

Да. А еще на собеседовании можно себя позиционировать как кодера или как постановщика задач
или архитектора. И не все задачи требуют решения в лоб.

Иногда имеет смысл смотреть в корень проблемы. А сортировка - это не ТЗ. Это артефакт.
14 ноя 13, 18:50    [15130710]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
mesier
Member

Откуда: Новокузнецк ► СПб
Сообщений: 1044
Пойдёт так? )))
Про сложность я, правда, ниче не знаю, извини..

public class SomeReplacementClass {

	static Collection<Integer> col = Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8);
	
	public static void main(String[] args) {
		LinkedList<Integer> myList = new LinkedList<Integer>(col);
        Integer t;
        for (int i = 0; i < col.size() - 2; i++) {
            Iterator<Integer> dIterator = myList.descendingIterator();
            if (dIterator.hasNext())
                dIterator.next();
            if (dIterator.hasNext()) {
                t = (Integer) dIterator.next();
                if (dIterator.hasNext()) {
                    dIterator.remove();
                    myList.add(i + 1, t);
                    i++;
                }
            }
        }
        for (Integer elem : myList)
            System.out.print(elem + " ");
	}
}
14 ноя 13, 19:17    [15130895]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
mesier
Member

Откуда: Новокузнецк ► СПб
Сообщений: 1044
Для ArrayList завтра подумаю.
14 ноя 13, 19:18    [15130900]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
mesier
Member

Откуда: Новокузнецк ► СПб
Сообщений: 1044
Atum1
Ну наконец-то.. )

Ура! Появилось первое решение для ArrayList vs LinkedList
http://ideone.com/W3oqDP

"Так и я могу!" (с)Промокашка )))

Было же условие. Отменили??
2) Без использования дополнительного списка (массива) - делать перестановки в этом же списке, массиве.
14 ноя 13, 19:49    [15131030]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
ivanra
Member

Откуда:
Сообщений: 848
Blazkowicz
ivanra
Если это не сортировка, а перестановка элементов, то связанный однозначно быстрее
O(n2) arraylist.
O(n) linkedlist.
В идеальной сферической ЭВМ в вакууме?

в идеальной, естественно. Что касается явы, linkedlist не позволяет напрямую работать с объектами хранения связанного списка, и без вспомогательного списка тут не обойтись. Но все равно дополнительная используемая память - O(1). Алгоритм достаточно очевиден - выбрать хвост (n/2) в дополнительный список, а потом используя ListIterator вставить обратно.
Можно также написать свою реализацию, либо попробовать сделать хак с использованием приватных методов LinkedList и рефлексии.

Но насчет массива я действительно погорячился - с ним тоже решается за O(n)

+
идея заключается в прямом вычислении нового адреса каждого элемента.
Элементы до n/2 занимают четные места, остальные - нечетные и в обратном порядке.
int newAddress(int currAdress, int size) {
  int test = currAdress*2;
  if (test<n-1) return test;
  if (currAddress==size-1) return currAddress;
  return size*2-test-3;
}

дальше начиная с адреса 1 переставляем элемент на 2, с в - на 4 и тд, с помощью этой функции. подразумевается, что адреса начинаются с 0
Реализацию полностью писать не буду, и так понятно. Для оптимизаторов хинт - умножение на 2 можно сделать сдвигом.
14 ноя 13, 20:34    [15131271]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
ivanra
Member

Откуда:
Сообщений: 848
mesier,
SomeReplacementClass не будет работать, так как список изменяется не только через итератор, соответственно он тут же и вывалит исключение
14 ноя 13, 20:37    [15131289]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
Blazkowicz
Member

Откуда:
Сообщений: 24443
Atum1
Для затравки решение на Хаскель
http://ideone.com/JiG0Ut

Совершенно аналогично на какой нибудь функциональной либе для Java.
На pure Java 8, как я понял, не получится, так как там отсутствует zip и походу вообще работа с индексами в функциональных методах коллекций.
14 ноя 13, 20:55    [15131388]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
cdtyjv
Member

Откуда:
Сообщений: 1638
Atom1,
Коллега, вы занимаетесь какой-то херней, право. Выдумали какой-то совершенно нереальный кейс, и настоятельно просите его решить. Да нафиг никому не упало так переставлять элементы, понимаете.

Коллекции надо оценивать по типичным операциям, которые над ними производят. Вот и давайте сравнивать. Какие есть операции? У списка?
1) Добавление в голову;
2) Добавление в хвост;
3) Добавление в середину;
4) Удаление с головы;
5) Удаление с конца;
6) Удаление с середины;
7) Взять элемент по индексу.

Вроде ничего не забыл. Теперь давайте сравнивать.
1) Добавление в голову
ArrayList = O(n), так как надо двигать все элементы вправо.
LinkedList = O(1), так как просто заменяем head.

2) Добавление в хвост
ArrayList = O(1), так как просто вставить по оффсету (иногда будет ресайз, но на него пофиг).
LinkedList = O(1), так как просто заменяем tail.

3) Добавление в середину
ArrayList = O(n), так как надо сдвинуть все элементы после вставленного вправо.
LinkedList = O(n), так как надо пройтись по всем элементам с головы.

4) Удаление с головы
ArrayList = O(n), так как надо сдвинуть все влево.
LinkedList = O(1), так как надо просто заменить head.

5) Удаление с конца
ArrayList = O(1), просто изменили длину.
LinkedList = O(1), просто заменили tail.

6) Удаление с середины
ArrayList = O(n), так как надо сдвинуться влево.
LinkedList - O(n), так как надо дойти до этого элемента.

7) Взять элемент по индексу
ArrayList = O(1), так как просто посчитать оффсет.
LinkedList = O(n), так как надо проитерироваться по узлам.

Вот и все, не надо никакие высосанные из пальца задачи выдумывать.
Если где соврал - поправляйте.
14 ноя 13, 21:47    [15131599]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
ivanra
Member

Откуда:
Сообщений: 848
cdtyjv
Если где соврал - поправляйте.

Ответ неполный
8) Добавление в текущей позиции - LinkedList = O(1)
9) удаление в текущей позиции - LinkedList = O(1)
задача и про это тоже
14 ноя 13, 21:52    [15131620]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
HoBTID
Member

Откуда:
Сообщений: 929
ivanra
Ответ неполный
8) Добавление в текущей позиции - LinkedList = O(1)
9) удаление в текущей позиции - LinkedList = O(1)
задача и про это тоже

Чем текущая позиция отличается от середины?
Очевидно, что ничем. Середина это не n/2, это просто не начало и не конец.
14 ноя 13, 21:59    [15131641]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
cdtyjv
Member

Откуда:
Сообщений: 1638
HoBTID
ivanra
Ответ неполный
8) Добавление в текущей позиции - LinkedList = O(1)
9) удаление в текущей позиции - LinkedList = O(1)
задача и про это тоже

Чем текущая позиция отличается от середины?
Очевидно, что ничем. Середина это не n/2, это просто не начало и не конец.
Пункт 8 мимо, да. Это тоже самое, что и мое добавление в середину.
А вот п.9 - это правильное замечание. Имеется ввиду Iterator.remove(). Здесь LinkedList это O(1), а ArrayList O(n).
14 ноя 13, 22:15    [15131697]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
ivanra
Member

Откуда:
Сообщений: 848
cdtyjv
Пункт 8 мимо, да. Это тоже самое, что и мое добавление в середину.
А вот п.9 - это правильное замечание. Имеется ввиду Iterator.remove(). Здесь LinkedList это O(1), а ArrayList O(n).

и все-таки я настаиваю по 8 пункту
14 ноя 13, 22:34    [15131763]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
cdtyjv
Member

Откуда:
Сообщений: 1638
ivanra,
Согласен.
14 ноя 13, 22:36    [15131767]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
mesier
Member

Откуда: Новокузнецк ► СПб
Сообщений: 1044
ivanra
mesier,
SomeReplacementClass не будет работать, так как список изменяется не только через итератор, соответственно он тут же и вывалит исключение

Именно поэтому Iterator и берется на каждом шаге новый, чтоб не было исключения.
14 ноя 13, 23:09    [15131961]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
Atum1
Member

Откуда: СПБ
Сообщений: 1836
super-code
Atum1, я решил на C# :)

сложность ArrayList - N^2, LinkedList - N


Отлично :)

http://ideone.com/

поддерживает C# - буду рад видеть Ваше решение.
15 ноя 13, 09:10    [15133320]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
Atum1
Member

Откуда: СПБ
Сообщений: 1836
mesier
Было же условие. Отменили??
2) Без использования дополнительного списка (массива) - делать перестановки в этом же списке, массиве.


Это второй вариант решения задачи. Делать перестановки в существующем массиве. Без использования и создания нового.

Такое решение приветствуется в двойне! :) и даст вам больше баллов.
15 ноя 13, 09:16    [15133366]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
Atum1
Member

Откуда: СПБ
Сообщений: 1836
cdtyjv
Atom1,
Коллега, вы занимаетесь какой-то херней, право. ....

Вот и все, не надо никакие высосанные из пальца задачи выдумывать.


Ваше право так думать , коллега.

С теорией я вижу у вас все ок! :)

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

Кто хотел тот - потратил 15 минут времени и предоставил свое решение .

Я рассматриваю такие задачки - как разминку для ума . Это не Олимпиадная задачка, не сверх энтерпразная , это простой алгоритм на перестановку , который требует от Вас знаний коллекций, понимания того как они устроены и применения этих навыков в жизни.

Любой спортсмен - должен поддерживать себя в форме - на это ему надо тратить минимум 40 минут в день . Любой кто бегло говорить на иностранном языке - должен каждый день практиковаться , чтобы не ушел навык ... думаю ассоциативный ряд понятен ?!

Как часто программисту приходится придумывать алгоритмы для решения тех или иных задач ,которые возникают в процессе работы?

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



Как пример из жизни - часто приходится использовать такие методы как

Collections.shuffle(list);
Collections.rotate(list, distance);


Так и в этой задачке - нужно было изменить порядок элементов - по заранее определенному алгоритму. Для чего это нужно?

Мой ответ : Кто решил задачу - возможно еще лучше разобрался в тех инструментах которые у него есть , лучше узнал язык на котором он пишет каждый день.
15 ноя 13, 09:52    [15133585]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
mesier
Member

Откуда: Новокузнецк ► СПб
Сообщений: 1044
Atum1
mesier
Было же условие. Отменили??
2) Без использования дополнительного списка (массива) - делать перестановки в этом же списке, массиве.

Это второй вариант решения задачи. Делать перестановки в существующем массиве. Без использования и создания нового.
Такое решение приветствуется в двойне! :) и даст вам больше баллов.

Вы меня пугаете!.. о_О
Где это вы уже баллы раздаете??
15 ноя 13, 09:55    [15133596]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
Atum1
Member

Откуда: СПБ
Сообщений: 1836
mesier
Где это вы уже баллы раздаете??


От себя :) Вам в Карму :)
15 ноя 13, 10:32    [15133864]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
Atum1
Member

Откуда: СПБ
Сообщений: 1836
mesier
Пойдёт так? )))
Про сложность я, правда, ниче не знаю, извини..



Спасибо! Добавил Ваше решение :)

http://ideone.com/UrCY6P


ivanra
mesier,
SomeReplacementClass не будет работать, так как список изменяется не только через итератор, соответственно он тут же и вывалит исключение


ivanra , решение работает и выдает верный ответ! Проверяйте ;)

Вопрос к вам : как работает descendingIterator() - и почему проходит вставка в .add(i + 1, t); и не выбрасывается исключение? ?
15 ноя 13, 10:46    [15133952]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
ivanra
Member

Откуда:
Сообщений: 848
Atum1
Вопрос к вам : как работает descendingIterator() - и почему проходит вставка в .add(i + 1, t); и не выбрасывается исключение? ?

был неправ, перепутал с LinkedList.listIterator - спросто сразу подумал про него, так как .add(i + 1, t) на LinkedList будет давать сложность O(n2), а вот с listIterator можно было бы сделать O(n) если бы не это исключение.

Кстати, алгоритм с прямым вычислением новых адресов на ArrayList оказался не так прост, без теории тут не обойтись, может, кто решит:
+
public class Sorter<T> {
	public void shuffle(List<T> list) {
		int loopStart = 1;
		int currAddress = loopStart;
		T currObject = list.get(currAddress);
		for (int i=1; i<list.size()-2;i++) {
			currAddress = newAddress(currAddress, list.size());
			T prevObject = list.get(currAddress);
			list.set(currAddress, currObject);
			if (currAddress==loopStart) { // цикл замкнулся, что делать дальше-непонятно
				loopStart = loopStart*2+1;
				currAddress=loopStart;
				currObject = list.get(currAddress);
			} else {
				currObject = prevObject;
			}
		}
		list.set(loopStart, currObject);
	}
	
	int newAddress(int currAddress, int size) {
		int test = currAddress*2;
		if (test<size-1) return test;
		if (currAddress==size-1) return currAddress;
		return size*2-test-3;
	}
}

прыгая с адреса на адрес, в конечном счете приходим в начальную точку, но если цикл не закончился, то как найти следующую неиспользованную точку для продолжения цикла - вопрос. Например, на массиве длиной 14 приведенный мной алгоритм работает неверно.
15 ноя 13, 11:15    [15134153]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
super-code
Member

Откуда:
Сообщений: 244
ivanra,

Вчерашнее решение:

http://ideone.com/opr12M

Сложность уже описывал.

Для linkedList: N (нужно пройти весь массив)
Для ArrayList: N*N (нужно пройти весь массив, на каждом шаге вставка идет в середину массива, и для этого будет полное копирование массива).
15 ноя 13, 11:24    [15134242]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
super-code
Member

Откуда:
Сообщений: 244
Atum1, предыдущее сообщение было, конечно же, Вам.

п.с. на работу пригласите? :)
15 ноя 13, 11:27    [15134274]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
Atum1
Member

Откуда: СПБ
Сообщений: 1836
super-code
ivanra,

Вчерашнее решение:

http://ideone.com/opr12M

Сложность уже описывал.

Для linkedList: N (нужно пройти весь массив)
Для ArrayList: N*N (нужно пройти весь массив, на каждом шаге вставка идет в середину массива, и для этого будет полное копирование массива).


Коллега, спасибо !

У Вас в выводе итоговой коллекции больше значений чем в исходной !?

Для ваших значений результат должен быть таким :

[8, 11, 9, 10, 12].size(5)
[8, 12, 9, 11, 10, 13].size(6)

x(1),x(2),...,x(n) => x(1), x(n-1), x(2), x(n-2),...,x(n)
15 ноя 13, 11:31    [15134321]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
super-code
Member

Откуда:
Сообщений: 244
super-code,

хотя для Queue, тоже можно сделать без доп. массива, наврал.
15 ноя 13, 11:32    [15134333]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: Ctrl  назад   1 [2] 3 4 5 6 7 8 9 10 .. 42   вперед  Ctrl
Все форумы / Java Ответить