One goal achieved

Back flip.

Now I guess the hard part will be working up the courage to do it on grass, wood, concrete...

2011

Some things I did in 2011.

Here's a video of me doing a front tuck on grass.

Back tuck on trampoline

Me dead lifting 315 pounds, and a great shot of my ass. I don't have a video of the 365 pound one.

Reflective Serializer for C#

Reflection would have been a nice feature to have when I was writing MFC C++ back in the day. Anyways, here's an easy way to auto serialize a class. Just have it derive from this class:


    public class ReflectiveSerializer : ISerializable
    {
        public ReflectiveSerializer()
        {
        }


        protected ReflectiveSerializer(SerializationInfo info, StreamingContext context)
        {           
            Type t = GetType();
            foreach (FieldInfo fi in t.GetFields())
            {
                fi.SetValue(this, info.GetValue(fi.Name, fi.FieldType));
            }
        }


        public void GetObjectData(SerializationInfo info, StreamingContext context)
        {            
            Type t = GetType();
            foreach (FieldInfo fi in t.GetFields())
            {
                object o = fi.GetValue(this);
                info.AddValue(fi.Name, fi.GetValue(this));
            }
        }
    }


And then add this constructor to the class:


        protected MyClass(SerializationInfo info, StreamingContext context) : base(info, context)
        {
        }


That class gets called automatically when serializing. The class will then be automatically serialized, provided all of its members can be serialized.

Smoke some trees, yo

A tree is an acyclic graph where each node has one or zero parents and zero or more children.

Binary trees

Number of children is always two.

Ordered binary trees

All nodes left of a given node, n, are <= n; all nodes right of n are > n.

Traversal

Pre-order:

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

In-order:

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

Post-order:

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

Level-order (breadth first search) (needs a queue)

1. enqueue root in q
2. while q is not empty
1. n = q.dequeue()
2. visit n
3. if n.left, enqueue(n.left)
4. if n.right, enqueue(n.right)

Note: changing the queue above to a stack will result in pre-order search (also have to swap the order of 2.3 and 2.4)

Of course, rather than using recursion, you can replace the call stack with an actual stack, and then mark the nodes as visited or not.

Sorting? Awesome fun for whole family

Bubble sort is dumb. Let's look at quick sort and merge sort.

Quick sort:

• O(nlogn) best and average.
• Worst case is O(n^2)
• divide and conquer mother fucker
• probably not stable (same keys may change order)
• pick a pivot, p, in the array (usually in the middle)
• partition into two arrays, one with all values <= p, the other with all values >= p
• the partition step can be done in place
• call quicksort on the two arrays
• if the array size is zero, you're done

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);
}

Now let's try some mergesort:

• worst case is O(nlogn)
• better for using slower data access things like files, tape drives
• don't have to store everything in memory

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();
  }
 }
}

Studying: Day Two

When we last left off I was working on stacks. I'm gonna implement it with a linked list by deriving off my linked list class. On the way I am also going to change the class to use generics. It turns out it's super easy to create generic classes in Java:

class LinkedListNode 
{
    public LinkedListNode(T newData)
    {
        data = newData;
    }

    LinkedListNode next = null;
    T data; 
};

public class LinkedList  {
// etc
};

I'm told that generics in Java are sorta bad because they use type erasure. This is when the compiler "erases" the types of generic classes, so it's compatible with any old non-generic classes. This means if a class has type T, you cannot reference T anywhere in your code, like you could with C++ templates. In fact, the other day one of my coworkers was complaining that they have to duplicate code that creates a new class of a generic type just for this reason.

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;
    }
} 

and then a queue is trivial:

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

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

Study time

In preparation for an interview I have with a certain Mountain View, California software company, I am reviewing and practicing all the basic data structures and algorithms that I learned in second year. I will be live-blogging this. Excited yet? Fuck ya.

Linked list: 

Probably the simplest data structure. Used for lists of shit.

The basic structure is a node (in Java) with a pointer reference to its next node.

class LinkedListNode
{
    public LinkedListNode(String text)
    {
        data = text;
    }

    LinkedListNode next = null;
    String data; // or whatever interesting thing the list holds
};

Some design considerations:

• Should there be a LinkedList class to perform insert/delete/retrieve operations, or should the LinkedListNode do these itself? 
• Probably makes more sense from an OOP perspective to have a separate class absract these ops, so I will write that.
• I should be recording how long I am spending on this. So far it's been at least 15 minutes.
• Apparently I don't know Java that well because I've already fucked up how Java copies references, and had a typo and shit...
• Forgot to update the previous node's next node after deleting
• I forgot to update the root after deleting the root node
• Forgot case where deleting the tail...wait no that's handled automatically
• A lot (all) of these functions could have been written recursively, whatever.

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;
        }
    }
}

Insert: O(n). Access: O(n). Delete: O(n). Some variants are double-linked list (where nodes point back to their next and previous nodes, and circular, where the head points to the tail.

A popular interview question is to reverse a linked list. Here goes:

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;
    }

The above took me a long time, and you can do it without recursion. For some reason I wasn't thinking about doing it moving forward in the list:

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!
    }

Stacks


Stacks are the basic LIFO structure. You can create them with any data structure you like, but typically arrays or linked lists are used. The array implementation was obvious to me:

#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.

So of course you can also create a stack with linked list:

For tomorrow:

Linked lists stacks, queues, priority queues, trees, sorting! Basic shit motherfucker.