Adam Horvath's blog

The formula of a circle is quite straightforward ( r=sqrt(x^2+y^2) ) but it's not trivial how to draw a circle or calculate the trigonometric functions without advanced math. However, an interesting finding from 1972 makes it really easy. Minsky discovered (by a mistake) that the following loop will draw an almost perfect circle on the screen: loop:     x = x - epsilon * y     y = y + epsilon * x # NOTE: the x is the new x value here Turns out that epsilon in the equation is practically the rotation angle in radians, so the above loop will gradually rotate the x and y coordinates in a circle. Calculating sinus If we can draw this circle, we can easily estimate the sinus values: for the current angle, which is basically the sum of epsilons so far,  we have a height (y), which just needs to be normalized to the 0-1 range to get the actual sinus for the angle. The smaller the steps (epsilon) are, the more accurate the formula will be. However, beca...

One of the typical interview questions is the three way partitioning, also known as the Dutch national flag problem: given an array with three different values, sort it in a way that all values are grouped together (like a three colored flag) in linear time without extra memory. The problem was first described by Edsger Dijkstra. As it's a typical sorting problem, any sorting would do but they would need n*log(n) time. There are two good solutions to it: do a counting sort which requires two passes over the array; place the elements to their correct location using two pointers. The latter uses a reader, lower, and an upper pointer to do the sorting. Reader and lower starts from one end of the array, upper pointer starts at the other end. The algorithms goes like this: - If it's a small value, swap it with the lower pointer and step lower pointer one up - If it's a middle value, do nothing with it and step reader pointer one up - If it's a larger value, swap ...