Тестовое задание на java

я его уже завалил =) теперь интересно почему.

Implement SimpleArrayList and write unit tests for the class.
Implement ReverseList.reverseList (List list) method and write unit tests for the class.

SimpleArrayList

package questions;

import java.util.Iterator;

/**
 * SimpleList implements some methods of List interface
 *
 *
 *
 */
public class SimpleArrayList
{
    //array to store elements of the list
    Object[] data;

    /**
     * Specified by: the same method of java.util.List
     * @param index
     * @return
     */
    public Object get(int index){
        //todo: implement
    }

    /**
     * Specified by: the same method of java.util.List
     * @param index
     * @param obj
     */
    public Object set(int index, Object obj){
       //todo: implement
    }

    /**
     * Specified by: the same method of java.util.List
     * @param index
     * @param element
     */
    public void add(int index, Object element){
        //todo: implement
    }

    /**
     * Specified by: the same method of java.util.List
     * @return
     */
    public Iterator iterator(){
       return new Iterator(){
         //todo: implement
       };
    }

    /**
     * Specified by: the same method of java.util.List
     * @return
     */
    public int hashCode(){
        //todo: implement
    }

    /**
     * Specified by: the same method of java.util.List
     * @return
     */
    public boolean equals(Object obj)
    {
        //todo: impelment
    }

    /**
     * Specified by: the same method of java.util.List
     * @return
     */
    public int indexOf(Object o){
       ////todo: impelment
    }
}
ReverseList
package questions;

import java.util.List;


/**
 * Test task
 */

public class ReverseList
{
    /**
     * reverse the list given as the param
     * !!! don't change the signature of the method
     * @param list to be reversed
     */
    public static void reverseList(List list)
    {
    //todo: impelment
    }
}
👍ПодобаєтьсяСподобалось0
До обраногоВ обраному0
LinkedIn
Дозволені теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter
Дозволені теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter

ваша реализация метода set нарушает контракт. вместо того, чтобы бросать исключение IndexOutOfBoundsException, она расширяет массив (this.extendArrayIfNeeded (index+1);), если индекс выходит за границы массива. то же с реализацией indexOf, если параметр равен null: вы должны были найти первый элемент, равный null, а вы возвращаете всегда −1.

вы, наверное, хотели применить паттерн нулевого объекта (getList — это не самоинкапсуляция поля, не отложенная инициализация), тогда нужно было определить
private static final Object [] nullValue=new Object [0];
и инициализировать им массив данных:

private Object [] data=nullValue; (если хотели сэкономить память и одновременно избежать NullPointerException)., а так у вас для каждого нового экземпляра создается массив нулевой длины, который невозможно никак использовать, поэтому постоянно будет вызываться сборщик мусора.

для копирования содержимого массива лучше использовать System.arraycopy (тем более, что этот метод может перемещать часть массива с сохранением содержимого); размещать новый массив оптимальней сразу большего размера;

в реализации next лучше было бы заменить дублирующийся код (if (pointer + 1 > list.length — 1)...) на вызов hasNext; цикл в changeArrayLength — не использует инвариант list.length<newlength, поэтому условный оператор там лишний, а еще лучше использовать arraycopy;

программа будет легче читаться, если не использовать ссылки this, не использовать логические литералы в выражениях сравнения ((list [i].equals (o) = = true)), использовать знания о приоритете операторов и убрать лишние скобки;

реализация equals слишком похожа на стандартную Eclipse; hashcode наверное, нужно было реализовать самостоятельно, без помощи arrays.hashcode;

наверное, нужно было все же реализовать интерфейс java.util. List и бросать исключения UnsupportedOperationException в нереализованных методах;

<p> Может Вы забыли использовать при реализации JUnit? </p>

Было такое условие?

Еще можно увеличивать массив не на единицу каждый раз, а в два раза. Тогда сложность add будет стремиться к O (lg n) вместо O (n).

С какого это перепугу там логарифм получился? Можно посмотреть выкладки? Да и фраза «стремится к О (ln n) » по меньшей мере комична.

Еще можно юзать dynamic arrays, там вставка в конец будет вообще за константу происходить.

