Its been 8 months since I’ve graduated from the firehose project. Man, has it been a ride. Since graduating, I’ve learned half a dozen new technologies, brushed up on fundamental CS concepts, and even landed a job working full time for an amazing startup (more on that later).
Basically, I’ve done my share of coding challenges and I thought I might offer some insights and mindsets into how to systematically solve these problems.
When you’re solving a coding problem, I think its best to take a top down approach. Here’s the 5 steps I take. Don’t worry if it doesn’t make sense now, I’ll be walking through these steps with a detailed example.
1.) Read and understand the nature of the problem. Usually, a coding challenge has a “trick”. The problem description will outline the boundaries of the problem, you’ll need to play around to get a “feel” for it.
2.) Develop a high level strategy. Break the complex problem into smaller, simpler parts. Don’t freak out if parts of the plan are really hazy. You should realize that you’re not supposed to be able to know the solution right after reading the problem. I know this seems obvious but its a really crucial point. Don’t freak out and give up because you don’t know the answer. Just start with what you know.
3.) Start blocking out the simple parts of your code. Keep things general and even in pseudo code. Don’t worry about implementation of the tricky parts. Solving a coding challenge is like solving a puzzle. It’s obvious where the corner pieces go but the pieces in the middle are a lot harder to place. Once you have enough of the edge pieces in place, the rest begins to fall into place as well.
4.) Start implementing the easy portions of your strategy. Just get something working. The code doesnt have to be perfect, and it DEFINITELY doesn’t have to be optimal. Once you get something working, you can go back and refactor it.
5.) Repeat steps 2-4. Lots of times, you’re going to need to change your big strategy. That’s ok, take what you learn and revise it for the better. Being a good developer means trusting in the process and being comfortable with unknowns. Great code is written iteratively. Ernest Hemingway said “The first draft of anything is shit”. Code is no exception.
I’ll be using the Binary Tree Sort problem from the FHP as an example. So from here on out, spoiler’s ahead. 🙂
1.) Understand the problem. Go ahead and review the problem from the FHP. You’re told to build a binary tree and then traverse it. We’ll just worry about building a binary tree for now. The problem description tells you what a binary tree is and provides an example. Almost always, I like to sketch out a few more examples. If you do this, you’ll discover certain behaviors of a binary tree.
The key behavior is that the nodes on the left are always smaller than the nodes on the right.
And this also creates a systematic pattern for part 2, when we need to traverse a binary tree:
Notice that there’s nothing here that’s too tricky. All you have to do, is build out a couple example binary trees by hand, and then traverse it by hand and you get a feel for how the code could potentially work.
Now we move on to step 2, develop a high level strategy.The more you code, the more you start thinking like a computer. You’ll begin to think The Ruby Way™. This step becomes more intuitive with practice.
2.) I know I’m given an array and I need to build a binary tree out of it.
array -> [my code] -> binary tree.
From step 1, I also know procedurally how portions of the code could work. From a high level, I’ll need to start building from the first item in the array. This will be the root node. Take the second item, and if its smaller, put it to the left, if its larger, put it to the right. Then I’ll take the next item, and start from the root node again. If there’s already a node where the new item is supposed to go, I’ll travel to that node and repeat the process above, placing new items in the array as leafs of the outermost nodes.
3.) Break these instructions into composable components. You might only know how to translate small portions of these instructions into code, and thats ok.
Here’s the main components that jumps out at me:
– Ideally, I want to be able to run some code like this to get the answer:
so, I’ll need a Tree Builder class that actually builds the Binary Tree.
-I’m given an array, I’ll need to iterate through it to build the nodes of the binary tree, so I’ll probably need some kind of loop.
-I’ll need to iterate the array through some kind of sorter that handles the logic for building the nodes.The sorter will somehow have to compare the current value to a node. At this point, I realized I should change the block iterator argument’s name for clarity. Here’s the logic I came up with.
Note, I have no clue right now how I’m going to pass in the array or how I’m going to pass in current node. I don’t know how I’m going to insert the values or traverse the node. I don’t know those parts yet, but I’m pretty sure I need some kind of logic like the ones above.
3.) Block out the code.
Putting these three pieces together…here’s what I now have. In the initialization method, I build the root of the binary tree from the first element in the array and then shift it off the array.
Steps 3-5) Iterate and flesh out the code.
Ok, so now we’re cooking. We just need to implement 2 more pieces of logic. Something that handles “insert” and something that handles “traverse”. The “build” method is getting a little bloated, so I decide to separate the insert logic into its own method. Be aware, I still don’t know how I’m going to pass in the “current_node” yet.
This is all well and good for 7, 4, and 9.
But now for the 4th item, TreeBuilder can’t just insert the node in. It’s gotta go down a node.
We’ll need to go from node 7, to node 4, and then insert node 1.
So to me for this iteration, the insert_into_tree method will need to do something like this:
This would work for value 1. But what happens if I need to traverse 4 nodes? I need to keep looping through the traversal and insert logic.
Ok this could work. For the sake of being academic, how else could this be solved? To me, the traversal logic is a little ugly. I feel that a recursive approach could be more succinct and also better represent the logic of the problem (binary trees are recursive). Here’s what I came up with:
Now with some refactoring of the “build” method…
…and we’re at a solution! Note: This code can be refactored some more to be more readable, modular and dry. Bonus: What scenario would cause this code to break? Which version, iteratively or recursively, is more efficient?