Category Archives: CodeProject

The real answer to the FizzBuzz interview question

A popular interview question is coding FizzBuzz.  Now I’ve had similar experiences to what is shown at Coding Horror — I had a description for a trivial piece of code that would offer insight into the depth of engineering skill, with my careful posing of the requirements.


I had a sheet with this written down, so I would always say it in the same carefully-crafted way.  I lost that some years ago, but here is the problem from memory:

Write a class whose constructor takes two integral arguments, and has members that return their sum and their difference.

Trivial enough?  Not even a “problem” with logic to be considered; just a routine microtask that anyone with any fluency can express without having to think about it.

What I expected was to see how well the applicant processed the statement of requirements: making assumptions, or asking for clarification.  I figure an experienced engineer would ask what was meant by integral, or use a typedef to abstract the decision of which integer type to use and specify it at only one point.  More fluent coders would write it as a template.

I was very surprised to find that most applicants who got past the screening process thus far had trouble writing a C++ class at all!  The best insight I had was from someone who explained that he usually uses the IDE and doesn’t know the details of syntax on how to write a class definition.  Because of the reliance on what Visual Studio calls wizards, we dubbed these people Wizards’ Apprentices with a reference to the segment from Disney’s Fantasia.  The story is simple: the young apprentice tries to use his master’s power but cannot control it; what we would recognize as a buggy program.

What are you showing them?

Now suppose that you are fluent in C++ (or whichever language you are using) and would have no trouble jotting down a piece of code that does what you want.

I see many solutions to FizzBuzz, as well as many other problems, that are written in a way that is completely unlike what we see in “real” code.  Someone who can effortlessly produce this might be in “scripting mode” which is used for single-use small programs — written quickly, sloppy, and highly specialized.  It does not illustrate good software engineering practices, and the interviewer can’t tell if the applicant always (only) writes like that, or is capable of working on projects like they have: large bodies of code, need for maintainability, testability; follows good practices, etc.

So, I thought about FizzBuzz as if it were a small utility feature that was ordered for use in a large project.


Certainly, a short piece of code can be written using up-to-date style and best practices as applicable for software development at the scale that is involved in real projects at work.

But I also thought about how much “good engineering” I can illustrate without making the result not-so-trivial.  Here is what I came up with:

  1. Separate the logic from I/O.
    Most solutions to simple problems like this mix console I/O with the logic, which is completely unlike real programs in multiple ways.  It should not directly solicit input from the user as if he was a text file, or print output in the middle of the work; the “solution” should feature a function that takes parameters and produces results to return.
    As with real projects, this can be called by a unit-testing main program as well as find a home in the application that needs that feature.
  2. One thing that bugs me about the typical implementation of FizzBuzz is the explicit repetition of code, checking each factor and often the combination as well.  Don’t duplicate code that varies only by a data value!  Instead, store the values and loop over them.
  3. Be mindful of future enhancements.
    Code always gets more complex over time.  It is an art forged by long experience to balance future maintenance with extra work now.  Don’t program in features that are not needed — rather, anticipate what will be changed or added later and consider that in the overall design, and allow for such things when it does not add complexity to the task at hand.  (I can probably write a whole essay on this topic.  Message me if you have examples or general thoughts.)


I was very successful in the point 2 makes the code simpler and shorter.  Point 3 takes the form of putting the configuration at the very top of the file, and showing how it can be extended; and the extensibility is free due to the architecture noted in point 2.

There are the needed #includes at the top of the file, and then the interesting part starts off with:

