I’m a fan of tries. I can’t claim that I’ve used them in practice, but I wish I had. They’re super! Common uses: substring search spell check autocomplete This is an implementation I just put together. Enjoy! Trie API: add(word) - Add the given word to the…
Read more
Geometric algorithms involve questions that would be simple to solve by a human looking at a chart, but are complex because there needs to be an automated process. One example is: given four points on a 2-dimensional plane, and the first three of the points create a triangle, determine if the…
Read more
I wanted to clarify the programming language requirement for the interview. I was under the impression that I needed C++ or Java to do the interview, and that in some cases C would suffice. But I also felt the need to know Python, since it is also widely used. A further reason for getting deep into…
Read more
Greed is good. And Dijkstra’s algorithm is greedy. Dijkstra’s algorithm not only calculates the shortest (lowest weight) path on a graph from source vertex S to destination V, but also calculates the shortest path from S to every other vertex. My implementation in Python doesn’t…
Read more
I put on my sorting hat and watched many, many videos on sorting. The videos covered: bubble sort selection sort insertion sort heap sort merge sort quicksort counting sort radix sort There are several more sorting algorithms I could have gone into, but I had to stop somewhere. I’d like to…
Read more
I’ve been studying for quite a while now, and even though I coded up data structures like crazy, I feel the knowledge fading. What I want is two special sets of flash cards: - general CS knowledge - vocabulary - definitions of processes - powers of 2 - design patterns - Big-O of…
Read more
In my study of data structures, I’ve made it to hash tables. I’m spending a little extra time on this one, because there is some math and inherent gotchas in hashing and I want to fully understand. I may not get all the math, but I’ve got the important bits. In addition, hash…
Read more
I ended up with 2 implementations of linked lists in C, an object-oriented approach in C++ (with templates!), and followed up with a smaller OO implementation in Python. I’m pretty proud of these. The C and C++ versions have test suites, so I’m very confident with the code. For the…
Read more
This is the first of a few reviews I’ll be posting of online courses available. 6.00.1x: Introduction to Computer Science and Programming Using Python is available though EdX, using coursework and instructors from MIT. https://courses.edx.org/courses/course-v1:MITx+6.00.1x_8+1T2016/info The…
Read more