Day 100 - Linked List Cycle
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.
Day 99 - Flatten a Nested Array
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.
Day 98 - Anagrams
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.
Day 96 - DOM Tree
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.
Day 94 - Linked List
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.
Day 93 - 100 Doors
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.
Day 92 - Job Scheduling
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.
Day 91 - Matched Brackets
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.
Day 90 - Chaos Game V3
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,
Day 88 - Chaos Game
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.
Day 87 - Stable Marriage
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.
Day 86 - Ode to FizzBuzz
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.
