Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Java Новый топик    Ответить
Топик располагается на нескольких страницах: Ctrl  назад   1 .. 33 34 35 36 37 38 39 40 41 [42]
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
mayton
Member

Откуда: loopback
Сообщений: 41924
asv79
Ну а если в тз этого нет,то зачем выдумавать огород-вам четко сказали что от вас хотят увидеть.

Напомни твой ответ по данной задаче.
21 апр 19, 12:57    [21868150]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
asv79
Member

Откуда: Тверь
Сообщений: 2084
mayton
asv79
Ну а если в тз этого нет,то зачем выдумавать огород-вам четко сказали что от вас хотят увидеть.

Напомни твой ответ по данной задаче.

Посмотри вверху там есть
21 апр 19, 13:09    [21868155]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
Андрей Панфилов
Member

Откуда: Москва > Melbourne
Сообщений: 3302
Озверин
Кстати, в целом, было интересной задачей отрефакторить метод так, чтобы не падал по стаковерфлоу.
Чет у вас, действительно, какое-то превратное понятие о рефакторинге.

1. удаляем логику из вывода
2. удаляет мусор из статических переменных
	public static void main(String args[]) {
		print(1, 10);
	}

	static boolean print(int from, int to) {
		System.out.println(from);
		boolean b = (from >= to || print(from + 1, to));
		return true;
	}

3. замечаем что LoC снизился, читаемость улучшилась
4. замечаем, что вместо глубины N нам достаточно log(N), получаем:
	public static void main(String args[]) {
		print(1, 10);
	}

	static boolean print(int from, int to) {
		System.out.println(from);
		int average = (from + 1 >> 1) + (to >> 1) + 1;
		boolean b = (from + 1 >= average || print(from + 1, average - 1));
		b = (average - 1 >= to || print(average, to));
		return true;
	}

5. поведение на границах разобрать самостоятельно
21 апр 19, 14:04    [21868187]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
Мозговой_слизень
Member

Откуда:
Сообщений: 3008
Господа, я всю ветку не читал. А такое решение было?


        Deque<Integer> deque = new ArrayDeque<>();

        deque.offer(10);
        deque.offer(20);
        deque.offer(30);
        deque.offer(40);

        System.out.println("Reverse order:");

        for(Iterator descItr = deque.descendingIterator(); descItr.hasNext();) {
            System.out.println(descItr.next());
        }


        List<Integer> al = new LinkedList<Integer>();
        al.add(10);
        al.add(20);
        al.add(30);
        al.add(40);

        Collections.sort(al, Collections.reverseOrder());
        System.out.println("Reverse order :\n" + al);


Для ArrayList код такой же как для LinkedList.

Ну типа для каждого интерфейса есть метод, который позволяет порядок любой использовать. LinkedList имплементит два интерфейса (это и лист и очередь), следовательно менее эффективен чем "чистая" очередь (ArrayDeque). ArrayList позволяет обращаться к каждому элементу за постоянное время, независимо от размера. То есть, условно, самый оперативный при прочих равных будет ArrayList, затем ArrayDeque и потом LinkedList.
21 апр 19, 17:20    [21868257]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
Мозговой_слизень
Member

Откуда:
Сообщений: 3008
package one;

import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

class Item{
    private int id;
    private String name;
    public Item(int id, String name){
        this.id = id;
        this.name = name;
    }

    public Integer getId() {
        return id;     }

    public void setId(int id) {
        this.id = id;     }

    public String getName() {
        return name;     }

    public void setName(String name) {
        this.name = name;     }

    public String toString(){
        return name;     }
}


public class C1762 {

    public static void main(String[] args) {
        List<Item> l = Arrays.asList(
                new Item(1, "Screw"),
                new Item(2, "Nail"),
                new Item(3, "Bolt")
        );


     l.stream().sorted((a,b)->a.getId().compareTo(b.getId())).forEach(System.out::print);
     System.out.println();
     l.stream().sorted((a,b)->b.getId().compareTo(a.getId())).forEach(System.out::print); // REVERS ORDER




    }

}
7 июл 19, 20:40    [21922316]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
mayton
Member

Откуда: loopback
Сообщений: 41924
Мозговой_слизень
Для ArrayList код такой же как для LinkedList.

