Решил поменять специальность и попробовать себя в JAVA. При этом стал проходить достаточно много тестов он-лайн от компаний, на собеседование которых хотел бы попасть. Попалась достаточно интересная задача, возможно, она интересна только начинающим, а кому-то станет очевидной и примитивной, тем не менее я пробовал получить разнообразные варианты решения ее на различных форумах.
Суть задачи такова. Необходимо написать метод, который принимает в качестве аргументов две коллекции ArrayList одинакового размера, например, одна a = [a1, a2, a3, ....], а вторая b = [b1, b2, b3 ...]. Метод должен превратить коллекцию а в следующий вид: a = [a1, b1, a2, b2, a3, b3....]. При этом решение должно быть экономным к ресурсам и процессорному времени.
Первый вариант, который может быть придуман фактически в лоб и этот вариант я тоже видел на форуме:
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++;
}
}
}
Когда тестировал метод, который принимает две коллекции с количеством элементов 1 000 000, то еле дождался результата. Получил 76 867 мс, печально, хотя вполне ожидаемо, когда каждая вставка методом add, сопровождается копированием массива, что находится правее… При миллионе элементов это, увы, очень плохой вариант.
Потом второй вариант, который можно придумать, тоже скорее всего в лоб, это использование промежуточной коллекции, типа:
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 = c;
}
Это заняло около 6 мс. Однако вполне очевидно, что данный способ не вполне экономен в части Memory.
Потом конечно хочется исключить промежуточную коллекцию. Именно этот вариант я предложил на собеседовании, и увы, провалил задание, хотя утешило, что на форуме предлагали и похуже вариант ребята, которые уже не парятся на тему «надо найти стартовую площадку для начала». Вот собственно говоря код:
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 мс. Время ухудшилось, причем значительно. Но плюс естественно есть — это отсутствие промежуточной коллекции. Причем здесь решил «выпендриться», показав, что я знаю как побитовыми операциями я могу сделать умножение на 2. По факту, вряд ли я получил тут экономию процессорного времени, но даже если и получил, то она едва заметна в данном случае.
Последний вариант, я думал оптимизировал за счет того, что использую метод a.ensureCapacity(size * 2) с мыслями, что как минимум я избавлюсь от одного лишнего копирования массива, потому что при превышении текущего размера Array коллекция увеличивает число нового массива в 1,5 больше от текущего, а так как нам нужна в итоге коллекция с удвоенным числом элементов, то это потом приведет еще к одному увеличению размера массива, которое нам по факту не нужно (т.е. чуточку экономит ресурсы Memory), т.е. по факту выглядело бы это так:
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));
}
}
Выгода по времени не существенна, но вроде 1мс есть. Но плюс все-таки есть. Пусть в каждой из коллекций, передаваемых в метод было size элементов, то при вызове метода merge1 там будет size*2 элементов. Для метода merge1 в принципе при вызове a.size() покажет такой же результат, но в основе этой коллекции до вызова метода trimToSize() будет массив с количеством элементов 1,5*1,5*size, т.е. мы сэкономили уток ресурсов.
Вообщем, ближе к самому оптимальному варианту решения задачи с учетом условия задачи, которое как минимум я нашел:
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 мс, и, как мне кажется, перерасхода ресурсов тоже нету.
Задача оказалась достаточно интересной, для ее решения мне дали 30 минут.
Однако, сама постановка задачи вроде и имеет цель оценить знания внутренней реализации коллекции, но в то же время все-таки изменять один из передаваемых параметров в методе является дурным тоном, поэтому стоило бы ее переформулировать немного ее в другом контексте.
Автор: brain_leo
