Задача на собеседовании

@brainleo · Регистрация: 01.07.2016

Студворк — интернет-сервис помощи студентам

Добрый день.

Являюсь начинающим разработчиком и пытался проходить одно собеседование на позиции стажера Junior Java и после моего предложенного решения мне отказали.
Хотел бы все-таки попытаться решить данную задачу или как минимум то решение, которое хотели от меня интервьювер.

Задча была следующей. Написатть метод merge, который принимаем в качстве параметров два ArrayList a и b.
Данные коллекции можно представить в виде a = [a1, a2, a3, ....] и b = [b1, b2, b3, ...]. По результату выполеения программы
надо получить в коллекции а следующее a= [a1, b1, a2, b2, a3, b3.....]. При этом необходимо написать метод, который
экономный к процессорному времени и памяти.

Я предложил следующий вариант решения задачи:

Java
1
2
3
4
5
6
7
8
9
10
    static void merge(ArrayList a, ArrayList b) {
    int size = b.size();
    for (int i=0; i<size; i++){
    a.add(null);
    }
    for (int i=size; i>0; i--){
    a.set((i<<1)-1,b.get(i-1));
    a.set((i<<1)-2,a.get(i-1));
    }
    }

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

@Данила37 · 20.12.2016, 13:54

Java
1
2
3
4
5
6
7
8
9
10
11
12
int size = b.size();
        a.ensureCapacity(size * 2);
        for (int i = 0; i < size; i++) {
            a.add(i+size,null);
        }
        int indA = b.size()-1;
        int indB = b.size()-1;
        for (int i = a.size()-1; i >0; i--) {
 
            if(i%2!=0){a.set(i,b.get(indB)); indB--;}
            if(i%2==0){a.set(i,a.get(indA)); indA--;}
        }

Только учу JAVA, замерял время на десятке способов, этот в большом отрыве от остальных, за счет добавления нулевых элементов в конец, а не в начало. При этом не копируются каждый раз элементы стоящие справа, т.к. их нет. Хотя может я в чем-то ошибаюсь.
А на счет capasity. Тут совершенно не влияет на скорость работы,т.к. без него мы увеличиваем массив 2 раза, а с ним 1 раз. Это настолько малые времязатраты, по сравнению с добавлением элементов одного массива в другой, что не играет никакой роли.

Если чушь пишу, поправьте)

@Ixb3k · 21.12.2016, 18:13

Сообщение от Данила37

замерял время на десятке способов, этот в большом отрыве от остальных

Самый быстрый алгоритм этот: merge3
Твой вдвое медленнее: merge1
Мой где-то посередине: merge0
Что удивительно, т.к. код мягко говоря костылен:

Кликните здесь для просмотра всего текста

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
    private static
    void merge0(ArrayList a, final ArrayList b) {
        final int size = a.size();
        final int dop = size % 2;
        final int size_h = size + dop;
        final int size_half_l = (size - dop) / 2;
        final int size_half_h = size_h / 2;
        
        //phase 1: reserve memory for part2
        a.ensureCapacity(a.size() + b.size() + 1);
        
        //phase 2: fill part2
        if (dop == 1) a.add(a.get(size - 1)); //bound array
        for (int i = 0; i < size_half_l; i++) {
            int ind1 = size_half_h + i;
            a.add(a.get(ind1));
            a.add(b.get(ind1));
        }
        
        //phase 3: sparse part1
        for (int i = 0; i < size_half_l; i++) {
            int ind1 = size_h - i * 2 - 2;
            int ind2 = size_half_h - i - 1;
            a.set(ind1, a.get(ind2));
        }
        
        //phase 4: fill part1
        for (int i = 0; i < size_half_l; i++) {
            int ind1 = size_h - i * 2 - 1;
            int ind2 = size_half_h - i - 1;
            a.set(ind1, b.get(ind2));
        }
        if (dop == 1) a.set(1, b.get(0));
    }

Сначала увеличиваем размер массива вдвое.
Потом заполняем пустое место данными из вторых половинок обоих массивов, сразу с чередованием. На этом конец выходного массива сформирован, осталось сформировать начало.
В начале массива половина данных (1/4 размера выходного массива) уже скопирована в конец - смело растягиваем первую 1/4 данных ровно до половины выходного массива, затирая уже неактуальные данные.
Ну и в конце распихиваем первую половину второго массива по первой половине выходного массива, между растянутыми элементами.

Получается три цикла по половине входного массива и количество перемещенных элементов равное размеру выходного массива минус один.

Новые блоги и статьи Все статьи Все блоги /
Debian 13: Установка Lazarus QT5 ВитГо 09.05.2026 Эта инструкция моя компиляция инструкций volvo https:/ / www. cyberforum. ru/ blogs/ 203668/ 10753. html и его же старой инструкции по установке Lazarus с gtk2. . .	Нейросеть на алгоритме "эстафета хвоста" как перспектива. Hrethgir 06.05.2026 На десерт, когда запущу сервер. Статья тут https:/ / habr. com/ ru/ articles/ 1030914/ . Автор я сам, нейросеть только помогает в вопросах которые мне не известны - не знаю людей которые знали-бы. . .	Асинхронный приём данных из COM-порта Argus19 01.05.2026 Асинхронный приём данных из COM-порта Купил на aliexpress термопринтер QR701. Он оказался странным. Поключил к Arduino Nano. Был очень удивлён. Наотрез отказывается печатать русские буквы. Чтобы. . .	попытка написать игровой сервер на C++ pyirrlicht 29.04.2026 попытка написать игровой сервер на плюсах с открытым бесконечным миром. возможно получится прикрутить интерпретатор питон для кастомизации игровой логики. что есть на текущий момент:. . .
Контроль уникальности выбранного документа-основания при изменении реквизита Maks 28.04.2026 Алгоритм из решения ниже разработан на примере нетипового документа "ЗаявкаНаРемонтСпецтехники", разработанного в КА2. Задача: уведомлять пользователя, если указанная заявка (документ-основание). . .	Благородство как наказание Maks 24.04.2026 У хорошего человека отношения с женщинами всегда складываются трудно. А я человек хороший. Заявляю без тени смущения, потому что гордиться тут нечем. От хорошего человека ждут соответствующего. . .	Валидация и контроль данных табличной части документа перед записью Maks 22.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа, разработанного в КА2. Задача: контроль и валидация данных табличной части документа перед записью с учетом регламента компании. . .	Отчёт о затраченных материалах за определенный период с макетом печатной формы Maks 21.04.2026 Отчёт из решения ниже размещён в конфигурации КА2. Задача: разработка отчёта по затраченным материалам за определённый период, с возможностью вывода печатной формы отчёта с шапкой и подвалом. В. . .

Опции темы