Ну типа для каждого интерфейса есть метод, который позволяет порядок любой использовать. LinkedList имплементит два интерфейса (это и лист и очередь), следовательно менее эффективен чем "чистая" очередь (ArrayDeque). ArrayList позволяет обращаться к каждому элементу за постоянное время, независимо от размера. То есть, условно, самый оперативный при прочих равных будет ArrayList, затем ArrayDeque и потом LinkedList.

Такие задачи интреснее всего решать на Lisp. Там есть азарт игры со списками. В библиотеках Java с коллекциями
мы только соревнуемся в частном знании какого нибудь конкретного метода. Это скушно.

Задачка с перевёртышем списка мне почему-то напоминает головоломки Мартина Гарднера (?возможно) где
есть железнодорожная ветка и стоит задача перевернуть состав вагонов наоборот. Ну... ассоциации.
7 июл 19, 22:14    [21922329]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
Atum1
Member

Откуда: СПБ
Сообщений: 1842
mayton
Мозговой_слизень
Для ArrayList код такой же как для LinkedList.

Ну типа для каждого интерфейса есть метод, который позволяет порядок любой использовать. LinkedList имплементит два интерфейса (это и лист и очередь), следовательно менее эффективен чем "чистая" очередь (ArrayDeque). ArrayList позволяет обращаться к каждому элементу за постоянное время, независимо от размера. То есть, условно, самый оперативный при прочих равных будет ArrayList, затем ArrayDeque и потом LinkedList.

Такие задачи интреснее всего решать на Lisp. Там есть азарт игры со списками. В библиотеках Java с коллекциями
мы только соревнуемся в частном знании какого нибудь конкретного метода. Это скушно.

Задачка с перевёртышем списка мне почему-то напоминает головоломки Мартина Гарднера (?возможно) где
есть железнодорожная ветка и стоит задача перевернуть состав вагонов наоборот. Ну... ассоциации.



Спасибо.

Сейчас спрашивают про деревья , просят написать алгоритм который обойдет дерево по горизонтали ( ярусами) итд ...

В Ведущих компаниях.
12 авг 19, 16:47    [21947369]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
mayton
Member

Откуда: loopback
Сообщений: 41924
Я думаю что это будет тот-же самый обход в глубину. Только делаем ограничение.
Добавляем переменную level. И публикуем только те листики которые попадают в уровень
1 потом 2 потом 3.

И обходов будет не 1 а соответственно N штук.

На псевдокоде.

for(level in (1,2,3,n)) {

  routeTree(Node node, int level) {
 
    // ...... main logic
    routeTree(newNode, level + 1);

  }

}
12 авг 19, 17:02    [21947389]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
Atum1
Member

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

вот нашел https://habr.com/ru/post/144850/

думаю просто про массивы уже надоело спрашивать :)
12 авг 19, 21:50    [21947551]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
mayton
Member

Откуда: loopback
Сообщений: 41924
Еще есть "волновой" алгоритм. Он требует модификаций всех узлов графа. Или маркировки их
какой-то целочисленной меткой.

Волна работает очень быстро и юзается в комп. играх для проверки путей в лабиринтах.
12 авг 19, 21:58    [21947557]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
Atum1
Member

Откуда: СПБ
Сообщений: 1842
Тут попалась задача на комбинаторику и графы ( возможно жадные алгоритмы ) и паковку чисел .

