Category Archives: Katas

The word ‘kata’ is defined as an exercise in karate where you repeat a form many, many times, making small improvements each time. We know this by a more common word ‘practice’. Code katas are designed to help you improve your programming skills, and are often used as interview questions.

Memoization

1 Reply

A coworker and I were recently discussing SDE interview questions, and I proposed that one of them could involve the use of memoization, which stores calculated values so they don’t need to be recalculated later. He hadn’t dealt with memoization much, so I wrote up two little sampler programs to demonstrate the value it can add. These programs calculate the Nth Fibonacci number, in the typical lazy recursive way (iterative could be better since it wouldn’t require all those stack frames, 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;
            }

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

The non-memoized variety will slow to an unresponsive crawl in very short order, because it has to calculate all the values leading up to the current value, repeatedly for each value; it forgets all the interim values on the way.

The memoized version remembers the interim values, and therefor only calculates them once, storing each in the cache.

Number System Interview Questions

Leave a reply

The following 2 interview questions can help gauge whether a candidate understands number systems.

//converts string '123' to numeric 123.
private static int Atoi(string number)
{
    int result = 0;
    int multiplier = 1;

    for (int idx = number.Length - 1; idx >= 0; idx--)
    {
        char digitChar = number[idx];
        int digitValue = digitChar - '0';
        result += (digitValue * multiplier);
        multiplier *= 10;
    }

    return result;
}

//determines the number of bits turned on in a number
private static int BitCount(int number)
{
    int bits = 0;
    while (number > 0)
    {
        bits += (number % 2);
        number /= 2;
    }

    return bits;
}

Find the intersection of 2 arrays

Leave a reply

The following is an interview question used to determine if you understand pointers, even if your primary managed language doesn’t support the traditional notion of a pointer.

public static T[] FindIntersectionOfSortedArrays(T[] a, T[] b) where T : IComparable
{
    T[] answer = new T[a.length + b.length];

    int aptr = 0;
    int bptr = 0;
    int answerptr = 0;

    while (aptr < a.Length && bptr < b.Length)
    {
        if (a[aptr].Equals(b[bptr]))
        {
            answer[answerptr++] = a[aptr];
            aptr++;
            bptr++;
        }
        else if (a[aptr].CompareTo(b[bptr]) < 0)
        {
            aptr++;
        }
        else
        {
            bptr++;
        }
    }

    return answer;
}

Zorro!

Leave a reply

I’m doing some simplistic string exercises using some of the programming competition problems from years past at EWU. This one is called ‘Zorro’. It takes in an integer representing the width of a ‘Z’ which will be represented on the screen using the letters of the alphabet in sequence (circularly).

Example input:

4

Example output:

abcd
  e
 f
ghij

This is the main body of the code to do it:

        private static void OutputZ(int widthX)
        {
            Console.WriteLine();

            char c = 'z';
            int posX = 0;

            for (posX = 0; posX < widthX; posX++)
                Console.Write(c = NextChar(c));

            Console.WriteLine();

            for (posX = widthX - 2; posX > 0; posX--)
            {
                for (int i = 0; i < posX; i++)
                    Console.Write(" ");

                Console.WriteLine(c = NextChar(c));
            }

            for (posX = 0; posX < widthX; posX++)
                Console.Write(c = NextChar(c));

            Console.WriteLine();
        }

 

Reversing a Linked List

Leave a reply

A very common interview question is to reverse a linked list without using recursion. If you’ve never done it before, this one can be challenging, especially if you don’t think visually.

The basic idea here is to keep a pointer to

  1. The previous node so that you don’t lose what you’re going to point the current node’s next pointer at.
  2. The current node.
  3. The next node, so that when you point the current node’s next pointer at the previous node, you don’t lose the reference to move on to next.

From there, after pointing the current node’s next pointer to the previous node, you just ‘inchworm’ your way forward until you’ve hit all nodes. At the end repoint the head to be where you’re at.

Here’s some code:

public void reverse() {

	if(this.head == null || this.head.next == null) {
		return;
	}

	Node previous = null;
	Node current = this.head;
	Node next = this.head.next;

	while(next != null) {

		current.next = previous;

		previous = current;
		current = next;
		next = current.next;

	}

	current.next = previous;
	this.head = current;

}