1. go left
2. visit root
3. go right

template  void qs2 (vector&; arr, int left, int right)
{
 if (left >= right)
  return;

 int i = left, j = right;

    int pivot = arr[(left + right) / 2];
     
    while (i <= j) {
        while (arr[i] < pivot)
                i++;
        while (arr[j] > pivot)
                j--;
        if (i <= j) {
  swap(arr[i], arr[j]);
                i++;
                j--;
        }  
    };

 qs2(arr, left, i - 1);
 qs2(arr, i + 1, right);
}

template  void mergeSort (vector& v)
{
 if (v.size() < 2) return;
 // first divide in two, until only size 1 left
 int n = v.size(); 
 int middle = n / 2;
 vector left;
 left.insert(left.begin(), v.begin(), v.begin() + middle);

 vector right;
 right.insert(right.begin(), v.begin() + middle, v.end());

 mergeSort(left);
 mergeSort(right);

 v.clear();

 // then reconstitute such that the new result is in order
 while (left.size() > 0 || right.size() > 0)
 {
  if (left.size() > 0 && right.size() > 0)
  {
   if (left[0] <= right[0])
   {
    v.push_back(left.front());
    left.erase(left.begin());
   }
   else
   {
    v.push_back(right.front());
    right.erase(right.begin());
   }
  }
  else if (left.size() > 0)
  {
   v.insert(v.end(), left.begin(), left.end());
   left.clear();
  }
  else if (right.size() > 0)
  {
   v.insert(v.end(), right.begin(), right.end());
   right.clear();
  }
 }
}

public class Stack  extends LinkedList 
{
    public Stack()
    {
        super();
    }

    public void push(LinkedListNode node)
    {
        node.next = _root;
        _root = node;        
    }

    public LinkedListNode pop()
    {
        LinkedListNode ret = _root;
        _root = _root.next;

        return ret;
    }
} 

public class Queue  extends LinkedList
{
    public void enqueue (LinkedListNode node)
    {
        insert(node);
    }

    public LinkedListNode dequeue ()
    {
        LinkedListNode ret = _root;
        _root = _root.next;
        return ret;
    }
}

public class LinkedList {
    LinkedListNode _root = null;

    public void insert(LinkedListNode node)
    {
        LinkedListNode current = _root;
        if (_root == null)
        {
            _root = node;
            return;
        }

        while (current != null && current.next != null)
        {
            current = current.next;
        }

        current.next = node;        
    }

    public LinkedListNode find(String data)
    {
        LinkedListNode found = _root;
        while (found != null && !found.data.equals(data))
        {
            found = found.next;
        }
        return found;
    }

// Version 1. delete using 1 extra pointer    public void delete1(String data)
    {        
        LinkedListNode found = _root;
        LinkedListNode prev = null;
        while (found != null && !found.data.equals(data))
        {
            prev = found;
            found = found.next;
        }
        if (found != null)
        {
            if (prev != null)
            {
                prev.next = found.next;
            }
            else
            {
                _root = found.next;
            }

        }
    }

// Version 2. delete without using 1 extra pointer    public void delete2(String data)
    {
        LinkedListNode found = _root;
        // special case where the head is what we're looking for
        if (found.data.equals(data))
        {
            _root = found.next;
            //delete( found); (if we were using c/++)
            return;
        }
        while (found != null)
        {
            if (found.next != null && found.next.data.equals(data))
            {
                found.next = found.next.next;
                //delete( found); (if we were using c/++)
                break;
            }
            found = found.next;
        }
    }
}

public void reverse()
    {        
        reverseEx(_root, null);
    }

    private void reverseEx(LinkedListNode node, LinkedListNode prev)
    {
        if (node.next != null)
        {
            reverseEx(node.next, node);
        }
        else
        {
            _root = node;
        }
        node.next = prev;
    }

public void reverse2()
   {
        LinkedListNode current = _root;
        LinkedListNode prev = null;
        LinkedListNode next = null; // this is necessary, at first I thought it wasn't, i'm retarded

        while (current != null)
        {
            next = current.next;
            current.next = prev;
            prev = current;
            current = next;
        }        

        _root = prev; // i fucked this up, previously I had _root = current, but at this point, current == null. but then again, I just wrote it then debuged it...hopefully i would read it over a couple times in an interview!
    }

#define MAXSIZE 2

template  
class Stack
{
 int _size;
 int _allocated;
 t* _data;

public:
 Stack::Stack() : _size(0), _data(new t[MAXSIZE]), _allocated(MAXSIZE)
 {    
 }

 t pop()
 {
  if (_size < 1)
  {
   throw new exception("stack underflow");
  }
  return _data[--_size];
 }

 void push(t d)
 {
  if (_allocated <= _size)
  {
   _allocated += MAXSIZE;
   t* newData = new t[_allocated];
   memcpy(newData, _data, sizeof(t) * _size);
   delete _data;
   _data = newData;
  }

  _data[_size++] = d;
 }

 Stack::~Stack()
 {
  delete [] _data;
 }
};

• I wanted to try having dynamic memory for some reason, that could grow past whatever, to test I set the maxsize to 2 which is obviously way low
• also wanted to  use templates
• when using a template function, it's just template  <class t> void MyFunction(){..}
• but when using a template class, it's template <class t> class MyClass {...}
• also I played around with std::stuff, I can't believe Fekete doesn't use it! MFC sucks compared to it.