Codeward Bound

One of my favorite cartoons growing up was Bots Master. Not only did it have the best theme song of all time...hands down, clown frown, one two step, Motown...it had the most amazing 3-D effects I've ever seen in my entire life...bread knife, flying high, no kite.

I've always dreamed of one day being able to design my own 3D robots so we could defend the world from bad guys on a weekly basis. I did not realize how incredibly terrifying and exhausting that would be. Thankfully only half of that dream is realized.

We live in a world where 3D is all around us (hehehe, get it?) and the technology used to create the effects of 3D go across industries. We use it to design cars, model buildings, create movies, make friends, print prototypes, etc. 

The barriers of entry in the 3D tech space has been lowered to the point that most any person (or robot...soon) can start creating in no time. It's an amazing time to be alive. The technology moves so fast that I can imagine my kids laughing at this post "Dad what do you mean by see a 3D effect? Why would I use my eyes? It's already in my brain. Freak!"

The future is here. All you need is an idea, some special software and this post to get started in the world of 3333333-DDDDDDD (I really hope that effect came through...so embarrassing).

3D models

3D modeling is the process of designing 3D objects on the computer. 3D modeling is the core component of many industries including video games, 3D printing, animated movies, friends, etc. These 3D models really are just 2D images sent through a process called 3D rendering to make them look (but not taste...yet) realz!

OpenSCAD is an open source program for designing 3D models right on your computer. OpenSCAD is programmer friendly, meaning that you write code to create the objects. Other 3D modeling programs require you to use a mouse to create the objects and we all know how much programmers hate using the mouse. With OpenSCAD you simply type what you want to create (ex: cube) and the program will render it for you. It's literally magic.  

You can make cool objects through the clever combination of a bunch of smaller shapes we all know and love, like cubes, cylinders and spheres. In the world of 3D modeling, these smaller shapes are called primitives. When you sprinkle some primitives here and there, and remove some pieces of it over there and thurr, now you're cooking with gas! OK enough talk, lets make something!

Let's do it!

OpenSCAD is simple and intuitive. Don't believe me? Well that's weird, why would I lie to you? We're friends...right? Right? WHY DONT YOU LOVE ME?!? OK OK, you just want proof, I understand. Let's say we want to make a primitive shape like cube, guess what we would type in? ::awkwardly long silence and stare:: That's right! We would just type in: cube().

Boom! It's that easy. Just type the code in the left panel and press F6 to render it on the right display panel. See there's your proof! Love me yet? OoOoOoOoOoO you want more? OK, things...are...about...to...get...cray.

Now who says a cube has to be a cube (deep yo!)? Well more specifically who says it has to be a square-y looking cube. What if we want, like a rectangle or something really flat and wide like a pizza box? OMG, are you as hungry as I am right now? We can make those hunger inducing shapes just by adjusting the length, width and height (or y, x and z values) of the cube.

While creating the cube you can pass in certain values for the length, width and height in two main ways. One, you can yell at your computer until it fixes it. Two, you can pass the values in the form of vector that represents the x, y and z values of that object, all enclosed in square brackets. Your mileage may vary with these options, I prefer number 2.

Check it 1...2...

In the picture you see I've created a cube that's 3mm (x-axis) by 6mm (y-axis) by 5mm (z-axis). Notice the tiny axis guide in the bottom left of the rendering panel. 

Note: You can also center the object on the center of the plane by passing in center=true. Ex: cube([3,4,5], center=true). All the dimensions will stay the same though. 

Boolean operations

Most complex objects in OpenSCAD are made up of a bunch of those primitives I spoke about, along with the use of something called boolean operations. This is usually called Constructive Solid Geometry or CSG (if ya feeling the groove).

Heres a brief overview of the operations you can perform:

Union - This operation basically smooshes two or more primitives together to make one gnarly looking object. You can create a union by wrapping all objects in the union function. 

Note: Unions are actually done by default in the editor but I wanted to just spell it out here to really stick it to the man! Get it? Cuz union? I'll be here all week...What that?...OK they are saying I have to leave immediately after writing this. 

Difference - This is basically the opposite of a union. Instead of rendering the additive (boy I sure hope I spelled that right) object of the two objects it subtracts the second object from the first leaving a whole hole (nailed it!). You can think of it as the first object minus the second object. It's a very sad relationship.

Importante! This is only boolean operation where order matters.

Intersection - Only show the common parts the objects share. Where they are touching...tehehehe

You can see how combining all this removing and adding can create alil sumthin sumthin but there's even more you can do stretch (huh? huh? You'll get that joke later) your creativity. 

Transformation operations

Transformation operations allow you manipulate the object in space to suit whatever wacky requirements you may have. These are relatively simple operations but the key is that you can do them on specific objects independent the whole darn thing.

Translate - This is how you move an object along the axises...axi? I don't know...the lines. Just like with the cube you pass in the values as a vector to the translate function where each value represents how hard you want to move that object on the x, y or z axes. 

As you see in the pic above, I moved the cube 3 units on the x-axis, 1 unit on the y-axis and 2 units on the z-axis. Looks like it's floating eh?

Scale - it's all about making the object larger or smaller by changing it's x,y and/or z values by some multiple. Lets take our new magical floating cube and make it twice as big by passing 2 as a multiplier to the scale function. 

Whoa! It's so massive now it doesn't fit on the screen anymore. We've created a monster! No one should have this much power.

You can also send in negative values to decrease the scale x,y and z values and even use float numbers to really fine tune your scaling. 

Rotate - This operation allows you literally put your hand through the screen and rotate the object around making sure you're satisfied with it's feel and squishiness. I'm just kidding ya'll. Don't do this. (disclaimer: I am not responsible for overzealous codewardbound fans who broke their computers by creating hand sized holes in the screen.)

This operation actually just allows you rotate along the axis by a certain number of degrees. It takes a vector of the degrees which indicates how much it should rotate on each axis. 

This rotates the cube along the x axis by 60 degrees, the y by 50 and z by -45. 

Making it purdy

The colors, Duke the colors! You can simply change the color of your object using the color function and passing in a vector of floating point RGB values from 0.0 to 1.0 like hurr:

Similar to how we doez in CSS, you can also simply pass a color's name:

