I’ve been into a couple of interviews during the last two weeks. Today I got an interesting question: “reverse a single-linked list, in place”. The solution I suggested was good, but not great - “a better solution would use non-static recursion and be only two lines long”. After some thinking on the way home, I think the answer could look like this (updated version):
A traditional way to debug programs is to carefully place print-statements here and there. However, as the amount of printed text increases the ability to filter out and understand the important information decreases. For this reasons, I have searched on how to use ANSI color codes in Java and found a nice implementation in Jlibs. Unfortunately this library did way more than what I needed, and therefore I have stripped it down into a small class that wraps a text string to add color codes and attributes. Feel free to use it and thanks a lot to the original author :-)
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.
Finding all possible, non-empty subsets of an array is actually a really simple task. Everything you need is a counter between 1 and 2^n-1, where n is the number of entries. For each possible value of the counter check it’s bits - 1 at position i means that i’th value of the array is present in the particular subset. No recursion, only shifts and additions.
I haven’t been programming algorithms for fun for the last 4, maybe 5 years. At the moment I have realized that it could be a good thing to do… So this is the first try :)
###The idea: Sequences can be viewed as numbers: 1 : 1 , 2 : 11 2, 3: 111 12 21 3, etc. This has a nice recursive property, for an x we take all the numbers y in [1,x] and append in in front of the solution for (x-y). Except x=1 and 0, which give “1” and “ ” respectively.
A simple solution is as follows:
Now, the problem with this solution is recursion and repeated calls to same print(String,int) and balls(int). The running time is O(2^n). A better solution is as follows (perhaps ArrayList can be swaped out with an array):
The running time is O(n^3).