Форум программистов, компьютерный форум, киберфорум
Наши страницы
Java SE (J2SE)
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 4.73/22: Рейтинг темы: голосов - 22, средняя оценка - 4.73
brainleo
1 / 0 / 0
Регистрация: 01.07.2016
Сообщений: 13
1

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

01.07.2016, 19:13. Просмотров 4064. Ответов 41
Метки нет (Все метки)

Добрый день.

Являюсь начинающим разработчиком и пытался проходить одно собеседование на позиции стажера 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.
0
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
01.07.2016, 19:13
Ответы с готовыми решениями:

Задача на собеседовании
Доброго времени суток, написал задачу с собеседования прошу Вас посмотреть, и...

Задание на собеседовании - в чём ошибка?
Вот что попалось: Отпишите кто может. Всё-таки интересно какие же тут есть...

Для работающих Java-программистом. Вопросы на собеседовании
Народ (кто работает или уже пытался устроиться), можете поделиться вопросами,...

Задача на собеседовании
Текст задачи: Создать страницу с 2-мя блоками. В первом блоке ссылки, при...

Задача на собеседовании
дана матрица NxM по ней можно двигаться либо вниз либо вправо найти...

41
Pablito
2731 / 2166 / 735
Регистрация: 12.05.2014
Сообщений: 7,580
Завершенные тесты: 1
01.07.2016, 19:20 2
а ты точно знаешь джаву?
ну просто глядя на ЭТО, закрадываются сомнения
1
brainleo
1 / 0 / 0
Регистрация: 01.07.2016
Сообщений: 13
01.07.2016, 19:44  [ТС] 3
Цитата Сообщение от Паблито Посмотреть сообщение
а ты точно знаешь джаву?
ну просто глядя на ЭТО, закрадываются сомнения
Спасибо за ответ по теме.

Добавлено через 20 минут
а что именно вас смущает? статичный метод, отсутствие generic'ов, не правильная работа с коллекцией? Зачем отвечать таким образом, что возникает больше вопросов. Если бы я полагался на свои знания, то в принципе не писал бы тут вопроса. Поэтому очень классно, что на форуме есть люди, которые знают джаву и могут помочь с исчерпывающим ответом даже на глупый вопрос.
0
ninjacut
149 / 149 / 51
Регистрация: 30.04.2016
Сообщений: 321
01.07.2016, 20:01 4
Вообще я думаю что это дебильное задание для собеседования, но не суть.
Посмотри в сорсах как реализован метод add, обрати внимание на вызов ensureCapacity
0
brainleo
1 / 0 / 0
Регистрация: 01.07.2016
Сообщений: 13
01.07.2016, 20:03  [ТС] 5
Цитата Сообщение от ninjacut Посмотреть сообщение
Вообще я думаю что это дебильное задание для собеседования, но не суть.
Посмотри в сорсах как реализован метод add, обрати внимание на вызов ensureCapacity
а по-мойму понял идею
0
ninjacut
149 / 149 / 51
Регистрация: 30.04.2016
Сообщений: 321
01.07.2016, 20:08 6
brainleo, не, так ты его вызываешь и все равно заполняешь null-ями. Суть в том что без вызова этого метода, массив будет копироваться два раза (может 3, но вроде нет) а если вызвать этот метод, размер увеличится до нужного и скопируется в новый только один раз. Соответственно если размер листа 100 тысяч то копировать 1 или 2 раза это большая разница.
1
brainleo
1 / 0 / 0
Регистрация: 01.07.2016
Сообщений: 13
01.07.2016, 20:17  [ТС] 7
ninjacut, а может подскажешь, для проверки верно ли понял.. при начальной загрузке например там лежит массив с 10 элементами, и когда все ячейки заполнены, то создается массив новый с 11 элементами? Когда писал, думал что массив автоматически как миниму в 1.5 раза увеличивается, как количество бэкитов в HashSet....?
0
ninjacut
149 / 149 / 51
Регистрация: 30.04.2016
Сообщений: 321
01.07.2016, 20:21 8
brainleo, Так вроде и есть, но если в 1.5 раза то оно же будет 2 раза увеличиваться, не? Если у тебя 2 массива по 10, тебе нужен первый в 20, он сначала увеличится до 16 или 15, потом до 30+. А так ты сразу делаешь его 20+.
1
KEKCoGEN
Эксперт Java
2054 / 1927 / 498
Регистрация: 28.12.2010
Сообщений: 7,715
01.07.2016, 20:31 9
Лучший ответ Сообщение было отмечено vxg как решение

Решение

