100 Days of Visualizing Algorithms

How can we check if a linked list has a cycle in it?  There’s a pretty clever way to do it - keep two pointers, one that moves forward by one node (blue), and one the moves forward by two nodes (black).  If there’s a cycle, then the black node wrap around and “catch” the blue node.  If the nodes never overlap, then there can’t be a cycle.

If we get an array that has other arrays in them, which in turn could have more arrays in them, how can we flatten the structure out to a single array?  We simply look at the type of the element, and if it’s an array, we recursively apply the same flatten functionality. 

How can we tell if strings are anagrams of each other, i.e., they have the same letters, but the order doesn’t matter.  So “monk” and “konm” are anagrams.  This one is really easy, we just sort all the strings, then we can directly compare.  But how can we improve the comparison step so we dont’ have to compare every sorted word against every other sorted word?  We can use a dictionary to store sorted words as keys, and all their unsorted words as an array.  Then, we simply do a dictionary lookup, which is constant time, and then we just have to compare our input word to the words in the anagram dictionary.

Another programming challenge question.  This questions asks you to, given an array of integers, find the next smallest integer for each integer in the original array.

Took the homepage of the New York Times website, and walked through it’s DOM to visualize it’s tree structure.  What we can see from here is that there are a lot of top level script and meta tags, but the bulk of the content is really contained all inside one element.  Wished I could have zoomed in on that mess of elements in the center, but ran out of steam again.  The closer I get to 100, the less steam I seem to have.

A doubly linked list is just a link list where each node has a pointer to both the next node and the previous node.  Makes it possible to traverse the list from either end.

A linked list is a classic data structure that connects nodes through points to the nodes after them.  Unlike an array, you can’t just grab an element of a linked list by it’s index.  They don’t have indices.  Instead, you have to traverse the list until you find what you want.  Same for inserting, you have to traverse all the way to the end to add a new node in.  So what’s the point?  It digs into technicalities a bit, but inserting and removing nodes from a linked list can be quite a bit faster than an array, since we don’t have to copy the entire list and move it somewhere else in memory.  

Another little puzzle.  You have 100 doors that are initially closed.  First, you go through each door and toggle it (if it’s closed, open it; if it’s open, close it).  On the first pass, we just open each door.  On the second pass, don’t visit every door, but visit every second door, and toggle it.  On the third pass, visit every third door and toggle it.  Continue this pattern (i.e on the 47th pass, you visit every 47th door - which is just the 47th door and the 94th door) until you’ve performed 100 passes through the doors.  What’s fascinating about this puzzle is that the open doors will always be the perfect squares; that is, the 1st door, the 4th, the 9th, the 16th, 25th, 36th, and so on.

Unsure of how to spend your time?  Let your computer decide for you!  The idea is there are a series of tasks that have start times and end time.  Assuming that the value of doing each task is equal, which tasks should you choose?  Ran out of steam on this one and didn’t get past a static image representing the output.

A programming problem I came across recently.  The goal is to figure out if a string of brackets is balanced (i.e. closed properly).  The idea is to add open brackets to a stack, and when we encounter a closing bracket, if it’s matching open bracket is at the top of the stack, then we know we have a match and we remove the top of the stack.  If at any point we find a mismatch, we return that the string is unbalanced.

I was curious to see what other patterns would emerge from the chaos game process.  This animation loops through regular polygons, decreasing the number of vertices.  There are patterns to be seen, somewhat like the Menger Sponge, but they’re tough to see without more points,

Now, a little visualization of how the chaos game actually works.  Yesterday’s description walks through the process, this illustrates it.

Chaos Game has simple rules.  Start with a set of vertices (in this case I’m using vertices of an equilateral triangle).  Then pick a random point, and choose a random vertex.  Split the distance between the randomly chosen point and randomly chosen vertex, and that’s where you place an actual point.  What’s amazing is that if we use an equilateral triangle as our vertices, we get the Sierpinski triangle.  Everything’s related, I guess.

I love the seriously dated names involved in this problem.  Anyway, the stable marriage problem assigns pairs of things based on the preferences of those things.  With people, for instance, Abe has a list of preferences of who he’d like to marry, so does Abi, so does everyone else.  A marriage is considered stable if there is not another person that either person wants more that is not already in a stable marriage.  Essentially, any more preferred people are already in stable marriages.  Ignoring the terminology for now (it was though up in 1962, a different time), it turns out to be a very useful strategy for things like matching clients to servers in distributed networks, or finding kidney matches.

FizzBuzz is the simplest of toy problems often presented to interview applicants to test right away whether they have ever really programmed before.  It’s really simple - for each number from 1 to 100, if the number is divisible by 3, print “Fizz”, if the number is divisible by 5 print “Buzz”, and it’s divisible by both 3 and 5 print “FizzBuzz”.  There’s been some controversy about the merits of using FizzBuzz as an interview technique, some think it’s too simple, or focuses on the wrong things, while others hold that it’s a necessary first step to reduce otherwise large applicant pools.  Whatever your feelings, fizzbuzz represents the strange ways in which programmers get jobs.

Long view of Fisher-Yates shuffle.  Red lines represent the elements being swapped on the current iteration.  You can see how it works it’s way backwards.

Shuffle an array of elements.