Algorithmic Puzzles and "The Real World"

July 04, 2017

Back Story

Growing up, I made a lot of mistakes. I once counted up the numerous tissue scars, nicks in my teeth, pops my dislocated joints make, and other artifacts of my youth. Just by going off this historical record, I calculate I had a close brush with death or major bodily injury about once every 2 years. Now side stepping the all the sport injuries and other summer mishaps, a less tangible but just as important class of mistakes I made were not physical. These were the all missed signals in relationships, the procrastination of my studies, and the all too common unfortunate choices throughout growing up which I'm sure we can share.

Now before you think I'm some fuck up, which I'll admit, I probably would have been, if not for my extremely patient and wise parents.

For I am very fortunate to have parents which gave advice that helped me avoid making many more mistakes than I actually did.

I am even more thankful for how they would know what situations I could make mistakes in. They gave me the appropriate space to fuck up and would let me learn from the natural consequences of my actions. They would always jump in before things went critically wrong, help me out, and provide the sort of after retrospective analysis of what I could have or should have done.

I'm sure you've experienced something similar in your parents too. And if you fuck up as many times as I have, eventually you find that your parents are going to have to optimize their time spent on correcting you. One of my dad's favorites was the age old saying of, "Matthew, when you get out into the real world…", followed by him elaborating on some painful, but true fact that at the time, I was too naive to understand.

The Overview

It is in this saying, "When, you get out into the real world", in conjunction with the peculiarities of the software hiring process, which I am going to elaborate on.

Now, if your thinking, ""WTF, how does that saying even relate?" Or, "Ugh… I predict this will be just another bitchy blog post on how the coding challenges fail in their goal of hiring good engineers?"

Then just hold up resist that ADHD tendency to jump around the interwebs in search of your next dopamine hit, and carefully read on.

The specific moments and rationale of why my dad said that phrase, have consolidated in memory, and now I have more of feeling of what it means. I perceive it more as a … TODO

I want to look at common interview questions, and learn not just simple tricks to pass a whiteboard interview, but actual insight or knowledge which I can leverage in my day to day.

I want to take the cute little problems which I see over analyzed for the shallow goal of passing interviews, and actually look at them and draw meaningful design strategies and patterns that will make me better.

The Challenges

Below are a list of beneficial problems. And by that I mean that they are actually usefully for more than just passing through the grind of a technical interview. They provide patterns and ideas which are useful in "the real world". And ways of thinking abstractly, from first principles, etc which I find to be useful in contexts outside of just software design.

Two sum problem

A simpler, non NP-complete problem to the Subset sum problem, aka perfect for whiteboarding!

The Description

Find all pairs of two integers in an unsorted array that sum up to a given $$S$$

Our input is an array of integers and a target sum. Our output is two indices of the numbers which add up to our target sum.

Note that there is in place the constraint that we may not use the same element twice. Also, we can assume that being a simple whiteboard problem, any array that we are given will only ever have exactly one solution.

An example to clarify:

// with input
array = [3, 8, 2, 11]
target = 5

// our output is
 out = [0,2] 

So i'm going to list two solutions, starting first with a "oh shit I'm too nervous, this will work but its slow". Followed by a "Hashtables are my best friend" solution. For most of the lines I'll have a comment near by which would be similar to my thought process if I was actually writing this out by hand.


Be lazy, and make the common trade off of time efficiency for space inefficiency. What we lost in space $$O(n)$$, we made up for with a complete reduction of a loop and thereby going from a polynomial to linear running time.

Stepping back to an even more generic description, one could say by that by utilizing an adjacent but efficient data structure to store results as we make our way through data is beneficial. This is just a slightly simpler version of dynamic programming, the only difference is we are not mentioning subproblems, but the caching aspect still stands.

Island Counting

A fun little problem to remind you of why its important to know how to move, or traverse, in our little worlds.

The Description

Given a matrix of 0s and 1s, where 0 represents water and 1 represents land, count the number of islands. Two pieces of land are connected if they are vertically or horizontally touching. Two pieces of land that are diagonal from each other are not touching.

Two examples to clarify:

// The matrix..
0 1
0 1
// has only 1 island

// This matrix...
1 0
0 1
// has two islands

Matthew Clemens © 2022