brainleo,
1. Создать новый лист с размером a + b
2. Переписать элементы через один из а и b.
1
DavidKarchikyan
62 / 62 / 26
Регистрация: 07.01.2016
Сообщений: 370
01.07.2016, 20:59 10
Или вставляй в Лист а из Листа b по нечетным индексам
0
brainleo
1 / 0 / 0
Регистрация: 01.07.2016
Сообщений: 13
01.07.2016, 21:38  [ТС] 11
Цитата Сообщение от KEKCoGEN Посмотреть сообщение
1. Создать новый лист с размером a + b
2. Переписать элементы через один из а и b.
окей, попробую засечь время на выполнение такой процедуры )
однако там было еще одно условие - не ресурсоемкое, а тут создается промежуточная коллекция...
т.е. надо в первый передаваемый массив сделать желаемую структуру...

Добавлено через 16 минут
Цитата Сообщение от DavidKarchikyan Посмотреть сообщение
Или вставляй в Лист а из Листа b по нечетным индексам
у вас в таком случае при каждой вставке будет переписываться часть массива, который справа находится, явно это не очень экономит время процессора, поэтому я делал это с конца массива, что как минимум я думал будет обходить это несчастное лишнее копирование
0
DavidKarchikyan
62 / 62 / 26
Регистрация: 07.01.2016
Сообщений: 370
01.07.2016, 21:50 12
brainleo,
С конца даже больше, так как придется копировать еще и данные которые с b ввел
0
brainleo
1 / 0 / 0
Регистрация: 01.07.2016
Сообщений: 13
01.07.2016, 21:53  [ТС] 13
Цитата Сообщение от DavidKarchikyan Посмотреть сообщение
С конца с начала то же кол-во копирований)
Преимущества ArrayList: в возможности доступа к произвольному элементу по индексу за постоянное время (так как это массив), минимум накладных расходов при хранении такого списка, вставка в конец списка в среднем производится так же за постоянное время. В среднем потому, что массив имеет определенный начальный размер n (в коде это параметр capacity), по умолчанию n = 10, при записи n+1 элемента, будет создан новый массив размером (n * 3) / 2 + 1, в него будут помещены все элементы из старого массива + новый, добавляемый элемент. В итоге получаем, что при добавлении элемента при необходимости расширения массива, время добавления будет значительно больше, нежели при записи элемента в готовую пустую ячейку. Тем не менее, в среднем время вставки элемента в конец списка является постоянным. Удаление последнего элемента происходит за константное время. Недостатки ArrayList проявляются при вставке/удалении элемента в середине списка — это взывает перезапись всех элементов размещенных «правее» в списке на одну позицию влево, кроме того, при удалении элементов размер массива не уменьшается, до явного вызова метода trimToSize().

https://habrahabr.ru/post/162017/
0
DavidKarchikyan
62 / 62 / 26
Регистрация: 07.01.2016
Сообщений: 370
01.07.2016, 21:58 14
brainleo,
Я конечно постараюсь доходчиво объяснить. КЛЮЧЕВОЕ СЛОВО
Цитата Сообщение от brainleo Посмотреть сообщение
конец списка
. А не с конца списка, так как из b копируется не только в конец.
0
brainleo
1 / 0 / 0
Регистрация: 01.07.2016
Сообщений: 13
01.07.2016, 22:27  [ТС] 15
Цитата Сообщение от 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 мс

уже что-то есть )) спасибо большое
0
DavidKarchikyan
62 / 62 / 26
Регистрация: 07.01.2016
Сообщений: 370
01.07.2016, 22:39 16
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));
        }
 
    }
}
Разберись)
0
KEKCoGEN
Эксперт Java
2054 / 1927 / 498
Регистрация: 28.12.2010
Сообщений: 7,715
01.07.2016, 22:56 17
brainleo, вы в любом случае создаете промежуточную коллекцию только неявно.
0
brainleo
1 / 0 / 0
Регистрация: 01.07.2016
Сообщений: 13
01.07.2016, 23:35  [ТС] 18
Цитата Сообщение от 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 мс
0
ninjacut
149 / 149 / 51
Регистрация: 30.04.2016
Сообщений: 321
01.07.2016, 23:39 19
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 попробуй.
0
brainleo
1 / 0 / 0
Регистрация: 01.07.2016
Сообщений: 13
01.07.2016, 23:43  [ТС] 20
DavidKarchikyan, в словах была ирония, а ведь
Цитата Сообщение от ninjacut Посмотреть сообщение
Вот здесь вместо a.addAll(c), a = c попробуй.
)) да, получилось 7 с, что ожидаемо )) но этот метод более ресурсоемкий за счет создания новой коллекции в любом случае. )
0
01.07.2016, 23:43
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
01.07.2016, 23:43

Задача при собеседовании!
Не могу понять , как ее реализовать (не очень ясна поставлена задача ) помогите...

Задача на логическое мышление на собеседовании
Имеется несколько классов. В каждом классе есть функция, внутри которой имеется...

Задачка на собеседовании
Дали задачку на собеседовании.A,B-булевские переменные. Есть выражение A?B:!B...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru