Codemonkey solutions

AuD_Codemonkeys_1.md

Notes

• All code snippets should pass all unit tests, but may have bugs beyond the tests
• the exercise list contains findSmallestElement_iterative, but codemonkeys does not.
  • the same for singly_linked_list::revert iterative...
  • and for singly_linked_list::find
  • also array_list::get

Binary Search

• new range does not include middle point
• also check for invalid lrm (like for empty array)

public int[] binarySearchStep(Listobject<T>[] array, Listobject<T> element, int[] lrm)
{
    int[] ret = new int[3];
    ret[0] = lrm[0];
    ret[1] = lrm[1];
    ret[2] = (lrm[0] + lrm[1]) / 2;

	// can probably be optimized
    if(ret[1] < ret[0]) {
        ret[2] = -1;
        return ret;
    }

    int cmp = element.compareTo(array[ret[2]]);
    if(cmp == 0) return ret;

    if(ret[1] - ret[0] <= 0){
        ret[2] = -1;
        return ret;  
    }


    if(element.compareTo(array[ret[2]]) < 0)
        ret[1] = ret[2] - 1;
    else
        ret[0] = ret[2] + 1;

    return ret;
}

Linear Search

• make sure to check for null in elem and i

public int linearSearch()
{
    if(getElem() == null)
        return -1;

    for(int i = 0; i < getArrayLength(); ++i) {
        if(getArrayElem(i) != null && getComp().compare(getArrayElem(i), getElem()) == 0)
            return i;
    }

    return -1;
}

Duplicate every second element

public Listobject<T>[] duplicateEverySecondElement(Listobject<T>[] array)
{
    Listobject[] ret = new Listobject[array.length + array.length / 2];
    for(int i = 0; i < array.length; ++i) {
        if(i % 2 != 0) {
            ret[i + i / 2] = array[i];
            ret[i + i / 2 + 1] = array[i];
        } else {
            ret[i + i / 2] = array[i];
        }
    }

    return ret;
}

Insert element in array

• not the most efficient implementation but a natural solution
  • if e.g. an object is inserted at position 0, the whole array is traversed 2 times
  • could be improved with additional checks, don't separate copy and potential move step, but implement them in one loop

public Listobject<T>[] executeInsertElementInArray(Listobject<T> element, int pos)
{
    int nl = pos + 1;
    boolean replace = false;

    if(nl < getArray().length + 1)
        nl = getArray().length + 1;

    if(pos < getArray().length)
        replace = (getArray()[pos] == null);

    Listobject[] ret = new Listobject[nl];
    for(int i = 0; i < getArray().length; ++i)
        ret[i] = getArray()[i];

   if(!replace)
        for(int i = ret.length - 1; i > pos; --i)
            ret[i] = ret[i - 1];

    ret[pos] = element;
    setArray(ret);
    return ret;
}

Insert element into array

• fulfills O(n) complexity

public Listobject<T>[] executeInsertElementInArray(Listobject<T> element)
{
    Listobject[] ret = new Listobject[getArray().length + 1];

    int i = 0;
    for(; i < getArray().length; ++i) {
        int cmp = element.compareTo(getArray()[i]);
        if(cmp <= 0) {
            ret[i] = element;
            break;
        }

        ret[i] = getArray()[i];
    }

    // handle case: element is larger than any object in getArray()
    if(i == getArray().length)
        ret[i] = element;

    ++i;
    for(; i < ret.length; ++i)
        ret[i] = getArray()[i - 1];

    setArray(ret);
    return ret;
}

Delete from array

• Pretty straightforward

public Listobject<T>[] executeDeletionFromArray(Listobject<T>[] array, int index)
{
    Listobject[] cpy = new Listobject[array.length - 1];
    for(int i = 0; i < index; ++i)
        cpy[i] = array[i];
    for(int i = index; i < cpy.length; ++i)
        cpy[i] = array[i + 1];
    return cpy;
}

Rotate pairs in array

public Listobject<T>[] executeRotation(Listobject<T>[] list)
{
    if(list == null)
        return null;

    for(int i = 0; i < list.length / 2; ++i) {
        // swap(list[2 * i], list[2 * i + 1]);
        Listobject tmp = list[2 * i];
        list[2 * i] = list[2 * i + 1];
        list[2 * i + 1] = tmp;
    }     

    return list;
}

Rotate triples in array

public Listobject<T>[] rotateSuccessiveTripleInArray(Listobject<T>[] list)
{
    for(int i = 0; i < list.length / 3; ++i) {
        // swap(2, 1)
        Listobject<T> tmp = list[i * 3 + 1];
        list[i * 3 + 1] = list[i * 3 + 2];
        list[i * 3 + 2] = tmp;

        // swap(2, 0)
        tmp = list[i * 3];
        list[i * 3] = list[i * 3 + 2];
        list[i * 3 + 2] = tmp;
    }

    return list;
}

Rotate triple in array

public boolean rotateTriples(Listobject<T>[] array, int a, int b, int c)
{
    if(array == null || a > array.length || b > array.length || c > array.length)
        return false;

    Listobject la = array[a];
    Listobject lb = array[b];

    array[a] = array[c];
    array[b] = la;
    array[c] = lb;

    return true;
}

Shift array left with rotation

public Listobject<T>[] leftShiftWithRotation(Listobject<T>[] list)
{
    if(list == null || list.length == 0)
        return list;

    Listobject first = list[0];
    for(int i = 0; i < list.length - 1; ++i) {
        list[i] = list[i + 1];    
    }

    list[list.length - 1] = first;
    return list;
}

Shift array right with rotation

public Listobject<T>[] rightShiftWithRotation(Listobject<T>[] list)
{
    if(list == null || list.length == 0)
        return list;

    Listobject[] ret = new Listobject[list.length];
    for(int i = ret.length - 1; i > 0; --i)
        ret[i] = list[i - 1];

    ret[0] = list[list.length - 1];
    return ret;
}

Search second largest element in array

public void searchSecondLargestElement()
{
    for(int i = 0; i < getLength(); ++i) {
        if(getElem(i) == null) continue;
        if(getLargest() == -1) {
            setLargest(i);
            continue;
        }

        int cmpLargest = getComp().compare(getElem(getLargest()), getElem(i));
        if(cmpLargest < 0) {
            setSecLargest(getLargest());
            setLargest(i);
            continue;
        } else if(cmpLargest == 0) continue;

        if(getSecLargest() == -1 || getComp().compare(getElem(getSecLargest()), getElem(i)) < 0)
            setSecLargest(i);
    }
}

Array is sorted

public boolean isSorted(Integer[] a, ArrayComponentComparator<Integer> comp)
{
    if(a == null)
        return false;

    for(int i = 0; i < a.length - 1; ++i) {
        if(comp.compare(a[i], a[i + 1]) > 0)
            return false;
    }

    return true;
}

Priority list push

public boolean push(T key)
{
    // this check is only needed due to inconsistent function
    // description
    if(key == null)
        return false;

    // create new node
    MListElement<T> node = new MListElement<T>(key);

    // test if new head must be set
    // or if it should be inserted before head
    if(getHead() == null || getComp().compare(key, getHead().getKey()) < 0) {
        node.setNext(getHead());
        setHead(node);
        return true;
    }

    // traverse through list to correct position
    MListElement<T> it = getHead();
    while(it.getNext() != null) {
        // check if we found the position. if so insert and return
        if(getComp().compare(key, it.getNext().getKey()) < 0) {
            node.setNext(it.getNext());
            it.setNext(node);
            return true;
        }

        it = it.getNext();
    }

    // insert as last element
    it.setNext(node);

    return true;
}

Priority list pop

public T pop()
{
    if(getHead() == null)
        return null;

    T ret = getHead().getKey();
    setHead(getHead().getNext());
    return ret;
}

Priority list peek

public T peek()
{
    if(getHead() == null) return null;
    return getHead().getKey();
}

Singly Linked list

// clone list elements flat --------------------------------------------------------
public ListElement<T> clone(ListElement<T> el)
{
    ListElement<T> ret = new ListElement<T>(el.getData());
    ListElement<T> it = ret;

    while(el.hasNext()) {
        it.setNext(new ListElement<T>(el.next().getData()));
        it = it.next();
        el = el.next();
    }

    return ret;
}

// duplicate every second element ---------------------------------------------
public MListElement<T> duplicateEverySecondElement(MListElement<T> head)
{
    boolean dup = true;
    MListElement<T> it = head;
    while(it != null) {
        if(dup) {
            MListElement<T> clone = new MListElement(it.getKey());
            clone.setNext(it.getNext());
            it.setNext(clone);
            it = it.getNext();
        }   

        it = it.getNext();
        dup = !dup;
    }

    return head;
}

// clone linked list flat ------------------------------------------------------------
// note: the method LinkedList.setSize is not advertised but needed and exists
// the core of this function was copied from clone list elements flat
public LinkedList<T> clone(LinkedList<T> list)
{
    LinkedList<T> copy = new LinkedList<T>();
    if(list.getFirst() == null)
        return copy;

    ListElement<T> el = list.getFirst();
    ListElement<T> ret = new ListElement<T>(el.getData());
    ListElement<T> it = ret;

    while(el.hasNext()) {
        it.setNext(new ListElement<T>(el.next().getData()));
        it = it.next();
        el = el.next();
    }

	copy.setFirst(ret);
    copy.setLast(it);
    copy.setSize(list.size());
    return copy;
}

// remove duplicates ----------------------------------------------------------------------
public ListElement<T> removeDuplicates(ListElement<T> head, LinkedList_ComparableComparator<T> comp)
{
    if(head == null)
        return head;

    ListElement<T> it = head;
    while(it.hasNext()) {
        if(comp.compare(it.getData(), it.next().getData()) == 0)
            it.setNext(it.next().next());
        else
            it = it.next();
    }

    return head;
}

// insert single ----------------------------------------------------------------------
// make sure to not forget the last 'setLast' check...
// make sure to get the idx downcounting right
public boolean insertSingle(ListElement<T> el, int idx)
{
    if(el == null || contains(el))
        return false;

    if(idx == 0)
        return insertSingleFirst(el);

    ListElement<T> it = getFirst();
    while(--idx > 0 && it != null) it = it.next();

    if(it == null)
        return false;

    el.setNext(it.next());
    it.setNext(el);
    setSize(size() + 1);

    if(el.next() == null)
        setLast(el);

    return true;
}

// insert single first ----------------------------------------------------------------------
public boolean insertSingleFirst(ListElement<T> el)
{
    if(contains(el) || el == null)
        return false;

    el.setNext(getFirst());
    setFirst(el);
    setSize(size() + 1);
    if(el.next() == null)
        setLast(el);

    return true;
}

// insert single last ----------------------------------------------------------------------
public boolean insertSingleLast(ListElement<T> el)
{
    if(contains(el) || el == null)
        return false;

    // check for special (empty) case
    if(getLast() != null) getLast().setNext(el);
    else setFirst(el);

    el.setNext(null);
    setLast(el);
    setSize(size() + 1);

    return true;
}

// insert whole list ------------------------------------------------------------
// the hardest beast so far. Would not be surprised if there are still bugs
// in it that are just not caught by the unit tests.
// Some key points (that were not so clear after reading the exercise) are:
//  - the list to insert (el) may be invalid, e.g. have loops in itself
//    - in this case it seems like it should just false be returned and the original
//      list should stay untouched (at least this works with unit tests)
//  - the algorithm must assure that no element in el that is already in the list
public boolean insert(ListElement<T> el, int idx)
{
    // we probably traverse the whole list here many times...
    // but i guess it was meant to be this way and who cares about performance anyways
    // since we are already in java...
    if(idx == 0)
        return insertFirst(el);

    if(contains(el) || el == null)
        return false;

    // iterate to correct position
    ListElement<T> it = getFirst();
    while(--idx > 0 && it != null) it = it.next();

    // index out of bounds
    if(it == null)
        return false;

    // store the beginning of the rest
    ListElement<T> rest = it.next();

    // find the end of the list to insert
    // also count its size and make sure the list does not
    // contain any elements already inserted
    // insert the elements step by step
    // needed since we cannot know el is a valid
    // list without loops.
    int addSize = 0;
    ListElement<T> end = it;
    ListElement<T> next = el;

    while(next != null) {
        ++addSize;
        end.setNext(next);
        next = next.next();
        end.next().setNext(rest);
        end = end.next();

        if(next != null && contains(next)) {
            it.setNext(rest);
            return false;
        }
    }

    // connect it
    setSize(size() + addSize);

    // set last if there was no end list
    if(end.next() == null)
        setLast(end);

    return true;
}

// insert first --------------------------------------------------------------------------------
// another really ugly one for the same reasons as the one above
// we have to check the inserted list for loops as well as for elements already
// in the list while not allowed to use a set for seen elements or sth.
// The implemented idea is to insert el element-by-element in the front of
// the list after checking that it is not already in there.
// Again (this time the unit tests explicity need this behaviour) should the method
// fail if el contains loop, although this is nowhere specified in the exercise.
// And again el may contain an invalid list, although the documentation states otherwise.
public boolean insertFirst(ListElement<T> el)
{
    if(el == null || contains(el))
        return false;

    // set first element
    ListElement<T> next = el.next();
    ListElement<T> oldFirst = getFirst();

    // we count the number of elements added
    int addSize = 1;
    el.setNext(getFirst());
    setFirst(el);
    if(oldFirst == null)
        setLast(el);

    while(next != null) {
		// assure that the element is not already in the list
		// this also checks for loops in el since we already inserted some
		// elements.
        if(contains(next)) {
            setFirst(oldFirst);
            return false;
        }

        ++addSize;
        ListElement<T> nextNext = next.next();

        // insert next after el
        next.setNext(oldFirst);
        el.setNext(next);
        el.next().setNext(oldFirst);

        // check for last element
        if(oldFirst == null)
            setLast(next);

        // variant
        el = next;
        next = nextNext;
    }

    // increase size by counted number of elements
    setSize(size() + addSize);
    return true;
}

// insert last --------------------------------------------------------------------------------
// The base idea (and bad documentation/exercise) the same as above but
// the implementation is a bit easier sine we append (more naturally in a linked list)
// to the end
public boolean insertLast(ListElement<T> el)
{
    if(el == null || contains(el))
        return false;

    ListElement<T> oldLast = getLast();
    int addSize = 1;

    // handle empty 'this' list
    if(oldLast == null) setFirst(el);
    else oldLast.setNext(el);
    setLast(el);

    el = el.next();
    getLast().setNext(null);

    // append all remaining elements
    while(el != null) {
        if(contains(el)) {
            setLast(oldLast);
            oldLast.setNext(null);
            return false;
        }

        ++addSize;
        getLast().setNext(el);
        setLast(el);

        el = el.next();
        getLast().setNext(null);
    }

    setSize(size() + addSize);
    return true;
}

// get  -------------------------------------------------------------------------------------
public ListElement<T> get(int idx)
{
    ListElement<T> it = getFirst();
    while(--idx >= 0 && it != null) it = it.next();
    return (idx == -1) ? it : null;
}


// remove --------------------------------------------------------------------------------
public ListElement<T> remove(int idx)
{
    if(idx >= size() || idx < 0)
        return null;

    ListElement<T> it = getFirst();

    // check if head should be removed
    if(idx == 0) {
        setFirst(getFirst().next());
        if(getLast() == it) setLast(null);
        setSize(size() - 1);
        return it;
    }

    while(--idx > 0 && it != null) it = it.next();
    if(it == null || it.next() == null) return null;

    ListElement<T> ret = it.next();
    it.setNext(ret.next());
    setSize(size() - 1);
    if(it.next() == null) setLast(it);

    return ret;
}

// remove first --------------------------------------------------------------------------------
public ListElement<T> removeFirst()
{
    if(getFirst() == null)
        return null;

    ListElement<T> ret = getFirst();
    setFirst(getFirst().next());
    setSize(size() - 1);
    if(getFirst() == null || getFirst().next() == null)
        setLast(getFirst());

    return ret;
}

// remove last --------------------------------------------------------------------------------
public ListElement<T> removeLast()
{
    if(getFirst() == null)
        return null;

    ListElement<T> it = getFirst();
    setSize(size() - 1);

    if(getFirst() == getLast()) {
        setFirst(null);
        setLast(null);
        return it;
    }


    while(it.next().next() != null) it = it.next();
    ListElement<T> ret = it.next();
    setLast(it);
    it.setNext(null);

    return ret;
}

