Tag Archives: algorithms

How To Hire Great Developers

2 Replies

In a previous set of posts I talked about how the difference between an average developer and a great developer is enormous, how bad developers can effectively cancel-out your good developers, and why you therefor need to hire just the very best.

So how do you tell if someone is good? or bad? What are the core competencies and key indicators of an ‘A’ player developer? And how do you interview for them?

Great Developer Key Indicators

The following is a list I’ve accumulated over time. It’s never complete, and certainly up for discussion, but in my experience is a pretty good set of indicators for whether a developer is an ‘A’ player or not.

Great developers:

  • Can deal with many levels of abstraction simultaneously.
  • Are masters at managing complexity.
  • Know space and time trade-offs of the major data structures.
  • Understands multi-threading, resource locking, and how it’s implemented.
  • Understands that simple is better than complicated, every time.
  • Has used a DVCS (git, mercurial, etc).
  • Are masters at managing expectations.
  • Plays with new technologies and languages and stays aware of upcoming developments.
  • Understands what TDD is and why it’s a valuable practice.
  • Is likely to develop iteratively and incrementally, adding value with each release.
  • Understands how to accomplish loose-coupling and encapsulation, especially in things that are likely to change.
  • Is not a lone-coder who goes dark for long periods of time.
  • Knows how to communicate well, not just with developers, but all levels of management and stakeholders, and can adjust communication vocabulary/style per context.
  • Knows SOLID principles and practices them effectively.
  • Recognizes that code reviews are excellent ways to improve yourself, both as an author or reviewer.
  • Can grasp the bigger picture.
  • Doesn’t just accept work items and marching orders, but also proposes alternatives and improvements.
  • Knows 1 procedural language, 1 object-oriented language, 1 functional language, 1 scripting language, 1 statically typed language, and 1 dynamically typed language. (There is much overlap between these categorizations)
  • Fluent in major design patterns and how/when to implement them.
  • Knows most of these books:  Code Complete, Pragmatic Programmer, Clean Code, Mythical Man Month, Design Patterns by the Gang of Four, Programming Perls, Code: The Hidden Language of Computer Hardware and Software, C by K&R.
  • Keeps up with development blogs/twitter/podcasts.
  • Is highly passionate about software development.

Bad Developer Red Flags

There are some simple things you can do to immediately weed out the really bad developers in an interview scenario.

  • Have them write FizzBuzz; believe it or not most developers do poorly on this, and it’s a great way to identify them early on in the process.
  • Ask them what the last new language or development environment they learned was. If it’s been a long time since they’ve learned a new one, that’s a red flag.
  • Ask them what they think a great developer’s best attributes are. If the answer isn’t in the list above, it’s probably a red flag.
  • Have them explain dependency injection to you, and a simple example. If you get a deer-in-headlights response, it’s a red flag.
  • Ask them to solve problems that involve in-place manipulation of a linked list or string. If they don’t understand pointers or space/time complexities of a problem, that’s a concern. ‘Reverse a linked list’ is a good one to ask.
  • Find out if they have a GitHub/BitBucket/Codeplex/SourceForge.  Look for evidence of development both inside and outside of work.

What NOT To Do

  • Don’t ask questions that are just quick facts. A programmer that knows what port IMAP runs on isn’t going to be a better programmer than one who doesn’t. Knowing little C compiler optimizations doesn’t make you a better programmer.
  • Don’t just ask questions with verbal answers, or open-ended answers. Actually have them write code on the whiteboard. A lot.
  • Don’t use questions that are common enough to where they could be googled before hand or memorized.
  • Don’t just be satisfied that someone answered something correctly. Talk to them about their solution. Ask them to modify it. Ask them to test it. Challenge their thinking.

This is an organic post, and I suspect I’ll add many suggestions from readers.

 

Collision Detection in 2D Games

Leave a reply

Implementing per-pixel collision detection in a 2D game can be accomplished using a variety of methods:

  1. Sprite image rotation, bounds intersection
  2. Sprite translation, per-pixel comparison of of non-alpha-transparent pixels
  3. Sprite translation, maintaining a bounding box, per-pixel comparison of of non-alpha-transparent pixels

The first method assumes that you are rendering your image verbatim, and the image is actually what you are manipulating. This is typically the way you’d be doing things in a Java Swing game. The bounding box of your sprite is effectively the bounding box of your image.

Here’s what that might look like:

    if (sprite.boundingBox.intersects(otherSprite.boundingBox)) {
        //collision!
    }

The second method utilizes matrix transforms (location, rotation, scaling) to figure out where and how to render pixels. This transformation is the most common scenario in C# XNA game development. Since you are essentially plotting pixels right to the screen, no bounding box exists. Each time your game loop runs, it’s necessary to ask the sprite where its pixels currently are and compare them with collidable pixels in the scene. This is VERY expensive, since you have to ask all your sprites on the screen for their current pixel information, ask your player sprite for its pixel information, and then do combinatorial math to determine if any non-alpha-transparent pixels are true for both sets of pixels.

Here’s what that might look like:

public bool CollidesWith(Sprite entitySprite)
{
    Matrix myMatrix = this.Sprite.GetMatrixTransform();
    Matrix theirMatrix = entitySprite.GetMatrixTransform();

    Color[,] myColorArray = this.Sprite.ColorArray;
    Color[,] theirColorArray = entitySprite.ColorArray;

    Matrix myMatrixToTheirs = myMatrix * Matrix.Invert(theirMatrix);

    int myWidth = myColorArray.GetLength(0);
    int myHeight = myColorArray.GetLength(1);
    int theirWidth = theirColorArray.GetLength(0);
    int theirHeight = theirColorArray.GetLength(1);

    for (int x1 = 0; x1 < myWidth; x1++)
    {
        for (int y1 = 0; y1 < myHeight; y1++)
        {
            Vector2 pos1 = new Vector2(x1, y1);
            Vector2 pos2 = Vector2.Transform(pos1, myMatrixToTheirs);

            int x2 = (int)pos2.X;
            int y2 = (int)pos2.Y;
            if ((x2 >= 0) && (x2 < theirWidth) &&
                (y2 >= 0) && (y2 < theirHeight) &&
                (myColorArray[x1, y1].A > 0) && 
                (theirColorArray[x2, y2].A > 0))
            {
                return true;
            }
        }
    }

    return false;
}

The third method is essentially the previous method, with the optimization of a bounding box being maintained around your drawn pixels. Checking for a collision has an early-exit optimization, in that you first check which sprites bounding boxes intersect with eachother, and then only do the per-pixel collision detection on those sprites. This is a much better way to do things, and many orders of magnitude faster.

Here’s what that might look like:

public bool CollidesWith(Sprite entitySprite)
{
    if (!entitySprite.BoundingBox.Intersects(this.Sprite.BoundingBox))
    {
        return false;
    }

    ...
    //rest of above method here
    ...
}

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