Memoization

A coworker and I were recently discussing SDE interview questions, and I proposed that one of them could relate to memoization, which stored calculated values with the intent of not needing to recalculate them later. He had never heard of memoization, so I wrote up two little sampler programs to demonstrate the value that memoization can add. These programs calculate the Nth Fibonacci number, in the typical lazy recursive way (iterative could be better, but this is just to prove a point).

First, here is the non-memoized form:

#include <iostream>
 
class Fibber
{
    private:
        std::map<unsigned int, double> _fibs;
 
    public:
        double fib_of(unsigned int idx)
        {
            if(idx <= 2)
            {
                return 1;
            }
            else
            {
                return fib_of(idx - 1) + fib_of(idx - 2);
            }
        }
};
 
int main()
{
    Fibber x;
 
    for(int i = 1; i <= 100; i++)
    {
        std::cout << x.fib_of(i) << std::endl;
    }
}

Now, if we take that same program but add memoization:

#include <iostream>
#include <map>
 
class Fibber
{
    private:
        std::map<unsigned int, double> _fibs;
 
    public:
        double fib_of(unsigned int idx)
        {
            if(idx <= 2)
            {
                return 1;
            }
            else
            {
                double ret = 0;
                std::map<unsigned int, double>::iterator loc_iter = _fibs.find(idx);
                if(loc_iter != _fibs.end())
                {
                    ret = loc_iter->second;
                }
                else
                {
                    double calculated = fib_of(idx - 1) + fib_of(idx - 2);
                    _fibs.insert(std::pair<unsigned int, double>(idx, calculated));
                    ret = calculated;
                }
 
                return ret;
            }
        }
};
 
int main()
{
    Fibber x;
 
    for(int i = 1; i <= 100; i++)
    {
        std::cout << x.fib_of(i) << std::endl;
    }
}

The difference in performance between the two is night-and-day. Try it out!

Removing while iterating

The context of this post is Java, but the concept applies to other languages as well. (C#, etc).

Have you ever encountered a need to remove elements from a collection while iterating over it? This is not allowed:

 
for(Foo f : fooList) {
    if(f.bar()) {
        fooList.remove(f);
    }
}

A ConcurrentModificationException will be thrown, since you are attempting to modify a list during iteration. It makes sense; after all, if you remove something, the list is in a new state, and who is to say what the next element is at that point?

There is however, a solution, and ironically, it involves regressing to a commonly used pattern in C++, which is to use an iterator. An iterator provides you with access to the next element in its iteration, as well as access to the original iteration index. This allows you to manipulate whatever list you are iterating over, since your iteration does not rely on its current state, only the state of which the iterator was based on.

Here is the above example reworked:

  for (Iterator<foo> iter = fooList.iterator(); iter.hasNext(); Foo f = iter.next()) {
    if(f.bar()) {
      iter.remove();
    }
  }

The .remove() option on the iterator removes the element from the underlying collection, but does not impact the iterator. Problem solved.

Generics vs Templates

Are you familiar with the difference between Generics in languages like Java and C#, and Templates in C++ ? Functionally they serve the same purpose, to dynamically type a class, but they are actually quite different, and may not be implemented as you might expect.

Let’s start with Generics. In languages like Java and C#, you can declare a class like so:

    public class Foo<t>
    {
        private T _bar:
        public Foo(T bar)
        {
            _bar = bar;
        }
    }

Doing so will force the consumer of this class to specify its type like so:

    Foo<string> myFoo = new Foo<string>("Stringly typed!");

The type is enforced to be ‘String’ in this case. But is the enforcement at compile time or runtime? You might be surprised to learn that it is at compile time. It is nothing more than compile-time convention to force the programmer to be type-safe. The actual objects at run-time have no notion that they can or cannot be a certain type, and are simply expected to be properly enforced at compile time.

So now that we understand how they work in Java and C#, what about Templates in C++? They serve a very similar purpose, but how are they actually implemented compared to the other languages? It turns out that at compile-time C++ will actually generate all possible combinations of the template based on the possible types that could be passed to it as determined by the compiler looking at the rest of the code. This makes sense, since the name of the feature is ‘template’, but it’s not often thought about in that fashion by average C++ developers.

Maximum Depth of Binary Tree

This is a fairly common interview question. Here is one possible solution using recursion:

int getMaxDepth(node n)
{
    if(n == null)
        return 0;
 
    l = 1 + getMaxDepth(n.left);
    r = 1 + getMaxDepth(n.right);
 
    return (l > r ? l : r);
}

Interview Code Snippets for 10/2009

Today’s potential interview question is to reverse a linked list, without recursion. This one can be rather tough on the brain if you don’t think visually, but the basic idea here is to keep a pointer to:

• Keep a pointer to the next node so that you don’t lose a way to access it once you reverse the direction of the prior node’s ‘next’ pointer.
• Keep a pointer to the last node so that you have a way of pointing the current node back (the above is required so that you don’t lose where it formerly pointed.)
• ‘Inchworm’ your way forward in this manner until you’ve hit everything, and at the end repoint the head to be where you’re at.

Here’s the code (Note that NodePtr is simply a typedef of a boost::shared_ptr – it’s a ‘smart’ pointer.):

void LinkedList::reverse()
{
	if((_head == NULL) || (_length == 1))
	{
		return;
	}
	else
	{
		NodePtr previous = NodePtr();
		NodePtr current = _head;
		NodePtr next = NodePtr();
		while(current)
		{
			next = current->next;
			current->next = previous;
			previous = current;
			current = next;
		}
 
		_head = previous;
 
	}
}

C++

Nursing memory management wound caused by blasting leg off with a C++ shotgun. It’s OK C++, I don’t hate you, I just wish you would retire.

Coffee and See Plus Plus

Do you remember the first time you had coffee? A lot of people relate their first experience as a bad one, and that coffee is an acquired taste. I can’t relate to that because I’ve always loved coffee, from my very first taste, but I understand the notion, and I want to relate that idea to C++ for a minute. C++ is a language that by all modern standards is an awful mess, but one that is arguably most important to learn and understand due to the manual management of the heap and stack.

Ok, so lets say you dive into C++ because you’re interested in knowing everything there is to know about programming. You discover it’s like your coffee experience; It’s bitter, it smells funny, and gives you jitters, but you keep on sipping it because you know it will give you benefits. Fast forward 6 months, and you’re practically hooking it up to your arm with an IV needle. Now you feel very comfortable with it, and you’ve learned a significant amount of other related knowledge as a result of your endeavours. You’re ready to move on to new things, satisfied that you used it as a learning tool, but are you really done with it? Ohh no.

And in that sense, it’s more like cocaine than coffee.

The gaming industry, or any industry that possesses an interest in high-performance computing applications, is addicted to C++. Regardless of how far managed code and garbage collection has come, or how good virtualization abstractions have gotten, they cling to it proclaiming “JUST ONE MORE HIT MAN, JUST ONE MORE HIT”. I sympathize on the one hand because C++ ought to be mandatory learning material for computer science students (because it does teach you about how things work under the covers), but at the same time, haven’t we come far enough with the performance of other languages that we can just go ahead and take C++ out back of the shed?