Не так выразился. Имелось ввиду, что в первом случае, чтобы вставить М элементов, нужно M ресайзов, а во втором — lg M.

> Еще можно юзать dynamic arrays, там вставка в конец будет вообще за константу происходить.
О них и речь.

> О них и речь.

dynamic arrays это не увеличивать масив в два раза при вставке, набери в гугле.

В них не надо копировать все элементы при ресайзе вообще.

en.wikipedia.org/..._amortized_cost

Я говорил об этом. А ты о чем?

Хм, похоже я изобрел новую структуру данных: она состоит из массива указателей на другие массивы в которых и лежат данные. Когда добавляем элемент и текущего массива не хватает, то мы создаем новый массив в два раза больше предыдущего, и добавляем указатель на него в массив указателей.
Временные характеристики будут такие же как у джавовского ArrayList за исключением того что добавление в конец будет занимать в худшем случае логарифмическое время (нужно рисайзнуть масив указателей) против линейного (нужно скопировать старые элементы) у ArrayList.

Я почему то думал что это и есть dynamic array.

> Хм, похоже я изобрел новую структуру данных

Вы придумали HAT? Только там вроде бы массивы одинаковой длинны.

Коментар порушує правила спільноти і видалений модераторами.

Кстати, нигифа, так как это описывает википедия, ХАТ при полном заполнении должен рисайзнуть не только масив указателей, но и все массивы с данными: When a hashed array tree is full, its directory and leaves must be restructured to twice its prior size to accommodate additional append operations, что делает сложность добавления в худшем случае линейной (нужно мувнуть все элементы), а у меня она логарифмическая (нужно мувнуть только элементы массива указателей).

Единственное, в твоем варианте доступ к элементу будет несколько медленнее, чем в обычном массиве.

Похоже на en.wikipedia.org/wiki/VList

С этим полностью согласен.

Только обращение к элементам в конце списка у VList’а будет вроде как дольше (там, вроде, используется связный список вместо массива).

И еще один плюс reality_hacker’у в java такая структура — это простой многомерный массив.

Но все же сомнительно что такое ожидали от человека на должность джава джуна.:)

> Только обращение к элементам в конце списка у VList’а будет вроде как дольше

Ага, lg n worst case

я не совсем понимаю, может надо было скопипастить исходники java и на самом деле тест показывает умения тестируемого работать с архивами и поиском файлов?

SimpleArrayList

package questions;

import java.util.*;

/**
* SimpleList implements some methods of List interface 
*/
public class SimpleArrayList{	
//array to store elements of the list
Object[] data;

/*
* Due to task, there are no words about exceptions.
* So, i will not catch them.
*/  

/**
* Specified by: the same method of java.util.List
* @param index
* @return
*/
public Object get(int index){
	Object[] list = this.getList();
	
	return list[index];
}

/**
* Specified by: the same method of java.util.List
* @param index
* @param obj
*/
public Object set(int index, Object obj){
	this.extendArrayIfNeeded(index+1);
	
	Object[] list = this.getList();  	
	
	Object oldItem = list[index];
	list[index] = obj;
	
	return oldItem;
}

/**
* Specified by: the same method of java.util.List
* @param index
* @param element
*/
public void add(int index, Object element){
	this.changeArrayLength(this.data.length+1);
	
	Object[] list = this.getList();
	
	for (int i = list.length-1; i > index; i—){
		list[i] = list[i-1];
	}
	
	list[index] = element;
}

/**
* Specified by: the same method of java.util.List
* @return
*/
public Iterator iterator(){
	return new Iterator(){
		private int pointer = −1;
		//private boolean canBeRemoved = false;
		
			@Override
			public boolean hasNext() {
				Object[] list = getList();
				//return list[pointer+1] != null;
				return pointer + 1 < list.length;
			}

			@Override
			public Object next() throws NoSuchElementException {
				Object[] list = getList();
				if (pointer + 1 > list.length — 1)
					throw new NoSuchElementException();
					
				pointer++;
				//canBeRemoved = true;
				
				return list[pointer];
			}

			@Override
			public void remove() throws 
			//IllegalStateException, 
			UnsupportedOperationException{
				//original SimpleArrayList has no any removal methods
				//so it’s illogically to make it accessible through Iterator interface
				throw new UnsupportedOperationException();
				//but, i can do it =)
				/*if (canBeRemoved == false)
					throw new IllegalStateException();
				
				Object[] list = getList();
				list[pointer] = null;
				
				canBeRemoved = false;
				*/				
			}  		
		};
}

/**
* Specified by: the same method of java.util.List
* @return
*/
public int indexOf(Object o){
	if (o == null)
		return −1;
	
	Object[] list = this.getList();
	
	for (int i = 0; i < list.length; i++){  		
		if ((list[i] != null) && (list[i].equals(o) == true))
			return i;
	}
	
	return −1;
}

/**
* Specified by: the same method of java.util.List
* @return
*/  
	public int hashCode() {
		final int prime = 31;
		int result = 1;
		result = prime * result + Arrays.hashCode(data);
		return result;
	}

/**
* Specified by: the same method of java.util.List
* @return
*/
	@Override
	public boolean equals(Object obj) {
		if (this == obj)
			return true;
		if (obj == null)
			return false;
		if (getClass() != obj.getClass())
			return false;
		SimpleArrayList other = (SimpleArrayList) obj;
		if (!Arrays.equals(data, other.data))
			return false;
		return true;
	}

