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

@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.

Pablito · 01.07.2016, 19:20

а ты точно знаешь джаву?
ну просто глядя на ЭТО, закрадываются сомнения

@brainleo · 01.07.2016, 19:44 **[ТС]**

Сообщение от Паблито

а ты точно знаешь джаву?
ну просто глядя на ЭТО, закрадываются сомнения

Спасибо за ответ по теме.

Добавлено через 20 минут
а что именно вас смущает? статичный метод, отсутствие generic'ов, не правильная работа с коллекцией? Зачем отвечать таким образом, что возникает больше вопросов. Если бы я полагался на свои знания, то в принципе не писал бы тут вопроса. Поэтому очень классно, что на форуме есть люди, которые знают джаву и могут помочь с исчерпывающим ответом даже на глупый вопрос.

ninjacut · 01.07.2016, 20:01

Вообще я думаю что это дебильное задание для собеседования, но не суть.
Посмотри в сорсах как реализован метод add, обрати внимание на вызов ensureCapacity

@brainleo · 01.07.2016, 20:03 **[ТС]**

Сообщение от ninjacut

Вообще я думаю что это дебильное задание для собеседования, но не суть.
Посмотри в сорсах как реализован метод add, обрати внимание на вызов ensureCapacity

а по-мойму понял идею

ninjacut · 01.07.2016, 20:08

brainleo, не, так ты его вызываешь и все равно заполняешь null-ями. Суть в том что без вызова этого метода, массив будет копироваться два раза (может 3, но вроде нет) а если вызвать этот метод, размер увеличится до нужного и скопируется в новый только один раз. Соответственно если размер листа 100 тысяч то копировать 1 или 2 раза это большая разница.

@brainleo · 01.07.2016, 20:17 **[ТС]**

ninjacut, а может подскажешь, для проверки верно ли понял.. при начальной загрузке например там лежит массив с 10 элементами, и когда все ячейки заполнены, то создается массив новый с 11 элементами? Когда писал, думал что массив автоматически как миниму в 1.5 раза увеличивается, как количество бэкитов в HashSet....?

ninjacut · 01.07.2016, 20:21

brainleo, Так вроде и есть, но если в 1.5 раза то оно же будет 2 раза увеличиваться, не? Если у тебя 2 массива по 10, тебе нужен первый в 20, он сначала увеличится до 16 или 15, потом до 30+. А так ты сразу делаешь его 20+.

@KEKCoGEN · 01.07.2016, 20:31

brainleo,
1. Создать новый лист с размером a + b
2. Переписать элементы через один из а и b.

@DavidKarchikyan · 01.07.2016, 20:59

Или вставляй в Лист а из Листа b по нечетным индексам

@brainleo · 01.07.2016, 21:38 **[ТС]**

Сообщение от KEKCoGEN

1. Создать новый лист с размером a + b
2. Переписать элементы через один из а и b.

окей, попробую засечь время на выполнение такой процедуры )
однако там было еще одно условие - не ресурсоемкое, а тут создается промежуточная коллекция...
т.е. надо в первый передаваемый массив сделать желаемую структуру...

Добавлено через 16 минут

Сообщение от DavidKarchikyan

Или вставляй в Лист а из Листа b по нечетным индексам

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

@DavidKarchikyan · 01.07.2016, 21:50

brainleo,
С конца даже больше, так как придется копировать еще и данные которые с b ввел

@brainleo · 01.07.2016, 21:53 **[ТС]**

Сообщение от DavidKarchikyan

С конца с начала то же кол-во копирований)

Преимущества ArrayList: в возможности доступа к произвольному элементу по индексу за постоянное время (так как это массив), минимум накладных расходов при хранении такого списка, вставка в конец списка в среднем производится так же за постоянное время. В среднем потому, что массив имеет определенный начальный размер n (в коде это параметр capacity), по умолчанию n = 10, при записи n+1 элемента, будет создан новый массив размером (n * 3) / 2 + 1, в него будут помещены все элементы из старого массива + новый, добавляемый элемент. В итоге получаем, что при добавлении элемента при необходимости расширения массива, время добавления будет значительно больше, нежели при записи элемента в готовую пустую ячейку. Тем не менее, в среднем время вставки элемента в конец списка является постоянным. Удаление последнего элемента происходит за константное время. Недостатки ArrayList проявляются при вставке/удалении элемента в середине списка — это взывает перезапись всех элементов размещенных «правее» в списке на одну позицию влево, кроме того, при удалении элементов размер массива не уменьшается, до явного вызова метода trimToSize().

https://habrahabr.ru/post/162017/

@DavidKarchikyan · 01.07.2016, 21:58

brainleo,
Я конечно постараюсь доходчиво объяснить. КЛЮЧЕВОЕ СЛОВО