constexpr std::pair<int, const char*> fbchart[] {
    { 3, "Fizz" }, { 5, "Buzz" },  // standard FizzBuzz
    { 7, "Boom" }  // easily generalized and extended by adding to this chart!

When I wrote this, Visual Studio’s C++17 compiler is still in per-release, and part of the exercise for me was to use new features and see where style needs to be updated.

constexpr is the new static const.”  Naturally, this tabular data will be declared as constexpr.

Now, why did I use const char* rather than an object type?  This was a deliberate choice.  First of all, the use of this table (described later) is flexible in what it can take, so I don’t require a std::string here even though that’s what will be used in the constructed object.  There is no need to store a std::string object here, which would make another copy of the lexical string literals, and string does not have a constexpr constructor.

The usual worries about primitive C-style strings do not apply since this is constant data.  After all, do you worry about writing cout<<"hello"; and demand that you store that in a string object before passing it to the function?

A hot-off-the-press alternative would be std::string_view.  But there is simply no need here.  I chose not to use gsl::zstring, since it would be the only use of the Guidelines Support Library in the program, and there is no question that C-strings are being used since they are right there, and only right there.  This is not a function parameter that needs documenting.

Likewise for the use of the plain array, rather than std::array.  Arrays are not as poor as they used to be: with the preference for free functions begin, end, size, etc. what does the object wrapper do that the plain doesn’t?  Only the regular value semantics of passing and assigning — and I’m not doing that.

string fbencode (int n)
    string retval;
    for (auto& [div, codeword] : fbchart) {
        if ((n%div)==0)  retval += codeword;
    if (retval.empty())  retval= std::to_string (n);
    return retval;

Here is the meat:  a simple stateless function that accepts the number as a parameter and produces the results to return as a string.

The loop has a one-line body, and it is automatically iterated over the data table shown earlier.  That is why adding another item just works.  This code is smaller and simpler than the cascade of tests you normally see.

// and to drive it: 
int main() {
    using boost::irange;
    for (auto n : irange(1,101)) {
        cout << n << ": " << fbencode(n) << '\n';

In the main, I avoided a legacy for-loop by using Boost.Range 2.0. That is tried and true for production work. I’ve not tried to get the latest Visual Studio compiler drop to swallow Range-v3 yet.


Not only does this show fluency in C++ with up-to-date skills, it is well crafted and provides a number of discussion points.  As summarized along with the code samples, I can explain why I did things a certain way, alternatives considered, what I might do under different circumstances, etc.

It is good to understand the constructs used and choose them purposefully, not apply things in a cargo-cult or voodoo programming situation.  On either end of the interview process, understand that simple coding problems can give far more insight than simply finding out whether the applicant can “write code” at all.

Error Handling Concepts (again)

In Ancient Times, I was privileged to be among those who deliberated upon a fundamental question in C++ programming philosophy: “Whither exception handling?”  Exception handling was still in the conceptual stages then, and the air was charged with excitement.

Twenty two years ago, I wrote an article for Windows Tech Journal recounting my experience a few years earlier in comparing error handling mechanisms of exceptions vs. error code returns.  In particular, I discovered that using both was an impedance mismatch, with code always wrapping the other kind to convert it:  catch the exception and return an error code; or test for an error code and throw an exception.  This blather is a road leading towards a pure exception handling approach.

I’ve scanned in the magazine pages and it can be seen on my web server.

Now, the C++ community is coming full circle it seems.  Everything old is new again.

In the 2017 standard we have std::optional which is the most basic “sum type”. In a talk Andrei Alexandrescu started with the example of the variant and asked the audience “Why is it called a ‘sum type’?” My own answer: because you don’t know its type but it returns something!

Seriously, in this presentation he also said “Remember when I told you the worst thing that happened to humankind was? I see the std::optional.” He introduces the expected class (still being argued about in committee as I write this), as the right solution giving the best of both worlds:  It can return a result or an error code, and the caller can take the step of checking the error code or just access the result without checking, in which case it throws an exception if it’s actually an error state.

Meanwhile, Niall Douglas rips expected.  Based on the peer review results of Boost.Outcome, he notes for consideration that many of the findings apply to the current expected proposal.

There’s no substitute for experience

This is part of a series of posts I’m writing about using toy projects and other exploration to get a hands-on feel for the new C++17 features, library, and style, as well as the behavior and real limitations of the compiler.

I coded up a very simple recursive descent parser, since it’s been noted that the new std::string_view is especially suited for parsers.  (There is a lot of sentiment about string_view being problematic and evil, but that’s another story.)

Now a recursive descent parser is one of the few places, it is generally acknowledged, where throwing an exception as a form of control flow is genuinely a good decision.  But, this simple grammar doesn’t have enough depth to need anything like that.

The interpreter (it does the work as it parses, as opposed to building a tree representation to be evaluated later) throws exceptions in case of errors.  The user of the class will know this as the way it gives errors on bad input or run-time conditions.

The parsing step itself, though, makes heavy use of std::optional.  As is the nature of such a parser, a production (grammar rule) might be called where this thing may or may not exist: optional parts in the syntax and alternatives and lists all lead to logic that says, “read one of these; did you get one?  No? OK, skip it (or try reading one of those instead).”

Other callers need to read something, period.  In that case, the caller needs to check for an error (just as it did when it was optional) and throw an exception.  This code is what gave me déjà vu:

skip_ws (input);
auto LHS= read_identifier(input);
if (!LHS)  raise_error(input, 4);
read_required ('=', input);
auto terms_result= read_terms(input);
if (!terms_result)  raise_error (input, 5);
if (!input.empty())  raise_error (input, 3);
set_value (*LHS, terms_result);
return *LHS;

The function read_required throws an exception itself if it can’t do what was asked.  read_terms and read_identifier, like most functions modeling grammar productions, return an optional-wrapped value.

Call a function, then check the return value and throw.  This is done repeatedly in these functions.  That is exactly the kind of mismatch I saw all those years ago.

From the nature of the optional returns, it is the caller who decides on the error code.  In a more complex grammar, I can easily see wanting to propagate that or modify it as it passes back up the call tree.  But in the case of optional, there is no error code coming up — just the lack of a result.

In testing this with different syntax error test cases, I found places where I was not checking the return code.  This can coredump because dereferencing the optional does not do any checking on whether it contains a value.  (On the other hand, there is a value() member function that does check.)  I guess I’m so used to writing such that functions do what they are asked (or don’t return at all) that writing in a style where every call is followed up by an explicit test is challenging as well as ugly and obfuscating.

It’s back to the assessment I made when promoting exceptions in the first place:  look at this block of code — what does it do?  It’s main purpose is a bunch of if statements and errors.  Where is the real logic I came here for?  The testing is drowning out the real work.

Would using expected/outcome be better for this?

If the called function loaded the result with an error code rather than just the lack of result, and the attempted dereference would throw an exception, then I would not have to check after every call but still could when I wanted to.

But… it is the caller that knows what error code to assign.  Furthermore, what about the specifics of the exception and its payload?  If productions returned an error code (just an enumeration), the exception still needs to be the parser_error type and include the cursor position.

Its like the (deeply nested) called function needs to interact with the caller to formulate the proper error.  Catching and modifying and re-throwing is something that will not go over well with modern implementations, as throwing is very slow.

I’m reminded of the exception class I wrote and used long before C++ was a standard: I included a feature to simulate dynamic scoped values-of-interest.

Parsing is one case where we really care about details across several levels of function call, in order to get meaningful feedback on the error.  In more normal circumstances, you tend to rely on logging.  Even so, having a speculative log — include this line if an error is logged; flush it upon success — is very helpful and cuts back on the spew of irrelevant information logged.

But the same technique could be used to generate a more meaningful exception, adding information as the stack is unwound.

Besides catch to deal with a problem after it occurs, and destructors to automatically clean up resources, we need some way to prepare for a possible error.  This would be primarily for reporting, not for recovery actions.  That’s probably why it has been neglected as a topic — destructors are perfectly good at cleanup and using them means we don’t have to explicitly prepare.

This entry should appear on .

Permutation Puzzle: “send+more=money”


I saw this puzzle on Bartosz Milewski’s blog, with an entry on using monads in C++.  I’d like to hold it up as an example of a completely different lesson to C++ programmers:  A central idea I want to teach is know your libraries.

I recall it was in the early ’90’s, when the STL for C++ was submitted as a proposal to include in the upcoming standard.  I noticed there were algorithms called next_permutation and prev_permutation, and wondered how they work—how do you order them and re-arrange your collection to the next such, without keeping an auxiliary state?  Then I wondered what I would ever use such a thing for.  Well, nearly 25 years later, I found out!

You should look through the list of algorithms every once in a while just to see what’s there.  Otherwise you might only know about the common ones that you use.  Consider the analogy with a tool (say, a special bent screwdriver only used to attach doorknobs) that you know is in the very back of the drawer, though you may need to rummage around to locate it.  Remembering you have that tool makes for a quick job.  Having to rig up something from common parts instead (to continue the analogy, use locking pliers to grab a short screwdriver bit from the side) is not as good, and certainly more work.

So… 8 nested for loops followed by 7 if statements containing 28 conditions?  Get real!  If you have a line that reads });});});});});});});}); then the code review will be a sight indeed.