	protected Object[] getList(){
	if (this.data == null)
		this.data = new Object[0];
	
	return this.data;
}

protected void extendArrayIfNeeded(int newLength){
	Object[] list = this.getList();
	
	if (list.length < newLength)
		this.changeArrayLength(newLength);
}

protected void changeArrayLength(int newLength){
	Object[] list = this.getList();
	Object[] newArray = new Object[newLength];
	    
	for (int i = 0; i < newArray.length; i++){  		
		if (i < list.length)
			newArray[i] = list[i];
		else
			break;
	}
	
	this.data = newArray;
}  
}

Бегло просмотрел: — нет дженериков; — класс не реализует java.util. List; — метода getList () — это бред — это должно было быть в конструкторе; — метод add (int index, Object element) — про arraycopy слышали?

— нет дженериков; — класс не реализует java.util. List;
какое тз выдали так и работаем.

getList () — это бред — это должно было быть в конструкторе;
en.wikipedia.org/..._initialization,
а теперь представляем ситуацию когда по умолчанию надо инициализировать массив в тысячу — две элементов... — метод add (int index, Object element)
что здесь не так?

> en.wikipedia.org/ _initialization

Спасибо, я знаю что такое lazy initialization. Вы считаете что этот подход здесь уместен, при любой операции будет дергаться метод и проводится проверка которая отработает только 1 раз вместо работы напрямую с полем (ваш же пример с тысячей элементов)

> > метод add (int index, Object element)
> что здесь не так?
download.oracle.com/....html#arraycopy (java.lang. Object, int, java.lang. Object, int, int)

Когда-то давно он был быстрее ручного копирования.

уместен, по скольку мы так-же избавляемся от NullPointerException при работе с этим полем.

> уместен, по скольку мы так-же избавляемся от NullPointerException при работе с этим полем. Какой NullPointerException? Массив надо было инициализировать в конструкторе.

lazy initialization — уместен когда инициализация значительно тяжелее чем доступ к элементу.

потом, внезапно, во время выполнения какого-то из методов, происходит внезапный СеверныйЗверекException, массив становится null и получаем нерабочий инстанс класса. так?

Не понял. Поясните пожалуйста.

теперь мои реализации

ReverseList

package questions;

import java.util.*;

/**
* Test task
*/
public class ReverseList
{
/**
* reverse the list given as the param
* !!! don’t change the signature of the method
* @param list to be reversed
*/
public static void reverseList(List list){  	
	int size = list.size();
for (int leftIndex=0; leftIndex < size / 2; leftIndex++) {
	int rightIndex = size — leftIndex — 1;
	Object left = list.get(leftIndex);
	Object right = list.get(rightIndex);     
	list.set(leftIndex, right);
	list.set(rightIndex, left);
}
}
}

Підписатись на коментарі