color("red") cube([2,3,4])

Note: You'll have to use the preview mode by pressing F5 to see the results of changing color.

Wrap it up...

There's so much coolness you can do with OpenSCAD. I would be doing ya'll a disservice if I revealed everything here. So go...go explore! Get messy, make mistakes and let me know how it goes. I can't wait to see all the incredible things ya'll design. Make something awesome that will make Pixar looks like childs play! I mean, I guess Toy Story was literally a movie about childs play toys so it isn't really an insult but you know what I mean.

DEUCES! SWAK!

Resources:

The Docs: http://www.openscad.org/documentation.html

Beginner's tutorial: https://www.youtube.com/watch?v=eq5ObNeiAUw

Throughout my adventures in coding interview land, a few general concepts seem to come up over and over again. One of the most overwhelming examples of this has been Sorting. Every interview I've had dealt with sorting in one way or another. Whether it's grabbing the tweets from a cat (true story), turning a Binary Search Tree into a Linked list, or changing up an array of strings so that anagrams are next to each other, they all required some knowledge of sorting.

Now there are many, (too?) many sorting algorithms out there but the ones that keep popping up in interviews have been merge sort and quick sort.

Sorting is basically how the computer organizes the data in a collection. From that simple concept, smart computery and mathy folks from all over the world have come up with a variety of colorful ways to accomplish this. Some ways are faster, some ways take up less space, some ways are  weird (odd/even sort), some are delicious (Spaghetti sort) MAMA MIA! but each one may be more efficient or appropriate than the other, depending on the task.

Why do we sort? Because us humans (no offense to the manatees) like to see things in some orderly fashion. Imagine if while standing in line at Trader Joes, the workers decided who goes to the next cashier by pulling people at random. You would be pretty upset, but given that the folks at TJs are so nice and cheery, you might actually forgive them and eventually blame yourself for your mistake. OK bad example, but you get the point. 

Sorting makes it easier for us as computer programmers, to perform other functions and algorithms on the data in an efficient manner. Like getting my top favorited tweet ("No data found"), my top liked Facebook post ("Nope, no friends"), or simply to sort my cash in descending order ([$1,$0])...you put the big bills on the outside so they know youz a BOSS!

So with that general knowledge of sorting lets jump into a few algorithms.

Quick Sort

The basic idea behind the quick sorting algorithm is to pick a value, called the "pivot", in the list then partition the list on either side of said value. You partition the list so that values less than the pivot appear before it and values greater than the pivot appear after it.

Then the rest is magic....

I'm just foolin' ya! There's no such thing as magic...unless you consider recursion magic, which it is. 

The last step is to keep following the "pick pivot then partition" sequence recursively on the smaller lists created by the initial partition, then again and again until ABRACADABRA! The list is sorted. (Note: Saying ABRACADABRA out loud has been proven to help the quicksort work. It hasn't been disproved though since I'm way too scared to find out.) 

In the illustration above, you see that first 15 is chosen to be the pivot, then the list is partitioned on the second line. Then each sub-list finds it's own pivot and partitions on that - 10 for the lesser list, 22 for the greater list and so one and so on, to infinity and beyond!

Then allz we have to do is smoosh all the results together in a new array, which is done through magic recursion (I know, I know, it's redundant to say it like that. Like saying "magic magic").

Lets see some code:

CODEZ!

The reason this works is because each item becomes the pivot at some point and by that logic each element will have the values less than in front and the values greater than behind it. Pretty clever stuff folks!

This version utilizes additional arrays. I challenge you to implement a version that doesn't need an additional data structure. 

Time Analysis

To figure out the time for this partition we just have to see how many comparisons the method has to make in order to sort the list. On the first step, to partition a list of size "n" we would need to make "n-1" comparisons because we have to compare the pivot to every value in the list. This gives us a time of O(n) AKA linear time.

Then comes the fun. When we recursively call the method on the lesser list and the greater list, we are only doing that call on half the list or n/2. This halving sequence should remind you of something. I'll give you a hint it rhymes with Binary and ends with Search Knees - And if we recall the time complexity of that thing was O(log n) AKA logarithmic time. 

Combining the times for the comparisons and the fact that it's doing it over half the list each time yields a average time of O(n log n)! Sweet baby Ray that's fast!

Now before you start running the streets throwing up Quicksort gang signs and tagging walls with O(n log n), there is one caveat. The worst case time for this sort can be O(n2). That is because it's possible that we happen to keep picking a pivot that the smallest of each list over and over again. Essentially leaving us with a sub lists of length 0 and length n-1 for each n we call the method with. 

One way around this problem is to beef up your pivot-picking logic to chose a value that is close to the average of the list. Ta-da!

Merge sort

As the name implies it's all about merging. Merge sort needs additional space. Merging is the act of combining two lists together and having the outcome be one sorted list. The merge algorithm works like with two lists:

1) Take the first items of the two lists to be merged and compare them.

2) The item that is smallest becomes the front of the new list.

3) Then we again compare the first items of the two lists. The list where the item was removed will be smaller since we plucked that item and put it into the new list.

4) The smaller item from that comparison is then added on as the second item in the new list.  

and...so on...and so on....

In the end you'll have one big ol' sorted list. 

Now in order to do this in your everyday life you would have to simply split your list into halves until you have a bunch of lists with one item in it. With a list of size n, upon splitting you would have n lists. 

Then using the merge algorithm we just learned you can then start merge each of the sub lists, placing the small item in front over and over again. Check the pic:

In the illustration above we can see that bottom row is just a list of one item each - That's where we would RELEASE THE MERGERS! That first merge step you see is fairly straight forward - 2 is less than 5 so it goes in front of 5, 4 is less than 6, 1 less than 3, etc. The second merge is where things get interesting!

Take the merging on the right of list [1 , 3] and [2 , 6]. The first comparison is between 1 and 2, 1 is less so it rides shotgun in the new list. Then we compare the lists [3] and [2, 6], since we removed the 1 from the first list so we compare 3 and 2, 2 wins and gets second place in the new list. Then we just have to compare lists [3] and [6] which is the same as comparing 3 and 6. That's how we get the new sorted list of [1,2,3,6].