и так для примера есть набор всех комбинаций 4 из 20 - обозначим С(4.20) = 4845
первый 1#2#3#4 .... 17#18#19#20 ( все числа уникальные , без повторений одного числа )
так же верно следующее :
С(2.4) = 6 - пар в комбинации из 4х чисел (пример 1 2 3 4 - = 4 числа , 6 пар )
С(2.20)=190 - всего может быть пар (первая 1#2 ....19#20

Нужно найти минимальный набор ( 190/6 = 32 ) из 4х чисел чтобы он содержал все 190 пар.

Фактически нужно запаковать все 190 пар в минимальный набор , каждая последовательность которого будет длинной 4.

понятно что в наборе 4845 - одинаковое число единиц, двоек , троек ...чисел 19 и 20 ... так же одинаковое число повторов всех пар чисел и всех , троек чисел .

а вот как посроить алгоритм , который найдет минимальное число N на котором можно разместить все пары .

Все подходы что я попробовал - говорят что некоторые пары (и числа) пары заканчиваются раньше( поэтому чтобы минимально разместить 190 пар ) нужно 38 комбинаций по 4 числа .

тривиальный алгоритм - перем 1 комбинацию - из 4845 - добавляем в свой набор - вычеркиваем из всего массива 190 пар ее 6 пар, берем следующую в которой есть 6 уникальных пар итд ... пока не пройдем все комбинации , потом идем снова и ищем все у кого есть 5 уникальных пар итд ...
12 авг 19, 22:05    [21947561]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
mayton
Member

Откуда: loopback
Сообщений: 41924
Atum1, очень похоже на "укладку рюкзака".
12 авг 19, 22:39    [21947576]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
Atum1
Member

Откуда: СПБ
Сообщений: 1842
mayton
Atum1, очень похоже на "укладку рюкзака".



Да, возможно.

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

(Set Covering Problem (6,36) covering design )

у нас есть 36 чисел (от 1 до 36 ) , комбинация 6 чисел , нужно разместить все числа на 42 комбинациях так чтобы каждое число
встречалось ровно 7 раз, и все 630 пар были на данном набор ( каждая пара встречается ровно один раз).
17 сен 19, 17:17    [21972732]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
asv79
Member

Откуда: Тверь
Сообщений: 2084
вот вам вопрос почище
почему при увеличении ArrayLIst увеличивается в 1.5 раза?
а ХеШмапа в 2?
17 сен 19, 17:24    [21972739]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
Atum1
Member

Откуда: СПБ
Сообщений: 1842
Atum1
mayton
Atum1, очень похоже на "укладку рюкзака".



Да, возможно.

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

(Set Covering Problem (6,36) covering design )

у нас есть 36 чисел (от 1 до 36 ) , комбинация 6 чисел , нужно разместить все числа на 42 комбинациях так чтобы каждое число
встречалось ровно 7 раз, и все 630 пар были на данном набор ( каждая пара встречается ровно один раз).


http://www.openproblemgarden.org/op/covering_designs
17 сен 19, 17:34    [21972747]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
Atum1
Member

Откуда: СПБ
Сообщений: 1842
asv79
вот вам вопрос почище
почему при увеличении ArrayLIst увеличивается в 1.5 раза?
а ХеШмапа в 2?


Почему выбрали такие константы?
17 сен 19, 17:35    [21972748]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
asv79
Member

Откуда: Тверь
Сообщений: 2084
Atum1
asv79
вот вам вопрос почище
почему при увеличении ArrayLIst увеличивается в 1.5 раза?
а ХеШмапа в 2?


Почему выбрали такие константы?

да почему мапа увеличивается в два раза ,а эрейлист в 1.5?
17 сен 19, 17:50    [21972774]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
mayton
Member

Откуда: loopback
Сообщений: 41924
    /**
     * Initializes or doubles table size.  If null, allocates in
     * accord with initial capacity target held in field threshold.
     * Otherwise, because we are using power-of-two expansion, the
     * elements from each bin must either stay at same index, or move
     * with a power of two offset in the new table.
     *
     * @return the table
     */
    final Node<K,V>[] resize() {
17 сен 19, 18:04    [21972789]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
mayton
Member

Откуда: loopback
Сообщений: 41924
По листу. Такой строгой формулы нет. Потому-что нет ограничений. Я думаю что можно растягивать на любой коэффициент. Главное
чтобы была геометрическая прогрессия.
    /**
     * Increases the capacity to ensure that it can hold at least the
     * number of elements specified by the minimum capacity argument.
     *
     * @param minCapacity the desired minimum capacity
     */
    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }



Oracle к примеру использует растягивание табличных пространств на 20% при каждой нехватке. Это кажется было в девятке.
Как сейчас - не знаю. Из практических соображений я-бы брал любое число в качестве множителя больше 1.0 но меньше 2.0.
В противном случае сработает предикат newCapacity - MAX_ARRAY_SIZE хотя при этом я ЕЩЕ НЕ ДОСТИГ 2 миллиардов.

Тоесть разумное число +50%. Я тоже плюсую.
17 сен 19, 18:08    [21972796]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: Ctrl  назад   1 .. 33 34 35 36 37 38 39 40 41 [42]
Все форумы / Java Ответить