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, because it's not a p

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