Now don't be fooled that this merge sort is just as simple as alternating the values from the two lists into the new list. The lists could have easily have been [1,2] and [3,6] then the comparisons would have been 1 and 3 resulting in lists => [2] and [3,6] , 2 and 3 resulting in one list => [3,6] then no comparison would have been needed since there's only one list. We know that one list is already sorted cuz of the other merging we did prior, AH, ya see ya see! Very slick!

Here's some codez!

Time complexity

I won't spend too much time (LOLOLOLOLOLOLOLOLOLOLOLOLOLOLOLOLOLOLOLOLOLOLOLOLOLOLOLOLOLOLOLOLOL....whew...LOLOLOLOLOLOLOLOLOLOLOLOLOLOLOLOLOL! That was all me!) on this since this post is getting a wee bit long in the tooth and also because it's actually the same timing as quick sorting!

O(n log n)!!

Coincidence? Not really, cuz when you think about the steps in the merge sort you basically keep splitting the list in half then recursive-magically apply the merge algorithm to each half. As we learned before that halving always results in O(log n)  and each merge actually takes (in theory...I guess everything is theoretical...I mean what is life...) O(n) for a total time complexity of O(n log n). Or it could be that quick and merge sort are the same person. I mean have you actually ever seen them in a room at the same time? I rest my case!

 Custom Comparators

valSo now we see that there's a few different techniques for how the actual sorting gets done but the fundamental mechanics is based on a simply function hidden in the programming language called the comparator (I think...I didn't actually look this one up sorry guys. Let's just go with it.). The comparator function's only job is to take in two relevent items, compare them and return the corrected order of them OR just simply return a number which defines the order. That's really the magic!

These sorting algorithms work with number values pretty well by default, but you should know that you can sort on almost any attribute you want! You just need to override/extend/monkey patch the comparison function in the language you're using. 

In Ruby you can write your own comparison method by defining a new <=> method - They call it the "spaceship" operator, I call it the "starship pew pew" operator - It's catching on in some circles and by "some circles" I mean myself and my offensive amount of stuffed animals.

CODEZ!

The starship pew pew operator (you see how quickly it's catching on?) returns a -1 if the first value is less than the second, 1 if it's greater than and 0 if they are equal. Ruby uses this method behind the scenes for a few of it's sorting methods like .sort.

There it is buddies! Sorting in a nutshell believe me there's ALOT more where that came from. So go forth and learn, learn, learn then teach me since I have this problem where I immediately forget everything I write.

What was I doing again? Oh yea, hey folks! Today we're going to learn about sorting...

Resources:

Sorting algos Wiki

Merge Sort 

Quick Sort

Sorting algorithms animations

Interviewer: "What's the time and space complexity of that solution?" 

Interviewee: "How many stormtroopers does it take to replace a lightbulb?"

Interviewer: "What?"

Interviewee: "Two - one to screw the bulb in, the other to shoot him and take the credit. LOL!"

Interviewer: "What?"

Interviewee: "Well, you said space and you look like a StarWars kinda guy so I figured..."

Interviewer: "Yes? You figured what?"

Interviewee: "Oh...I don't actually have ummm...anything to say after that. I was just hoping to trail off and not be noticed"

Interviewer: "I see. But seriously what's the answer-"

Interviewee: "Who wants cake?!"

Don't let the above situation happen to you. Time and space complexity or Big-O Analysis is actually a really important, valuable skill to have as a developer. The reason interviewers tend to obsess over this is because at scale, any improvements in processing time and/or storage space can greatly affect an application's experience. This can tie directly to the bottom-line (in other words "CHA-CHING!!!")

This is going to come up a lot. So while you're sitting down and throwing your hands in back of your head in admiration of whiteboarding so impressive you're waiting for Ada Lovelace to rise up and come straight to your interview, just to give you a high five, remember you might need to make it better. 

Some interviewers are going to ask you to optimize your solutions using Big-O analysis. It's even better if you can do this on your own without the probing.

So I'll just do a tiny intro here that you can take and hopefully use a foundation to derive more complex analysis from. 

Space...the final frontier

Finding the space complexity is actually not that hard, the name just sounds intimidating. It's literally the amount of additional space you would need for your solution. So if you need to put all the elements from one array of size "n" into another array thats O(n) space. If you define a function with local variables, each of those variables take up constant space or O(1).

Sometimes recursive solutions require more space than iterative ones so just keep that in mind. Make sure to point out these tradeoffs to your interviewer, they like that kinda stuff.

Time...

To find the time complexity of a solution you would, quote unquote, simply count the number of statements/calculations/steps needed to get to your solution, in terms of the size of your data set, usually size of "n".

So if you have a loop, that goes over a the entire length of an array and performs an action to each element, like adding 1, that time would be linear or O(n). If you have some algorithm that takes advantage of halving or doubling the data set it's probably going to be around logarithm time or O(log n). We talked about this in more detail in the Binary Search Tree post.

Now things can get more complicated when you start talking about best, average and worst case scenarios. Very much as the naming implies, they refer to the best, average and worst case times of the solution. The way you would calculate these times are very much based on your implementation of the solution.

The idea of the worst case time is usually derived using amortized analysis, meaning taking into account the rare scenarios that would take the absolute most time - the edge cases. The best case is really theorectical, like if all the sun gods were shining on your algorithm that day and everything went perfectly. The average case is really what you're after, since it's the most realistic case that tries to take into account all the randomness and quirks of real life. 

This is just the tip of the iceberg but these are the building blocks. Understand this stuff and you're golden!

Don't worry if this is all greek to you now. Just absorb and keep it in the back of your head. I didn't know much about this stuff either until the situation at the top happened...in my head! The story above happened in my head. I made it up! It's not from experience. Gosh, my story is much more embarrassing than that.

Hope this helps, whether you're actively interviewing for developer roles, looking to improve your own code or just trying to impress your easily excitable boss that you made it go fast. Check out the resources below. Don't procrastinate unless you want to be a Darth...Waiter! ::rim shot:: I'll be here all week!

Resources:

Beginner's guide to Big-O

Big-O in plain english

Time complexity Wiki

Space complexity

BOO! Oh man, You're face. LOL. You should have seen it. I scared the bajeezus out of ya! I know I know it's been awhile since I've posted. I've been busy. Mostly with interviews and such since real life has kicked in after school has ended. It's been fun though albeit a bit stressful. For Developers, every interview is basically an exam that could be on any computer science topics. Given the breadth of the field, and interview can range from "oh man I never heard of that, it's so much fun to work through this" to "oh man, I never heard of that...::awkward silence::..::blank stare::...sooo....do you like stuff?" 

But fear not friends, in my continuing effort to be as transparent as possible, I will be giving you the low down on some of the "exams" I've had the "pleasure" of going through.

Let's talk about something we all learned about in kindergarden, Trees. Here's a pic that might jog your memory:

If you're like me, and god help you if you are, you're probably thinking that is the weirdness looking tree ever! But me no judge. This is what computer scientists think of when you say tree. Not the ones that grow in the scary outdoors but the data structure that grows in the safety of our friends computers. So just be mindful of that when you invite your developer friends over.

Now we had a bit of introduction to the tree data structure with my post on tries so now we can talk about another type of tree structure, Binary Search Tree.

"OoOoOoOoO Binary! I know that. From the Matrix right?" Is something that I may or may not have said the first time I heard of this. I also may or may not have starting laughing when everyone else was laughing, oblivious to the fact that the joke was me...I mean them...the hypothetical person I'm telling the story about. Yea that guy, I mean come on right? ::nervous laugh::

The Binary part of the name comes from the fact that each node can have up to 2 (like binary) children. The difference between a plain ol' Binary Tree and a Binary Search is all about the structure. 

Binary Search Trees (BST if ya nasty) are traditional tree data structures that have rules to govern it's ordering of elements. Basically the rules are that for each parent node, the values on the left side are less than the value of the parent and the values on the right side are greater than the value of parent.

Right == Greater

Left == Lesser

Try not to take this as commentary on left-handers vs right-handers. Some of my best friends are left handed. Sure they give awkward hi-fives but so do I! Anywayz those are the rules of binary search tree so let's see some operation examples.

Insertion 

Here's an example of inserting the number 4 into an existing tree.

Notice the computer does a comparison step at each node it encounters so it knows whether or not to go to the right of the left node next.

Deletion

Here's an example deleting a node with two children. The greatest (rightmost), left (lesser) child pops up to take the parent's place. This makes sense since we know this node's value is going to be less than the right children cuz thats the rules of the BST ::Law and Order sound:: 

Traversal

Traversal is just a fancy way of going through the tree and touching (ewwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww!) each of the nodes. And they go alil sumthing like this:

Pre-order

The root of a binary tree is visited first, then its left children, and finally its right children.

In-order

Left children of a binary tree are visited first, then its root, and finally its right children.

Post-order

Left children of a binary tree are visited first, then its right children, and finally its root.

In-order traversal is most suitable for Binary Search Trees. 

These tree things are pretty cool if I do say so myself, if I do say so myself. So let's talk about the elephant in the room. Why would you ever want to use a BST in the wild? I mean we already have those easy to understand arrays and those super sexy linked lists, what else could a gal want!?! One word, "time and relationship". OK two words, I wrote one before I finished my thought.

Time Complexity

Let's face it, we're all obsessed with time. It governs our whole lives. My favorite super power is the ability to control time. Do you know how many french fries I could get? Nom Nom.

The computer science folks' obsession with time is all about speed. In general, the faster we can do something the better (though sometimes it's better to have things go slow to prevent malicious behaviors like with encryption algorithms and such). So what I'm telling you is that the typical operations you can perform on arrays and linked lists are faster on binary search trees - All because of the hierarchical relationship structure of the thang.

