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

 
 
 
Сообщения:8
Добрый день.

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

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

Я предложил следующий вариант решения задачи:
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.
Изменен:11 сен 2016 13:38
 
 
Сообщения:409
Quote:
int size = b.size();
for (int i=0; i<size; i++){
a.add(null);
}

public void ensureCapacity(int minCapacity)
Increases the capacity of this ArrayList instance, if necessary, to ensure that it can hold at least the number of elements specified by the minimum capacity argument.
Parameters:
minCapacity - the desired minimum capacity

Изменен:01 июл 2016 18:38
 
 
Сообщения:409
Quote:
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));
}


void add(int index, E element)
Inserts the specified element at the specified position in this list.
 
 
Сообщения:8
abihle:
public void ensureCapacity(int minCapacity)
Increases the capacity of this ArrayList instance, if necessary, to ensure that it can hold at least the number of elements specified by the minimum capacity argument.
Parameters:
minCapacity - the desired minimum capacity

наверное я не верно использую, но пытался применить этот метод так
допустим коллекция имеет 3 элемента, то тогда если a.ensureCapicity(6), все равно у коллекции 3 элемента (хотя массив с 6-ю элементами), и т.е. когда я всавляю в a.set(5,1) ошибка выход за пределы массива...

а второе сообщение не совсем понимаю как трактовать... ведь когда вставляю в середину методом add массива возникает проблема с тем что находится правее смещается на одну позицию соответствующим копированием массива, что наверное не сильно экономит ресурсы и процессорное время
Изменен:01 июл 2016 18:49
 
 
Сообщения:409
Quote:
ensureCapacity(int minCapacity)
ну да это только увеличит массив внутри ....а размер ArrayList останеться тот же.
 
 
Сообщения:409
я вижу два варианта, или доп. массив(меньше операций) и поочередно добавляем элементы из а и b,
или модифицируем массив а, меньше памяти, больше операций.

и нужно учитывать что ArrayListы могут быть разного размера

я бы так сделал:
public static ArrayList merge(ArrayList a, ArrayList b) {
        ArrayList r = new ArrayList(a.size()+b.size());
        int minSize = Math.min(a.size(),b.size());
        for (int i = 0; i < minSize; i++) {
            r.add(a.get(i));
            r.add(b.get(i));
        }
        if(a.size() == minSize)
            r.add(b.subList(minSize,b.size()));
        else
            r.add(a.subList(minSize,a.size()));
       return r;
    }
Изменен:01 июл 2016 19:21
 
 
Сообщения:8
abihle:
и нужно учитывать что ArrayListы могут быть разного размера

не не , в условиях две коллекции одинакового размера
 
 
Сообщения:409
brain:
abihle:
и нужно учитывать что ArrayListы могут быть разного размера

не не , в условиях две коллекции одинакового размера

не вижу??
но если так, тогда все правильно
кроме разве что

int size = b.size();
	for (int i=0; i<size; i++){
	a.add(null);
	}

лучше наверное так:
a.addAll(b)


сдвиги i<<1, лишнее, компилятор и сам знает как на 2 умножать ))
Изменен:01 июл 2016 19:53
 
 
Сообщения:8
abihle:
не вижу??

забыл написать )
abihle:
сдвиги i<<1, лишнее, компилятор и сам знает как на 2 умножать ))

а тут явно перемудрил :( где-то просто видел что деление на 2 и умножение на 2 лучше битовым сдвигом делать.... поверил на слово, хотел показать знания, оказался идиотом )))

в любом случае спасибо большое, сейчас попробую оценить все идеи с секундомером
Изменен:01 июл 2016 20:00
 
 
Сообщения: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 мс

	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 мс

	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 мс

	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 мс

	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 мс

Экспиремент проводил на коллекциях каждая их которых по 1 000 000 элементов
 
 
Сообщения:409
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.clear(), но это еще замедлит).

время должно быть на уровне merge0

вообще-то
static ArrayList 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));
		}
		return c;
	}

будет самым правильным.
1. Изменять один из передаваемых параметров, дурной тон.
2. можно ведь использовать так a=merge(a,b), намного понятнее
3. По использованию памяти все варианты одинаковы, т.к. при вызове a.addAll(b) будет создаватся новый массив, такой-же как при явном вызове ArrayList c = new ArrayList(...)
4. в последнем варианте меньше вычислений.
Изменен:01 июл 2016 21:03
 
 
Сообщения:8
abihle:
1. Изменять один из передаваемых параметров, дурной тон.

да, но это просто условие задачи, я вот не все описал, у них была описана сигнатура метода void merge(ArrayList a, ArrayList b){//тело метода}
 
 
Сообщения:456
brain:
у них была описана сигнатура метода void merge(ArrayList a, ArrayList b)

У меня бы такая сигнатура вызвала вопросы к интервьюеру:
1. WTF, по логике данный метод должен явно вернуть коллекцию, а он ничего не возвращает. Могу ли я изменить сигнатуру?
2. Если ответ на первый вопрос нет, то тогда вопрос: А в какой из параметров вернуть результат выполнения метода.
Возможно от Вас ждали этих вопросов, а Вы сразу бросились решать задачу.
 
 
Сообщения:8
izon:
У меня бы такая сигнатура вызвала вопросы к интервьюеру:
1. WTF, по логике данный метод должен явно вернуть коллекцию, а он ничего не возвращает. Могу ли я изменить сигнатуру?
2. Если ответ на первый вопрос нет, то тогда вопрос: А в какой из параметров вернуть результат выполнения метода.
Возможно от Вас ждали этих вопросов, а Вы сразу бросились решать задачу.

У меня интервьювер был в виде монитора экрана у себя дома, поэтому как минимум по мне не корректно подразумевать
такой вариант общения. Интревью должно состоять из 3 частей. Первый - онлайн-тест из вопросов и вариантов
ответа, второй - это как раз решение задачи и только третий этпа - личная беседа.

Хотя сейчас посмотрев, что предлагают на форуме и реакцию на такую задачу, меня успокоило в том контексте,
что это все скорее всего ни в коем случае не является индикатором моих личных знаний, там не понятно
что вообще хотели, можно только догадываться. И согласитесь, онлайн-тест, это не способ адекватной оценки
знаний если уже на то пошло. Просто уже не знают как изголяться, создали 7 кругов ада.
Изменен:02 июл 2016 11:55
 
 
Сообщения:456
brain:
У меня интервьювер был в виде монитора экрана у себя дома, поэтому как минимум по мне не корректно подразумевать
такой вариант общения.

Ровно наоборот. Задавать уточняющие вопросы (по почте например) по тестовым задачам это только плюс соискателю и вполне практикуется. Более того если почитать различные форумы посвященные поиску работы то можно обнаружить что такое очень часто встречается. Некоторые работодатели вполне осознанно выдают не полное описание задача чтобы посмотреть не только результат, но как соискатель подходит к решению задачи. Если постановка некорректная/неполная гораздо правильней задать уточняющие вопросы чем додумывать что имелось в виду самому.
Все IMHO.
 
Модераторы:Нет
Сейчас эту тему просматривают:Нет