Don't Build Software

If you're a software construction specialist like me, you've written code for thousands of hours. You're good at it. You should be: after all, it's your job. Sort of.

Let's look at it from the perspective of the customer.

(Now you're the customer.)

There is an unavoidable problem with building software: it's slow, expensive, and error-prone. It usually takes longer than you want - good luck getting anything at all quickly. You have to hire expensive employees - a single senior software engineer will easily set you back $100K+ in salary alone - and managers to hire and feed them.

Once you've waited a very long time and paid huge sums of money, there's a fair chance the software you asked for will be delivered. You might not get it at all. Should you get it. it is quite likely that there are bugs in it, only a fraction of which are known. In other words, there are an unknown number of problems of unknown severity in the software you ordered.

(Now you're a software construction specialist again.)

Put it that way, and building software starts to sound like a bad idea. It's the kind of thing you'd only do as a last resort, when all else has failed or no other options are available: not doing the business it would support, supporting the business with more people, or buying existing software, for example.

When you're a software builder, understandably everything starts to look like a problem that can be solved by building software. But it's not the case, and it's important to investigate alternatives before committing yourself, and your customer, to an expensive and lengthy project.

If you've done your diligence and you still believe that building software is the right solution, you should build as little as possible, because everything you build will be expensive, take a long time, and have bugs. More on that in an upcoming post.

Test Driven Anything

A lot more people talk about test-driven development than practice it. Certainly I've talked more than I've done, but I've done nonetheless. And it's so successful that I want to do more.

If tests tell you that code works, and test tells you that features work, and tests tell you that security works... how about the root of all of those? How about your architecture?

It's no stretch to say your should test your architecture - as it's constructed. But how about in the design phase? You should surely be able to test your design. So start your design by writing tests, then build a design that passes them.

Example architecture tests:

The system handles 200,000 concurrent sessions. [yes/no]
Sessions can drop off at any time without warning, and no customer data is lost. [y/n]
Scaling from 200,00 to 500,00 can be accomplished in 3 days (or 3 minutes...) with no programming. [y/n etc.]
The system is resistant to denial of service attack within these constraints and in these scenarios...
The system can be deployed into a third-party cloud due to structure, configuration, data handling...

Once you have a suite of tests (classically, these are requirements, but from a different perspective) you can work with test engineers and other designers to put the system design against these tests, telling you upfront whether your design, implemented correctly, is very likely to pass physical implementations of these tests.

Once you're reasonably certain you have the right design and the right tests (I think you'll discover more tests as you design to fit the tests you have already) then you can start buildingt the tests immediately - working system to follow shortly.

This is also a perfect time to build your threat model and tests for it.

Pragmatic Complexity Analysis for Software Developers

This article is geared towards the sort of complexity analysis you may be asked to do in interviews, so it is fairly superficial, but should also be accurate. Complexity theory is, of course, a vast field of its own, but in practice, most software engineers use only a small part day to day. What an engineer needs to know is how expensive an algorithm is. Understanding complexity lets you critique and revise algorithms in a sensible manner, a particularly useful skill for programmers.

Fortunately, you can learn all you really need to know about basic analysis in a few minutes.

Complexity is expressed in relation to the size of input. For sake of argument, let's consider set of input data such as A = { } and B = { 1, 2, 3 }. When we're talking about input as a variable (could be A, B, or whatever) then we'll call it X.

Time Complexity by Example

Constant Time: Algorithm a:     O(1)

a(X) = { return 199; }

a(A) = 199;
a(B) = 199;

This is just shorthand. In other words, algorithm a(X) always returns 199.

Algorithm a, given input X, always does the same amount of work. The expense of the algorithm - how much time and space it requires to work - is constant and invariant. It does not vary according to the size of the input. This is expressed in Big O notation as O(1).

Time complexity of a(X) = O(1).

In fact, anything done the same number of times regardless of the size of the input takes constant time. Let's consider algorithm a1:

a1(X) = { k = compute 200 trillionth digit of pi; return k; }

This is an example of a time-consuming calculation. Despite its impracticality, it doesn't vary according to the size of the input so it's constant time. (A hint here is that X is never referenced in the function, but it's possible to reference X and still have constant time; maybe covered later.)

Time complexity of a1(X) = O(1).

Linear Time: Algorithm b:        O(n)

b(X) = { for each element of X, add the element value to variable k; return k; }

In other words, b(X) adds up every element of X and returns the total.
b(A) = 0;
b(B) = 6;
Etc.

Let's look at the expense of running the algorithm; how much effort the machine running the algorithm goes through to finish the algorithm's calculations. We can express this in steps.

For set A, algorithm b does nothing. "For each element" occurs zero times because there are zero input elements. Steps = 0.

For set B, algorithm b takes three steps. "For each element" occurs once for each element in the input. Since there are three elements in the input, there are three steps. To be terribly pedantic, here's more detail:

Step 1: add X[0] to k
Step 2: add X[1] to k
Step 3: add X[2] to k

It's easy to see that algorithm b takes one step for every element in its input. This is a direct, linear relationship. We call it linear time. Expressed in Big O notation, this is O(n), "n" being the number of elements in the input. In our examples, n(A) = 0, and n(B) = 3.

Time complexity of b(X) = O(n).

Of course, this isn't all that algorithm b does. Algorithm b also does these things:

Step 0: create variable k and set it to 0
Step 4: return k

Crucially, algorithm b always does these things, invariant to the number of elements in its input. As a result, these steps are done in constant time, and if an algorithm is more complex than constant time in any way, we disregard its constant time elements. We could say that the time complexity of b = O(n) + O(1), but in practice we don't. This reminds me of the +C result in integrals.

Sometimes an algorithm has a chance of stopping early. For example, Algorithm b1:

b1(X,j) = {for each element of X, if its value equals j, return its position k; }

In other words, look though the input until you find j, and then return its position.

Consider b1(B,j). With j = 1, the algorithm takes one step. With j = 3, algorithm b1 takes three steps.

Even in the case of an algorithm short-circuiting right away, we actually consider complexity in the worst case scenario. You must ask yourself the question, "What could possibly go wrong?" And then make the assumption it will take as many steps as it possibly could. It's pessimism for fun and profit.

Time complexity of b1(X) = O(n).

Quadratic Time: Algorithm c:     O(n^m)

c(X) = { for each element of X, add the value of every other element to variable k; return k; }

A high level statement of an algorithm can hide the details of the approach; since an algorithm is an exact set of instructions, not the idea of a set of instructions, here’s enough detail for us to work with:

c(X) =
For each element e1 in X,
For each element e2 in X, except element e2,
Add e2 to j
Add j to k
Return k;

c(A) = 0;
c(B) = 12;

For input set B, these are the steps taken:

Step 1: add X[1] to j
Step 2: add X[2] to j
Step 3: add j to k
Step 4: add X[0] to j
Step 5: add X[2] to j
Step 6: add j to k
Step 7: add X[0] to j
Step 8: add X[1] to j
Step 9: add j to k

It is of course no coincidence that there are 9 steps, 3 elements in B, and 3^2 = 9. Since we're vising each element as many times are there are elements, the number of steps is n times n, or n^2.

Time complexity of c(X) = O(n^2).

Algorithms a, b, and c indicate that one rule of thumb for finding complexity is to look at the loops. Each nested loop (over all elements) increases the exponent of time complexity by one.

No loops = n^0
1 loop = n^1
2 nested loops = n^2
m nested loops = n^m

Logarithmic Time: Algorithm d:      O(log(n))

d(X,j) = { search ordered input X for element value j and return its position k; }

Our implementation of algorithm d will be a binary search. This search probes input X at diminishing intervals to isolate the position element value j must be. In this case we are executing a loop, but not over all elements of the input (for sizeable inputs, anyway).

Quick summary of binary search: check the value of the middle element k of the input set. If it is equal to the target value j, return k. If it is less than j, repeat this operation with the set of input from k to the end of the input. If it is greater than j, repeat this operation with the set of inputs from the start of the input to k. If the set of inputs is at any time empty, return error value (j not found).

The number of probes to either find j or determine that j is not in the input X is the base 2 logarithm of n, the number of elements in input X.

Time complexity of d(X,j) = O(log(n))

While there is a loop in this algorithm, we do not visit each element to complete the loop. For temporal complexity this loop counts as log(n) Within a set of nested loops it counts for less than n; for example, an algorithm that does a binary search, but at each probe loops through the entire input X, has a time complexity O(log(n) x n). This is often written (O)(n log(n)).

Linear Time Part 2: Algorithm e:       O(n+m)

e(X,Y) = { add the sum of every element of X to the sum of every element of Y; return sum k; }

This can be implemented in terms of algorithm b, which sums input.

e(X,Y) = { k = b(X) + b(Y); return k; }

The complexity of this algorithm is best expressed in terms of both X and Y. In standard notation it would be O(n+ m), where n = the number of elements in X and m = the number of elements in Y. This is still considered linear time.

Time complexity of e(X,Y) = O(n+m)

Once you start passing functions as arguments, you can compound complexities for fun and profit.

Exponential and Factorial Time:       O(2^n), O(n!)

Many other exciting complexity types exist, of course.

…And that should pretty much get you through interviews and day to day life.

Tenate Quaestionem: Deconstructing a Simple Coding Interview Question

I have had the pleasure of interviewing at a few companies recently and one thing about my coding-problem-solving style struck me as worth mentioning and explaining. Having conducted quite a few interviews myself (300 or so) I appreciate when candidates make a concerted attempt to understand the problem posed. Perhaps this is because it's something I do myself (we hire people like ourselves, unfortunately, and quite unconsciously) but I also think it's a good practice.

Here's a thorough example.

An engineer asked me to "write a method which takes two Date parameters and returns true if the first is one month after the second, otherwise false". (Lightly paraphrased.) He said I had the freedom to assume that Date objects have convenience methods I might need. Obviously, I immediately wrote

bool IsSecondDateOneMonthLater(Date a, Date b)

{
return a.IsOneMonthEarlierThan(b);
}

And just as obviously he said that was stretching it too far. So I concentrated on learning the true nature of the problem, because it was greatly underspecified. I needed to know many things about what the method was really supposed to do and how it should behave for its customers. I started asking questions.

Are the Date objects in the same calendar?

Motivation: a lot of rules and heuristics would be needed to transform one Date into a compatible calendar so I could do the calculation; assuming the transformation is possible; also assuming that it's really a valid thing to do.

Answer: yes.

Are they in the Gregorian calendar?

Motivation: I know this calendar best. Other calendars may have eccentricies I don't understand well, or which are difficult to calculate. More further down.

Answer: yes.

Are the Date objects guaranteed to be valid? For instance, could one Date be set to a strange day such as February 55th, or be set before the beginning of the calendar, such as Gregorian year 1210?

Motivation: determine how much error checking I must do. If dates will not let themselves be initialized or set to invalid states, then I can count on them to be in sane states.

Answer: yes.

Are the dates in the far future or far past?

Motivation: I'd like to know if I need to worry about special circumstances such as the distance between two years being too large to fit in some number types, or being so close to a boundary that overflow or underflow become a problem. For example, if there are more than 2^64 years between the dates, then I need a special number type to contain and manipulate them. Is it likely I'll be asked to work with dates more than 1.8 * 10^19 years apart? I don't know what this method is used for, so I don't know. It could be for cosmological modeling.

Answer: the dates are in the near future, don't worry about it.

What is a month?

Motivation: It could be a solar, lunar, or calendar month. The time of day could be important, or not. The location could be important, or not. Examples: 8:15AM January 2 and 8:16AM February 2 might, or might not be a month apart, that's a policy decision. I did not ask about location (translating to time zone) but I should have. Due to the dateline, the same GMT, in local time, could be on different days. If location is not a factor, or the Dates are normalized to GMT, I don't have to worry about that. I should have asked that, but didn't. My error.

A month could reasonably be a lunar month. That's a lot more complex, and if so I need to know whether the Date objects have enough information to make this determination.

Answer: the same day number in the next month is the only deciding factor.

Are leap years a factor?

Motivation: This helps clarify his intention. February 2 to March 2 is a month regardless of the varying number of days, right?

Answer: no.

At this point I am a little unsure of this definition, because it means that there's no second date that could be one month from October 31st, ever, there not being a November 31st in any year in the Gregorian calendar. But I run with it, so I write some examples, then write something quite like this code:

bool IsSecondDateOneMonthLater(Date a, Date b)

{

// check that a and b are both not null

// for randomly selected close dates, this is most likely to fail first, so try it first

// to save time.

if (a.Day != b.Day)
return false;

if (a.Month == 12) // December, special case
if (b.Month != 1)
return false;

if (a.month != 12)
return (a.Year == b.Year)
else
return (a.Year == b.Year -1);
}

Now, if it hadn't been an interview, I might have made this code a bit neater, such as:

{
return ( (a.Day == b.Day)

&&( b.Month == 1 ? (a.Month == 1) : b.Month == a.Month)

&& (b.Month == 1 ? (a.Year == b.Year -1 : a.Year = b.Year) );
}

or this:

{
if (a.Day != b.Day)
return false;
if (b.Month== 1)
return (a.Month == 12 && a.Year == b.Year -1);
else
return (a.Month == b.Month && a.Year ==b.Year);
}

They both have their own charm. But it was an interview, and I wrote for simplicity and ease. Writing code on a whiteboard is unnatural, so if I can save brain cycles, I do. I ran the code through my test cases, it worked, and I declared it done.

These questions are summarized - I rephrased a few to make sure I and the interviewer both understood, repeated the question back to him, and asked a few miscellaneous questions. I am sure it added up to 15 or 20 questions. I doubt it was always obvious why I was asking, and sometimes I explained. There's time pressure in interviews.

Is this what the interviewer wanted, or did he want me to just make a bunch of assumptions and bang out some code? I asked whether he felt I was over-analzying the problem or should hurry through it, but he said no. I don't know whether he was being polite or this was his actual expectation. Regardless, I did it my way, and I solved the problem. The end solution was trivial. Getting there was not.

That's a lot of my job. Taking complex problems, usually vague and under-specified, and turning them into clear problems that can be solved, then solving them (or showing someone else how to). Usually fairly simply, but not always. The not-always has led to a number of patents, but that's another story.