Example time! If you have to find a specific element in an array, the computer has to go through each value in the array until it gets to the value you're looking for. So let's say for an array of size "n" the worst case scenario for a look up time would be the (time it takes to check each element) multiplied by n. Computer Science peeps have a fancy way of representing this, Big-O notation (mentioned in my post about hash tables) which would look simply like this O(n).

So it's cool to know the time it would take to find something in an array but why should we care? Well imagine if we had an array with like a million-billion-gazillion things in it, then to find something that happens to be at the very end would take light years (::puts on glasses and red tee shirt:: Well actually light years is a unit of distance and not of time sooooo...you're wrong. Please correct this post and stop talking to yourself). LIGHT YEARS YA'LL!! That's a long time!

This is where binary search trees really shine! Because of those rules (left = lesser, right = greater) during a search the computer can quickly eliminate a whole half of the tree!

You see, if you're looking for the number 9, the computer will look at the value of the current node it's on. If the current node is less than 9 it'll go to the left and won't even waste time looking on the right side of the tree. For a tree with a gazillion-billion nodes, that elimination technique cuts the time down super fast. So speaking of that time, what is it anyway? 

Warning: Math ahead! Warning: Math ahead!

Well this is when things get all mathy. If math isn't your thing, don't fret, It's not mine either. We'll take it slow and I'll drop a few linky links to help jog your memory.

The code for searching a BST for a specific value (key) might look something like this:

Let's say that T(n) = the number of operations needed to find the key value, where n is the number of nodes we need to check in the tree. Since n is always going to be factor of 2 we can say n = 2x. So according to the code above the formula would look like this:

T(n) = the first if statement on line 2 + the second if statement on line 4+ the recursive call to the same function but only with checking half the nodes of the original n:

T(n) = 1 + 1 + T(n/2)

Now if we go through this function a few times the sequence would look like this:

First call: T(n) = 2 + T(n/2)

Second call: T(n/2) = (2 + 2) + T(n/4) => (2 * 2) + T(n/4)

This is because we go through the if statements again (+2) and we call the function again reducing the original set of nodes to check by half (/2). For every (less than, greater than) check the computer makes it's gets to eliminate half of the nodes left.

Third call: T(n/4) = (2 + 2 + 2) + T(n/8) => (2 * 3) + T(n/8)

See a pattern here? ::Dora the Explorer stare:: Of course you do, cuz you're super smart! The pattern can be reduced down to this equation:

T(n) = 2 * x + T(n/2x)

Since we know that n = 2x we can say:

T(2x) = 2 * x + T(1) 

Now we solve for x from n = 2x. So if you remember from high school math ( I actually learned this in university and the magic school bus) in order to solve for the value of an exponent you can use logs. 