ArrayList

// remove
public boolean remove(int i)
{
    ArrayListElement<T> it = getFirst();
    while(i >= 0 && it != null) {
        if(i < it.getN()) {
            for(; i < it.getN() - 1; ++i) {
                it.getData()[i] = it.getData()[i + 1];
            }
            
            it.decN();
            return true;
        }
        
        i -= it.getN();
        it = it.getNext();
    }
    
    return false;
}

// insert
// holy fuck what am i doing with my life
public boolean insertAtPosition(int pos, Listobject<T> key)
{
    if(pos < 0 || getFirst() == null)
        return false;
  
    ArrayListElement<T> it = getFirst();
    while(pos >= 0 && it != null) {
        // case 2
        if(pos > it.getN()) {
            pos -= it.getN();
            it = it.getNext();
            continue;
        }
        
        // case 3
        // split
        if(it.getN() == it.getData().length) {
            ArrayListElement<T> next = new ArrayListElement<T>(getArrayLength());
            next.setNext(it.getNext());
            it.setNext(next);
            int itn = it.getN();
            
            for(int j = 0; j < it.getN() / 2; ++j) {
                it.decN();
                it.getNext().incN();
                it.getNext().getData()[j] = it.getData()[(itn + 1) / 2 + j];
            }
        }
                    
        if(pos > it.getN()) {
            pos -= it.getN();
            it = it.getNext();
        }
        
        for(int i = it.getN() - 1; i >= pos; --i)
            it.getData()[i + 1] = it.getData()[i];
        
        it.getData()[pos] = key;
        it.incN();
        
        return true;
    }
    
    return false;
}

// contains
public boolean contains(T data)
{
    ArrayListElement<T> it = getFirst();
    while(it != null) {
        for(int i = 0; i < it.getN(); ++i)
            if(data == it.getData()[i].getData())
                return true;
        
        it = it.getNext();
    }
    
    return false;
}

Fibonacci

// iterative
public int fibIterative(int n)
{
    if(n < 0)
        throw new IllegalArgumentException("gnurf");
        
    if(n == 0)
        return 0;
        
    int p1 = 1;
    int p2 = 0;
    
    while(n-- >= 2) {
        int fib = p1 + p2;
        p2 = p1;
        p1 = fib;
    }
    
    return p1;
}

// recursive
public int fibRec(int i)
{
    return i <= 0 ? 0 : i == 1 ? 1 : fibRec(i - 1) + fibRec(i - 2);
}

Iterative/Recursive

// proxRootRec
public double proxRootRec(double x, double g, double tolerance) throws IllegalArgumentException
{
    if(x < 0 || g < 0 || tolerance < 0)
        throw new IllegalArgumentException("Go away!");
        
    double n = (x / g) - g;
    if(n >= 0 && n < tolerance || n < 0 && -n < tolerance)
        return g;
    
    return proxRootRec(x, ((x / g) + g)/2, tolerance);
}

// isPalindrome
// Is this StringHelper bullshit really needed?
public boolean isPalindrome(String s)
{
    if(StringHelper.isEmpty(s))
        return false;
        
    for(int i = 0; i < StringHelper.length(s) / 2; ++i) {
        if(StringHelper.charAt(StringHelper.toLowerCase(s), i) != 
            StringHelper.charAt(StringHelper.toLowerCase(s), StringHelper.length(s) - i - 1))
            return false;
    }
    
    return true;
}

// isPalindromeArrayCheck
public boolean[] palindromeArrayCheck(String[] a)
{
    if(a.length == 0)
        return null;
        
    boolean[] ret = new boolean[a.length];
    for(int i = 0; i < a.length; ++i) {
        ret[i] = true;
        String lower = StringHelper.toLowerCase(a[i]);
        for(int j = 0; j < StringHelper.length(lower); ++j)
            if(StringHelper.charAt(lower, j) != StringHelper.charAt(lower, StringHelper.length(lower) - j - 1))
                ret[i] = false;
    }
    return ret;
}