Сообщение от brainleo

конец списка

. А не с конца списка, так как из b копируется не только в конец.

@brainleo · 01.07.2016, 22:27 **[ТС]**

Сообщение от DavidKarchikyan

Я конечно постараюсь доходчиво объяснить. КЛЮЧЕВОЕ СЛОВО

не вопрос, возможно доходчиво и не понимаю

если не сложно, набросайте код, я реально профилировщиком оценю

Добавлено через 21 минуту
я оттестировал два варинта

1 вариант который я предлагал - среднее время на выполнении 12-13 мс на коллекциях каждая в 1 млн элементов

после коррекции с учетом рекомендаций ninjacut в таком виде:

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

время составило 3-4 мс

уже что-то есть )) спасибо большое

@DavidKarchikyan · 01.07.2016, 22:39

brainleo,
i

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
mport java.util.ArrayList;
 
public class Main {
    public static void main(String args[]) {
 
        ArrayList<Integer> a = new ArrayList<Integer>();
        ArrayList<Integer> b = new ArrayList<Integer>();
        int count = 0;
 
        for (int i = 0; i < 10; i++) {
            a.add(i);
        }
 
        for (int i = 0; i < 10; i++) {
            b.add(i + 15);
        }
 
        for (int i = 0; i < 20; i++) {
 
            if (i % 2 != 0) {
                a.add(i, b.get(count));
                count++;
            }
 
        }
        for (int i = 0; i < a.size(); i++) {
            System.out.println(a.get(i));
        }
 
    }
}

Разберись)

@KEKCoGEN · 01.07.2016, 22:56

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

@brainleo · 01.07.2016, 23:35 **[ТС]**

Сообщение от DavidKarchikyan

Разберись

а ты разберись что произойдет с твоим кодом когда размер каждой из коллекций не 10, а 1 000 000

ты не против таких изменений в твоем коде???

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
package by.topolev.serailize;
 
import java.util.ArrayList;
 
public class TestTest {
    public static void main(String args[]) {
         
        ArrayList<Integer> a = new ArrayList<Integer>();
        ArrayList<Integer> b = new ArrayList<Integer>();
        int count = 0;
        int size = 1000000;
        for (int i = 0; i < size; i++) {
            a.add(i);
        }
 
        for (int i = 0; i < size; i++) {
            b.add(i + 15);
        }
 
        for (int i = 0; i < 2*size; i++) {
 
            if (i % 2 != 0) {
                a.add(i, b.get(count));
                count++;
            }
 
        }
        for (int i = 0; i < a.size(); i++) {
            System.out.println(a.get(i));
        }
 
    }
}

через профилировщик это "программа выполнялась 76489 миллисекунд"

Добавлено через 23 минуты
Если вдруг у кого идеи появятся, будет интересно, а так я тестировал следующие коды, при этом каждая коллекция содержит не менее 1 000 000 элементов и замер осуществлялся в среднем на 1000 вызовах.

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

Итог в среднем 5 мс

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

Итог в среднем 14 мс

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

Итог в среднем 16 мс

Java
1
2
3
4
5
6
7
8
9
    static void merge3(ArrayList a, ArrayList b) {
        ArrayList c = new ArrayList(a.size()*2);
        
        for (int i=0; i<a.size();i++){
            c.add(a.get(i));
            c.add(b.get(i));
        }
        a.addAll(c);
    }

Итог в среднем 16 мс

Java
1
2
3
4
5
6
7
8
9
10
    static void merge4(ArrayList a, ArrayList b) {
        int size = a.size();
        int count = 0;
        for (int i = 0; i<size*2; i++){
            if (i % 2 != 0) {
                a.add(i, b.get(count));
                count++;
            }
        }
    }

Итога чуть дожадся и после даже первой итерации 76268 мс

ninjacut · 01.07.2016, 23:39

Java
1
2
3
4
5
6
7
8
9
static void merge3(ArrayList a, ArrayList b) {
        ArrayList c = new ArrayList(a.size()*2);
        
        for (int i=0; i<a.size();i++){
            c.add(a.get(i));
            c.add(b.get(i));
        }
        a.addAll(c);
    }

Вот здесь вместо a.addAll(c), a = c попробуй.

@brainleo · 01.07.2016, 23:43 **[ТС]**

DavidKarchikyan, в словах была ирония, а ведь

Сообщение от ninjacut

Вот здесь вместо a.addAll(c), a = c попробуй.

)) да, получилось 7 с, что ожидаемо )) но этот метод более ресурсоемкий за счет создания новой коллекции в любом случае. )