Our equation n = 2x  looks suspiciously like the left side of that equation above. THIEFS! Well in any case, let's transform it with some log goodness.

Log base 2 or log2(x) means the power you have to raise 2 by in order to get x. For example, 22 = 4, so log2(4) is 2. So let's start by taking the log base 2 of both sides:

n = 2x <=> log2 n = log2 2x 

Now because logs are magic, we can drop down that x like so:

log2 n = x * log2 2

Annnnnnd because log base 2 of 2 equals one, well then:

log2 n = x

Plugging into our original formula yields:

T(n/2) = 2 * log2 n + T(1) 

Since T(1) yields a constant we simplify to:

T(n/2) = constant_1 * log2 n + constant_2

This is the running time of the search. In the world of Big-O, constants become irrelevant for large data sets so we ignore them to get the running time to be ::drum roll::

O(log2 n)

This is known as logarithmic time meaning the running time increases logarithmically (huh? huh? see what I did? ) in proportion to the input size (n).

Great Scott! We did it. We found the time complexity of searching a BST using math! YAY!! Cheeseburgers all around!

So why is this important? Well it turns out that the longest time it takes or worst case scenario would be if it has to search for a node at the very bottom of the tree. A time of  O(log2 n) Is much faster than a time of O(n) for an array. Such Awesomeness!

Well it's not entirely true that every array has a search time of O(n). If you have an array that's sorted you can use Binary Search to get to a specific key. Binary Search grabs the middle element and checks whether the key is that middle value, on the left (less than the middle) or on the right (greater than the middle). This is exactly the same freakin thing we just did, hence the name. So likewise the running time of a Binary Search Algorithm is O(log n).  

That's if for now folks. Go forth and impress your friends, rando people on the train, Obama and pets with your knowledge of trees and time complexity. 

Now, I actually don't have any money to pay for those cheeseburgers. So, completely unrelated, please excuse me while I take my coat and bag into the bathroom. Cheers!

Resources

BST Wiki

Khan Academy Logarithm Basics

Yea you are.

Behavior Driven Development that is. Sometimes (read: all the time) I like a little cucumber in some (read: all) aspects of my life. In my water, on my eyes, in my sandwich, in my code, etc. I could hardly contain myself when I discovered the Cucumber testing framework since it combines my two favorite things - testing and vegetables. Amazing!

Cucumber is a testing tool that allows you write out the features of an application in plain ol' english. Cucumber is great since it really looks like actual documentation. It gives you the chance to break out the different features of your application according to the Behavior (ya see what I did there?) of the user. Here's an example of a cucumber test:

As you can see, this is really a narrative that describes, 1) What this feature is for, 2) The benefit it yields, and 3) The actual feature itself. All in declarative, user speak, not wacky programmer talk. No mention of controllers, routes, parameters. etc. but these tests will touch all those things (Eeeeeewwwwwwwwww!).

So I know what you must be thinking, "This is all well and good but how does the computer know how to do these things?" Well my friend all will be revealed in time and by in time I mean now. These feature steps only serve as output in the console the real work happens in the step definition file.

Each of these "steps" you see from the Cucumber (.feature) file maps to a step definition ruby file where the actual code lives. As cucumber goes through the steps in the .feature file, it'll come to the step definition file to execute the code in the same order.

The Then statement usually maps to an expect statement in the step definition. The Given and When statements are like setup statements. Given gets you to where you need to be so you can perform the When step.

There's a concept called Outside-In Development which is like TDD but at a higher Behavior Driven, Feature test level - This is where Cucumber really shines. 'Member how with TDD we would start by writing the tests first, then have them fail, then write the code to fix it? Well, with Outside-In Development (OID..I really don't know how to say that or if it's even a thing) we do the same thing. We first start out by writing the Cucumber tests, fail the tests, then write the minimum amount of code to turn the tests green. Rinse. Lather. Repeat.

This is where we finally get to talk about that picture up top. You start in the outside circle at the top writing and failing acceptance or feature tests with a tool like Cucumber. As you go through the process of turning the tests green, you write the unit test for each component - fail, pass, refactor them. Then you pop out to the outside circle again and keep it going. Round n' Round, like a record baby! 

So right now we have all these cool automated tasks running in a background browser thanks to Capybara but if you actually want to test javascript then you'll need to add that selenium-webdriver gem to the gem file and simply add "@javascript" over the scenario in the cucumber file.

This will actually automatically open your browser and run through the tests with the speed of a cheetah, drinking coffee in the Indy 500. There are some issues with this approach though. One of them being the fact the test suite is now interacting with the database from two different places - the headless browser via default Capybara and non-headless (I guess that's what it's called) to test the javascript. This is a problem with database concurrency. 

Concurrency issues

