This is an classical question, the general solution to this question is first using sorting algorithm to sort the array, then get the kth number in the array, the complexity is O(nlogn), we can also use selective sort or head sort to, the complexity of selective sort is O(kn) and heap sort is O(nlogk). The better solution is to use quick sort to find the kth smallest number, the complexity is O(n), the worst case cost is O(n^2). But today we introduce one more solution which has the worst case cost O(n).First let's check the quick sort solution, quick sort is to find one number, then put all n...

Array sorting algorithm question is frequently asked during technical interviews. There are lots of sort algorithms including bubble sort, selection sort, insertion sort, quick sort, merge sort etc. Usually interviewees will be asked to implement sort algorithms. But have you ever been asked to sort an array which you are allowed to define ONLY ONE local variable in your algorithm? Bubble sort can be used to do this actually. Normally a bubble sort algorithm may need three local variables : the index variable, the boolean variable to determine whether continue, a temp varia...

You may be familiar with integer overflow, but what you may not be familiar with is how gcc handles signed integer overflow.First let's look at the standard, for unsigned integer, the standard says :A computation involving unsigned operands can never overflow, because a result that cannot be represented by the resulting unsigned integer type is reduced modulo the number that is one greater than the largest value that can be represented by the resulting type.In other words, unsigned integer overflow will be wrapped so that it will be still in the range of an unsigned integer.For signed integer,...

There’s a charming little brain teaser that’s going around the Interwebs. It’s got various forms, but they all look something like this:This problem can be solved by pre-school children in 5-10 minutes, by programer – in 1 hour, by people with higher education … well, check it yourself! 8809=67111=02172=06666=41111=03213=07662=29313=10000=42222=03333=05555=08193=38096=57777=09999=47756=16855=39881=55531=02581=?SPOILER ALERT…The answer has to do with how many circles are in each number. So the number 8 has two circles in its shape so it coun...

I am a great programmer, but a horrible algorithmist. It is a thought that has been weighing on me heavily recently, and I'd like to gather other developers feelings on the subject as well.I started what can be called my professional development career back in 1999. I was still in middle school, but my father hired me at his software company. My official duty was to make updates to our websites, but I mostly ended up bugging the other developers to help me learn.From there I picked up Perl (somewhat) and then moved to PHP and front end web development where I have stayed comfortably for the l...

After having started to build my own internet search engine as described in a previous blog post, I now have read some papers and books about web search engine architecture and information retrieval to complete my hobby project. Here is a list of papers and books that I highly recommend to anybody who is interested in this topic:1. Google: data structures and algorithms by Petteri Huuhka2. The Anatomy of a Large-Scale Hypertextual Web Search Engine by the Google founders Sergey Brin and Lawrence Page3. Introduction to Information Retrieval by Christopher D. M...

This post is meant to be a gentle introduction to Algebraic Data Types. Some of you may be asking why you should learn Algebraic Data Types and how will they change your world?  I am not going to answer that, but suffice it to say that Algebraic Data Types are the underpinning of the type systems to the ML derived languages, Haskell and OCaml included, and their construction and properties allow for the power (and inference) that accompanies these type systems.  They are cropping up in other languages, like Scala, F#, and Clojure.  Well, here are my 2 cents.I wrote this blog pos...

The Tower of Hanoi is a mathematical game or puzzle. It consists of three rods, and a number of disks of different sizes which can slide onto any rod. The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top, thus making a conical shape.The objective of the puzzle is to move the entire stack to another rod, obeying the following rules:Only one disk may be moved at a time.Each move consists of taking the upper disk from one of the rods and sliding it onto another rod, on top of the other disks that may already be present...