K-th smallest element

Reading time ~1 minute

Task: Given an unsorted array of integers, find the k-th smallest entry.

Solution: this can be viewed as a reduce-and-conquer problem. The key-idea is to select an element as pivot and split the array into two sub-arrays, smaller (A) and greater (B) than pivot. Then, as long the length of A is greater or equal to k, we delegate the task to this array. Otherwise, we check if the rank of the smallest entry in B is greater or equal to k in the original array (n-|B|). If so, delegate the problem to B with k’ = k-(n-|B|). Otherwise, return the pivot value.

The worst case time of this method is O(n^2), for more information see the Wikipedia article.

Getting started with Flutter on Mac

[Flutter](https://flutter.io/) is a great Google SDK allowing effortless creation of mobile apps with native interfaceson iOS and Android...… Continue reading

On designing and running online experiments

Published on February 28, 2018

Software Engineering at Cxense

Published on April 17, 2017