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
Today I’m studying flow graphs and disjoint sets data structure. Maximum flow falls into the category of combinatoric optimization problems. The Ford-Fulkerson method, published in 1956, is a way of solving the computation of maximum flow through a flow graph, which could represent a network…
Read more
This well-known article, Numbers Everyone Should Know, was intriguing, but it was hard to mentally get a handle on the scale of the numbers. Here are a few: So I converted some of them into round trips, since data accesses are round trips in themselves. I started with an L1 cache access, at 0.5ns,…
Read more
Back on August 8, I talked about how I was going to change up my study schedule for the interview. I discovered that it was difficult to interleave learning new things and practicing, and I wanted to get past the learning phase done so I can just practice all day long. The Remainder of the Learning…
Read more
Today I studied cryptography and compression, so I’m trucking along. These topics are not on the coaching docs I’ve seen, but I added them to round out my studies. I’m basically trying to compress a 4 year CS degree into less than 1 year. It’s lossy…
Read more
I’ve heard the term “entropy” over the years and never understood it until now. I used to think entropy was randomness, and it’s kind of related. Entropy can be defined in a few ways, some more complicated than others. Entropy is a measure of how much information is gained…
Read more
Yes, you can sort in linear time, as long as you’re avoiding comparisons. Radix sort and counting sort are two examples. They both avoid comparisons, and are possible because they sort based on grouping by a single element at a time, where that single element is a letter or digit (in…
Read more
Time management can be tough. I found myself spending way too long on some subjects. Some take more time than others. Graphs, trees and sorting take more time to go over than studying priority queues, for example. But I could just watch videos on dynamic programming for days. I just keep learning…
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
I needed this for myself, and Googled around but didn’t find anything satisfactory, but now after a little work, I’m all set with Valgrind. Wouldn’t you love this on your toolbar? Well, you can have it, friend. Read on. 1. Add this Bash script I have it in my current project,…
Read more