Solution in C++ w/standard library

Here’s the meat of my solution:

using cellT = int8_t;

cellT A[10] {0,1,2,3,4,5,6,7,8,9};

void solve1()
    do {
	auto [ig1,ig2, s,e,n,d,m,o,r,y] {A};
	int send= decode({s,e,n,d});
	int more= decode ({m,o,r,e});
	int money= decode ({m,o,n,e,y});
	if(send+more==money) {
    } while (std::next_permutation(std::begin(A), std::end(A)));

You’ll notice that besides the uniform initialization syntax introduced in C++11, this uses something you might not have seen before (if you’re reading this in 2017).  Hot off the press in C++17 is structured bindings.

	auto [ig1,ig2, s,e,n,d,m,o,r,y] {A};

This defines 10 variables and assigns all the elements of the array to them.  The first two are ignored so I used scratch names, and the others are simply the names of the letters in the puzzle.

One thing I have to point out from Milewski’s listing is the call to turn a word into a numeric value.  He writes:

int send = asNumber(vector{s, e, n, d});

This creates a std::vector on every use.  Let me elaborate: it allocates a block of memory from the heap (vectors can’t use a small-vector optimization).  Then after the call returns it is deallocated.  Then the next two lines to the same thing.  And that happens on every iteration.

The constructor for std::vector takes this handy literal list.  Now in C++ these containers are not special language features, but are ordinary libraries.  It should be clear that anything they do — cool syntax or unusual ability — you can do yourself on your own code!  My version of the same construct does not create a vector, doesn’t require more words to make the call, and most importantly does not have any overhead.

int send = decode({s,e,n,d});

And here is the function that takes such an initializer list:

int decode (std::initializer_list<cellT> lst)
	int total= 0;
	for (auto digit : lst)
		total= total*10+digit;
	return total;

The solving function doesn’t print the results because I want to time just the solving logic.  So the solutions are pushed onto a vector, and the caller prints them after stopping the clock.  In a real program, this might be an object (not globals) and the results available in the object afterwards, or as the return value from the solving function.  In another post I’ll make it lazy.

 Make it faster

This simple function found 50 solutions, one of which doesn’t have a leading zero.  It ran in 39.6 milliseconds, trying all 3,628,800 permutations.  That’s 92 million iterations per second.

The value of 10 factorial is an interesting number here.  Donald Knuth, in the The Art of Computer Programming, wrote that this is about the size that separates things that may be done by brute force from things that are impractical to simply try all possibilities.  Volume 3 was published in 1973.  I hazard to guess that computers now are about 230 (or about a billion) times the power of the machines that were around when he wrote that.  A billion times 30 milliseconds is 460 years.  So, I revise that to more like ten million times the speed, if I postulate that he could have run this program to completion in a matter of days.

Anyway, to make it faster, I need to skip over permutations that are “the same” as one I already rejected.  The order of the two ignored digits don’t change the solution, so if I decide that one order is canonical and when the other is detected I skip over the whole lot, that would cut the number of iterations in half.

So how do you skip over states in the next_permutation algorithm?  I looked it up — a StackOverflow post described it well and also pointed to a Wikipedia page on it.  The states are generated in lexicographical order, so when a given digit changes everything to the right is in reverse sorted order, and it “rolls over” to advance that digit by one and everything to the right is now in forward sorted order — the lowest value of that substring.

So, when I identify a digit value that I know will not be a solution no matter what the other digits are, I can skip to when that digit is advanced again by reversing everything to the right of it.

void skipfrom (int pos)
    std::reverse (std::begin(A)+pos, std::end(A));

    do {
	auto [ig1,ig2, s,m,e,d,y,n,o,r] {A};
	if(ig1 > ig2) {

Indeed, it still found 50 solutions but the iteration_count showed half the number: only 1.8 million times through the loop.  However, the time only went down to 26ms — about two thirds the time, not half.

We also don’t want solutions with a leading zero, so filter those out too.  Notice in the listing above I changed the order of declaring the digit variables.  It doesn’t matter to the solution algorithm, but putting these farther to the left means I can skip over more.

	if(s==0) {
	if(m==0) {

That didn’t save much though: 1.45 million iterations in 22 ms.

Another big constraint can be found on the right side of the puzzle.  I would think that parsing the arrangement of digits into ints would be slow, seeing as that involves multiplying by 10 and adding each digit.  Looking at the rightmost (units) digit only, the puzzle has d+e=y with a possible carry.  Test that before parsing the int values, and furthermore skip ahead until one of those three digits changes again.  To that end, the declaration order has d, e, and y next after the previous items we wanted on the left.  This leaves only 3 letters to the right, so each time the units digits don’t work it can skip 6 iterations.

I added a counter to that, and see that it happened 219,360 times.  The loop only executed 355,053 times now, taking a mere 4.7 ms.

Faster yet?!

Notice in the listing that I declared a type CellT for the array of digits and anything that holds a digit.  My thought was that keeping the array small would save in parameter passing to decode.  Keeping the size of the data small is generally good for memory caching, but it probably doesn’t matter here because I don’t have enough data to exceed the L1 cache anyway.

But, I can change the type in one place in the code and it affects everything in the program.  I changed it from int8_t to plain int (int is 32 bits here), and…  the time was down to 3.4 ms!

64-bit was the same.  16-bit values was the slowest at 5.2 ms.  So, the CPU is inefficient at loading 8-bit values and worse with 16.  I don’t know if the actual load is slower, or the compiler generated somewhat different code rather than just using MOVXS instead of MOV.  This was a difference of a quarter of the execution time over the entire algorithm, and loading values is only a part of what it does, with values kept in registers once loaded.