Rails by default uses transactional fixtures...which means it only allows one database execution at a time. Sometimes this may cause problems when you are interacting with the database from the actual browser and the headless browser at the same time. To get around this, you can use a gem called database_cleaner which would give you more flexibility on how to handle these database transactions. Here are the configuration steps you need to make for rails (http://devblog.avdi.org/2012/08/31/configuring-database_cleaner-with-rails-rspec-capybara-and-selenium/)

Debugging

Capybara supplies a sweet helper method called 'save_and_open_page' that you can put anywhere in your tests. It will save a copy of the page it sees at that point in the test. You can then open that page and see what test is seeing to understand why something might not be executing properly. 

You can also put the statement 'binding.pry' anywhere in the code and the program will stop the execution and allow you check things out just like the debugger. You're in the computer bro!

As you can see cucumber is a great tool for writing tests and requirements for your application in a way all stakeholders can understand. It also helps you to define the scope for your application. Which should keep everyone in check! No extra glittery scrolling marquees.

Cucumber doesn't really replace the tools for unit and controller tests but it's a great way to hit a bunch of components of your app in one shot - End-to-end testing. Also, using a code coverage tool like SimpleCov combined with Cucumber will tell you the percentage of code you're testing within your application. 

OK there it is folks! I challenge you to use BDD during your next project. That means not writing a lick of core application code until you write and run the feature tests. It's a whole different way of thinking about building your app, from the user's perspective. Now I leave with a recipe that will give you a whole different way to think about Cucumbers, from a nom nom's perspective. You're welcome. 

Resources:

Cucumber Docs

Cucumber Regex Cheat Sheet

Testing...testing...1,2,3 everybody clap your hands and repeat after me. Anyone who knows me knows I'm a HUGE advocate for testing code. Test early and test often I always say. Writing tests not only ensures that the code works but it doubles as documentation. If you ever come across some code you want to use but has poor documentation, check out the test suite - It'll give you a good idea of what's going on.

There's a world of tools out there you can use to help test your applications to get them up to snuff. In Rubyland there's Capybara.

Capybara, (no, not the terrifyingly cute giant rodent) is a Ruby tool for testing user interactions with the browser. It basically simulates the behavior a user would perform on your web app (creeeeeeepy), so you can write assert statements to test the expected results. By default it works with headless (creeeeeepy....it means no graphical rendering engine) browsers but you can make it work with JavaScript if you install a gem called 'selenium-webdriver'. Capybara uses Selenium to do automatic browser tasks and Webkit, the rendering engine for Chrome and Safari. Capybara can also be used with Rspec! Which we're already familiar with. 

In the world of web application testing there are a few different types of tests:

Unit Testing  - This is basically an I/O test. Usually a method or class test in Object Oriented Programming. Rails models are not exactly a unit test since they can cross the boundary into the database.

Integration Testing - Test that multiple pieces of the application work together.

Acceptance Testing - Test for stakeholders expectations.

Feature Testing - Test the...uhhh...features. Don't worry we'll get more into it later.

Features tests are all about testing the user facing features of the application. It's kind of an all encompassing test since it can span boundaries between classes, between database and application, the MVC, etc. It's also good for testing lots of end to end code. Whether a feature works or not is a nice unit of measurement for the stakeholders, so it can kinda do double duty (hehehe) as acceptance testing. 

The methods of Capybara are pretty semantic right down to the blocks. If you're familiar with Rspec, you'll see that Capy (nickname) replaces the word 'describe' with feature along with text to describe what we're testing. Then there are the 'it' blocks in rspec which are called scenario in Capy and they basically describe the expected behavior. The context keyword stays the same and basically describes the current state we're in Ex: "As registered user".

here's some code:

These methods do exactly what you think they'll do with the browser. The visit method will visit the path given, it can be a hardcoded url but you know how Rails loves it when you use it's helpers, so use them when you can. 

The fill_in method will look on the page and find the input field with either the name, id, or value of the string you supplied - the :with will fill in that text input field with the value supplied. Then it clicks the button (creeeeepy). It's pretty intuitive dontchathink? 

The last line of the block is where we put our expectation. The result of what we imagine to happen once a user does steps on lines 4-7 is that the page will have the content of "Welcome Friend, you are now one of us, one of us, one of us...." (awwwww what a friendly site. 

WamBamBoom! That's some basics on feature testing with Capybara which will lead us into our next step into the awesomeness abyss of code testing...BDDizzle. I hope you repeated all this. 

Resources:

Annyong folks,

If you haven't noticed, lately my posts have been getting pretty heavy on the data structure side of things. This is because data structures and algorithms are really the heart of computer programming. These concepts aren't specific to a particular language so it's a fun challenge to try to implement them in various languages are you grow your skills. As I learn you learn, we learn together! Today we're going to learn about Hash Tables.

In layperson's terms, Hash Tables are used to store stuff (technical word), specifically store data. Hash Tables are a data structure that stores information in a key/value format. Hashy (my Hash Table's pet name) leverages a special magic function called a hash function to perform super fast operations (insert, delete, find, etc.). Hash Tables accomplish this by basically implementing something called an Associative Array - a general computer science data structure concept that maps keys to values. 

The hash function takes in a key (om nom nom) and spits out (pa-tewie) an index for the key/value pair to be stored at in the associative array. Inserting values in this manner is done in what's called constant time or O(1) - folks in the know call this Big-O notation, probably because Big-P was taken by too many rappers. 

Indexing

The hash function usually constructs an index like so:

Insertion

Once an index is determined then the key/value pair can be popped into that spot in the array in a similar manner as below:

array[index] << [key,value]

Finding

To find something in the Hash Table all youz do is pop that key into the hash function, an index will come out, you look at that index in the associative array and return the result. Set it and Forget it! This is the secret to why hash lookups are so fast - Once you know the index you can go directly to that spot in the array. 

Actually most operations on the Hash Table have an amortized (some can take a long time but they are rare and weirdos) constant time. You saw how quick and easy the find and insertion was. Once you have that index you have the power! YAY! This is fun. Let's do it again!

hash(Keith) ~> index: 1

hash(Keef) ~> index: 1 (Oh no, my alter ego was given the same index?!?!! ::takes off hat:: Dear GOD...)

Collisions

So it turns out the Hash Table isn't the perfect tool, but don't tell him that it hurts his self-esteem. Sometimes the hash function will spit out the same index value for a different key this is called a collision!!!!! (I like to yell it out loud even when I type). Don't worry there's a solution. Actually there's a few solutions, one is called chaining where you essentially would branch off a linked list from that index in the associative array.

Chaining isn't limited to linked links, oh no siree bob! You can use dynamic arrays that adjust the size based on the amount of elements or even trees that can bring operations times down to O(log n) since that's just how trees roll (imagine if they did for realz though!).

Another way of dealing with collisions is through the use of open addressing. Where when inserting, if there's something in the index spot the hash function gave, the computer will just move to the next open index and drop that key/value pair in.

There's a whole science behind finding an open spot in the array called probing. As the name suggests, you basically have to probe the index values starting with the one the hash function gave until you find a free spot where the data can live. 

There's many different types of probing techniques like linear probing, quadratic probing and double hashing, all which would sound terrifying at doctor's appointment. They basically differ on the interval they use between probes. 

Even with collisions though, it's still super duper fast. The hash function will tell you exactly what index to start off at in the associative array. So like let's say you have like a huge number of values in the array, like gosh...idk...like 20 (I have a fear of extremely large numbers) then instead of going through all 20 (::shudders::) values we only have to go the index that the hash function threw out. Nice yo!

There's even folks out there trying to make these things even faster (goes to 11). Check out Concurrency Kit.

For a more detailed explanation on Hash Tables, please check out my buddy Sarah's excellent blog post here.

Later peeps, Annyong-hi-gay-say-yo!

Resources:

Wiki Hashy

Big-O Notation

Big-O Cheat Sheet

I love lists. No you don't understand I LOVE lists! Some people call me the list king and by some people I mean me and only me. I make lists for everything. A list for chores, a list for foods to try, a list for cats to hug, a list for vacations to go on, a list for lists to make, etc.So you can imagine my excitement when I recently learned about a different type of list in computer programming called Linked Lists.

Linked Lists are a data structure in which nodes are connected to each other through, you guessed it, links. These links are essentially just pointers to other nodes. 

BA-BAM!

Looks kinda crazy right? I mean, is it floating? What's up with those arrows? It's all good. We're going to just grasp that nettle and dive right in to figure it out! Let's start out with writing a node class AKA the template for the node objects.

That next attribute is that link to the next node I was talking all crazy about early. Let's continue with the actual list class mkay?

Yep that's it. You can go home now. G'night folks! J/K, J/K there's lots more to be done. Notice the only thing the list knows about is the starting node. Every time we need to perform an operation on the linked list, we have to traverse the list. Traverse is just a fancy way of saying walk, but no one really says "I sped traversed to my Zumba class" but I'm trying to bring it back!

Adding nodes

So in order to add a node to the linked list we must go through the entire list until we reach the end, then pop that bad boy right at the back. 

See that traversal of the list? You see? You see? It's awesome....Everything is awesome!

Deleting nodes

Release the hounds! In order to delete nodes you MUST use hounds...::whispers from off stage:: Oh...I see. Well, apparently you do not actually "need" hounds to delete nodes. I have lots of apologies to make. No matter, we can still figure this out without hounds, though it will be a lot slower imho.

Deleting nodes are a bit tricky ya see. Basically what you're doing is making the parent node (the node right before) reroute it's link to point to the node after the to be deleted node. Like hurr:

So how do we do that? Hounds!!...::whispers from off stage:: Ok nope. Instead we can do this only using computers...I know weird right? Here tis:

Finding nodes

"Help, help! I lost me node and I cannot find she. Please help!" . No worries the hounds will find...::whispers from off stage:: Let's just write method for finding nodes whatdayasay? 

end

Hi-fives all around peeps. We did it! and guess what? I have all these extra hounds soooo...everyone gets a free hound! You get a hound! You get a hound! Hounds all around!

Big thanks and Pusheen sized hug to fellow fellow Nikki who not only introduced me to Linked Lists but also did an amazing job of mock interviewing me while I coded it out. Nikki also helped alot during the Trie exercise as well. She's too awesome! =) 

Are there improvements to be made to this code? You betcha? Riddle me this. What if we wanted to delete the parent node? What happens if we have a circular linked list? How can we detect that? Why are Trolli Sour Brite Crawlers so duhlicious?!? Uh so many questions, so little room in this post.

There's also consistency issues with the different methods I wrote. I did that on purpose to show alternative ways to write but IRL it appears that more that one person worked on this code. Tsk, tsk me.

I leave it to you to marinate on these questions/challenges and come up with other hound-less solutions. Happy coding and dancing!

Resources: 

Wiki Linked List

PSH WHATEVER YODA! There IS a try and it's called Trie (pronounced 'No one really knows so lets just say try'). A Trie is a tree-like data structure and my latest crush. You know how Google does that autocomplete thing? How does it know? Black magic? Well yes and alil bit of algorithms....whoa whoa, don't run off. I know algorithms sounds like a big scary topic but it's really just math...whoa whoa, stop running. I know math can be kinda daunting at first blush but just like anything else, take it one step at a time...whoa whoa, yea I understand you run one step at a time but how about you just give this thing a chance eh? Yay! 

Algorithms are kinda like math for computers. They are a set of steps in the program the computer executes to get to an end goal. Spoiler: Yes, you've been doing algorithms this whole time! Just like how there's many different ways to eat french fries (squirt ketchup all over the fries or the wrong way), there are many different ways to get to the same end goal.

That's when we start taking into account the tradeoffs of the different types of algorithms. Some algorithms take longer, some are more memory efficient, some have require less code, etc. Which algorithm you use is based on the specifics of your situation.

Now why all this talk about algorithms when I tied you down to stop the running gently suggested you should stay and learn about the Trie data structure? Well cuz we're going to build one in Ruby and you're going to see the methods we need for the Trie to be all Trie-like are essentially algorithms.

Tries are a data structure where each node contains a letter and a possible link to other children nodes. If followed from the top node these children nodes will form a word! Each node can also contain a flag to indicate if it's an end of a word. Check it:

So you can see in this sexy Trie we can form the words A, IN, IS, TAVERN, THE (see that flag?), THERE and TOWN. Now let's figure out a way to implement this structure in Ruby. 

Let's start off with a node class. So a node object would probably have 1) a letter, 2) a link to the other children nodes and 3) an end of word flag. Maybe something like this:

K cool looks good for now. Let's talk about the Trie itself. Looking at the pic it makes sense that the Trie would have an idea of all the beginning nodes of the words. Those beginning nodes would then in turn know about the following words in it's children. So initializing the Trie would look like this:

Nice! We got the skeleton going, now let's put some meat on those bones whatdayasay? Let's make some algorithms! First one will be for inserting a word into the Trie:

Inserting Words

So it looks like we have a new method that creates nodes on line 10. The reason we decided to move this logic to a separate method aside from the single responsibility principle, is the fact that once we reach an unknown letter in the children or roots hash, we know that all the nodes that come after that will b brand spankin' new. So since we have repeatable logic - create a new node - we know one of the ways to handle it is with a method. A method that goes alil something like dis:

Let's keep going and write a method to retrieve a word.

Retrieving Words

Fun Fact: Legend goes, the word "Trie" is from the word retrieval. Which actually should sound like "Tree" but then it might be confused with a real Tree. I mean imagine me going to my mom and telling her don't worry I'll get an "Apple" from the "Tree". HA! Makes no sense...anywayz...Lookie code!

  We did it! See all that wasn't so bad now was it? Of course there ways to improve this code. For example, we could take into account the amount of times a letter is in a word in the Trie, perhaps with a weight attribute on the node. We also could improve the retrieve_word method to return all words starting with a certain letter - Ala autocomplete style. There's also just a plethora other fancy schmacy methods we could have written for this Trie.

So it's not perfect but atleast we gave it a Trie! LOLOLOLOLOLOLOLOLOLOLOLOLOL...oh come on, that was a good one...fine, you can run off now for putting up with that.

HUMONGOUS shoutout to fellow fellow Sarah for pair whiteboarding this out with me. She's the best =)

Resources:

Trie

Recursion

Yoda

In the same vein as the other tips and tricks document for Ruby this will always be changing and updated. It's not a trick, it's an illusion....

Use jshint to check syntax.

Chrome Dev tools. Use it. Use it always. Heres a video on it's hidden secrets...shhhh...

Use filter method when creating arrays with values of a particular conditional

Object.keys returns all the properties that have been marked as enumberable when they were defined on on the Object.

Object.getOwnPropertyNames returns and an array of all the properties set directly in the object.

Write random things in a notebook during a restaurant visit for better treatment. They think you're a food critic.

You can use placecorgi.com or placekitten.com for quick place holder images on your site.

If you don't want lookie loos seeing your email you can hide it:

Use indexOf() to quickly see whether or not a value exists in a array. It returns -1 if it's not found. 

To sort an array by comparing numbers use this sort function:

Psuedo operator loading tricky tricks...more here

Debugger is a best thing ever! http://debugjs.com/

With Prototypal Inheritance the Parent Scope will be consulted when objects are not found on the childScope but not for brand new objects, Ex: 

childScope.anArray[1] = '22' //Will set the value on parentScope

childScope.anArray = ['22'] //Will create new object on childScope

Add something to array n number of times by leveraging .length

Hey 'member bitwise operations from Ruby? Well they're BACK!! In JavaScript that is BUT the good news is that it's all the same crap!

Bitwise AND

a & 0  == 0

a & -1 == a

Bitwise OR

a | 0 == a

a | -1 == -1

Bitwise XOR

a ^ 0 == a

a ^ -1 == -a

Bitwise NOT

~a = -(a + 1)

Bitwise Left Shift

a << b = a * b^2

Bitwise Sign-Propagating Right Shift

Sign-propa-whatnow? OK yes this is new. In this operation the bits are shifted to the right but the sign is preserved.

9 >> 2 = 2

-9 >> 2 = -3

Different, I know. Just stay with it and everything will be OK.

Bitwise Zero-Fill Right Shift

Did that sign bit freak you out? No worries, with this operation the results will always be positive. 

9 >>> 2 = 2 (whew!) 

-9 >>> 2 = 1073741821 (...I uhhh....I really just don't know)

Hey, things get weird you get this tiny. Now you know how to get pretty intimate with the computer and do some really quick operations using it's bits. Make sure you buy it a drink atleast before hand.

Resource: 

Think you know everything about Angular from reading one post? Well of course you do! That's just cuz you're super smart but what if I told you, you could search through all the stuff in your resource array without clicking a button or even refreshing the page? "Witch" they call me! Ha! Well I'll show them! Through some Angular magic.

You can do some sweet searching/filtering through the custom attribute <ng-model>. ng-model basically lets you create variables in real time in the ng-repeat (repeater's) scope. Now by doing this seemingly simple thing, a whole ginormous world of possibilities are about to open up!

Hold on tight, I'm about to blow yo freakin' mind!

Putting ng-model on an input type will basically create a variable "on the fly" and populate it with the value of whatever the user types in. Since that variable is in the controller's scope, you can use it to do things like filter/search and order your resources in the view. 

The way it works is the values that come from the iteration 'nics in nic' will be piped (|) to the input of the filter which is based on the value of what the user types in. What the user types is then bound (binded?) to the query property.

Since this updates in real time the user will see the updates of the search in real time. Without a page refresh. It's really sweet!

You can also use the | filter for other small bits of logic inside of the templating curly curlies

Re-re-repeat

ngRepeat updates the view in real time by only showing the results of the array that come out of the filter.

Fun Fact! The value of query can be accessed within the controller since it's defined in the same scope! I'll let you think a bit on all the fun goodies you can do with that. 

There's also the ability to have objects as variables. Where you can do alil sumthing like this:

Order it, just a lil bit...

Let's say you want your data to be displayed in a certain order based on a attribute in your data set (ex: by date, by nickiest nic, by age, etc.) - Well orderBy looks to be the tool for you.

It's as simply as setting a variable equal to the attribute of the data you want to initially sort/order by. Taking that variable and popping right next to the filter bad boy from above. Then wam bam thank you sam, you gots yourself another filter! The most convenient way to use it is within a select input so you can restrict the user's choice for ordering to properties on the object itself.

There's another directives you can use like ngClick to interact with your dataset. 

This will basically call the newMonkey() function you have defined on the controller's scope - which, if you recall, has access to dem there "on the fly" created variables from the user's input. So you might be able to do even more fun things there as well. 

Data Functions

Angular has a bunch of different options for encapsulating data gathering functionality, through: Factories, Services, Providers or Values. They all basically do the same thing, gather the data but differ in the way they create the object that gets the data. 

Factory - creates objects and attributes inside of the function and then returns the object.

Service:- Similar to Factory but instead uses defines attributes on the keyword this.

Provider - Has a $get function we can define and use to return the data. They can be configured during the module configuration phase.

Value - A way to get simple data, like key value pairs. 

I might have to get into this in a separate post but for now you can check out this example of the differences here: http://jsbin.com/ohamub/1/edit

So at this point you may be saying to yourself, "Wow! Now I REALLY know everything about Angular. Thanks Codeward!". To that I would say "Whoa whoa, there's still plenty of meat on that bone. You take what you learned here, try it out on your app, check out the Angular API Docs, throw it in a pot, add some server-side stuff, well then you got a stew going!"

For now that's all I have on all the amagical greatness that is AngularJS. There is plenty more to learn, so I advise you go seek out the docs and try things out like forking and improving my Nic Cage app here. Isn't this so much fun? And I didn't even have to use my witch powers this time...this time...

Resources:

AngularJS Filters

AngularJS API Docs