Новые блоги и статьи Все статьи Все блоги /
Почему дизайн решает? Neotwalker 09.01.2026 В современном мире, где конкуренция за внимание потребителя достигла пика, дизайн становится мощным инструментом для успеха бренда. Это не просто красивый внешний вид продукта или сайта — это. . .	Модель микоризы: классовый агентный подход 3 anaschu 06.01.2026 aa0a7f55b50dd51c5ec569d2d10c54f6/ O1rJuneU_ls https:/ / vkvideo. ru/ video-115721503_456239114	Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ФедосеевПавел 06.01.2026 Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ВВЕДЕНИЕ Введу сокращения: аналоговый ПИД — ПИД регулятор с управляющим выходом в виде числа в диапазоне от 0% до. . .	Модель микоризы: классовый агентный подход 2 anaschu 06.01.2026 репозиторий https:/ / github. com/ shumilovas/ fungi ветка по-частям. коммит Create переделка под биомассу. txt вход sc, но sm считается внутри мицелия. кстати, обьем тоже должен там считаться. . . .
Расчёт токов в цепи постоянного тока igorrr37 05.01.2026 / * Дана цепь постоянного тока с сопротивлениями и напряжениями. Надо найти токи в ветвях. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа и решает её. Последовательность действий:. . .	Новый CodeBlocs. Версия 25.03 palva 04.01.2026 Оказывается, недавно вышла новая версия CodeBlocks за номером 25. 03. Когда-то давно я возился с только что вышедшей тогда версией 20. 03. С тех пор я давно снёс всё с компьютера и забыл. Теперь. . .	Модель микоризы: классовый агентный подход anaschu 02.01.2026 Раньше это было два гриба и бактерия. Теперь три гриба, растение. И на уровне агентов добавится между грибами или бактериями взаимодействий. До того я пробовал подход через многомерные массивы,. . .	Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Programma_Boinc 28.12.2025 Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / ********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / ********/ gallery/ bKBkQFf Пост отсюда. . .

Pablito 2884 / 2296 / 769 Регистрация: 12.05.2014 Сообщений: 7,978
	01.07.2016, 19:20
	а ты точно знаешь джаву? ну просто глядя на ЭТО, закрадываются сомнения 1

ninjacut 155 / 154 / 53 Регистрация: 30.04.2016 Сообщений: 321
	01.07.2016, 20:01
	Вообще я думаю что это дебильное задание для собеседования, но не суть. Посмотри в сорсах как реализован метод add, обрати внимание на вызов ensureCapacity 0

ninjacut 155 / 154 / 53 Регистрация: 30.04.2016 Сообщений: 321
	01.07.2016, 20:08
	brainleo, не, так ты его вызываешь и все равно заполняешь null-ями. Суть в том что без вызова этого метода, массив будет копироваться два раза (может 3, но вроде нет) а если вызвать этот метод, размер увеличится до нужного и скопируется в новый только один раз. Соответственно если размер листа 100 тысяч то копировать 1 или 2 раза это большая разница. 1

@brainleo 1 / 0 / 0 Регистрация: 01.07.2016 Сообщений: 13
	01.07.2016, 20:17 [ТС]
	ninjacut, а может подскажешь, для проверки верно ли понял.. при начальной загрузке например там лежит массив с 10 элементами, и когда все ячейки заполнены, то создается массив новый с 11 элементами? Когда писал, думал что массив автоматически как миниму в 1.5 раза увеличивается, как количество бэкитов в HashSet....? 0

ninjacut 155 / 154 / 53 Регистрация: 30.04.2016 Сообщений: 321
	01.07.2016, 20:21
	brainleo, Так вроде и есть, но если в 1.5 раза то оно же будет 2 раза увеличиваться, не? Если у тебя 2 массива по 10, тебе нужен первый в 20, он сначала увеличится до 16 или 15, потом до 30+. А так ты сразу делаешь его 20+. 1

@KEKCoGEN 2399 / 2224 / 565 Регистрация: 28.12.2010 Сообщений: 8,672
	01.07.2016, 20:31
	Сообщение было отмечено vxg как решение Решение brainleo, 1. Создать новый лист с размером a + b 2. Переписать элементы через один из а и b. 1

@DavidKarchikyan 64 / 64 / 26 Регистрация: 07.01.2016 Сообщений: 374
	01.07.2016, 20:59
	Или вставляй в Лист а из Листа b по нечетным индексам 0

@DavidKarchikyan 64 / 64 / 26 Регистрация: 07.01.2016 Сообщений: 374
	01.07.2016, 21:50
	brainleo, С конца даже больше, так как придется копировать еще и данные которые с b ввел 0

@KEKCoGEN 2399 / 2224 / 565 Регистрация: 28.12.2010 Сообщений: 8,672
	01.07.2016, 22:56
	brainleo, вы в любом случае создаете промежуточную коллекцию только неявно. 0

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

Решение