Prepare for a move - algorithm

Most of the algorithm is like solving a puzzle, it is interesting, but it lacks of math. I came across an algorithm problem, which is interesting to me, at least more math involved.

Given a complete binary search tree in form of array. Write a sort function to sort the given array in O(n)time complexity and constant memory.

________100
_____50_______150
___25___75__125___200

then array is {100 50 150 25 75 125 200}

the trick is the tree is a full binary tree.

if the node is left most node: its index = (0 + parent node's index) / 2
if the node is right most node: its index = (n + parent node's index) / 2
other nodes: its index = (parent's index + grandparent's index) / 2

with this formula, it is easy to pin point the location.

Prepare for a move - threading and parallel

Finally, it is time to prepare for some move in the future. When you buried in everyday work, you must have got tunnel vision, I hope this preparation process will give me some fresh air. You might use the low performance statement every day or totally lose your mind when being ask what is "algorithm X" with O(n). :-) Let us start my journey and hopefully learn something new.

The first topic I want to touch is to use lock keyword in the C#.

if there are some variables in the class and how to use lock to update it.

if it is a int or long, use the interlock.increament if that is possible. Otherwise, the general rule is

1. declare a private or protected variable as syncroot
2. if the variable is value type, then lock the syncroot
if the variable is ref type, lock the variable itself.

Actually, if you want to get your work done, use the data structure under System.Collection.Concurrent namespace (new .net 4.0) , which is usually get rid of the need for explicit synchronization.

One catch I found is that on 32-bit system, the reading a 64-bit int is NOT atomic. You have to use Interlock.Read(). In a 64-bit system, reading 64-bit int is atomic.

Today I found the [ThreadStatic] attribute is very useful when design the multi-thread application. It has unique value for each thread!

Find the maximum difference in a sequence

Let us put another interview question solution with F# (functional way). The question is to find the x[a], x[b], where x[b] - x[a] -> maximum

we are going to find a tuple (a,b) where x[b] - x[a] -> maximum. Be careful b must be greater than a. So our first problem will be how to generate a sequence (a,b) where b>a and a between (0, L).

f(i) will generate a sequence from i to L.
f(i) -> [i..L] |> Seq.map (n-> (i,n))

[0..L]
|> Seq.map (i-> Seq.map (n->(i,n)) [i..L] ) //generate the (a,b) tuple
|> Seq.collect (n->n) //flatten the sequence
|> Seq.maxby ((a,b)->x[b]-x[a]) //find the max dif

Use sequence to solve the interview question

When I looking into some interview questions, I found interesting to solve them without using FOR-loop.

The first thing to do is to group list according to its index. So the input will be list and the output will be a grouped list. Let us start to group the list into two elements unit. The idea is simple:

{ ai } |> { (ai, i) } |> { (ai, i/2) } |> groupby second part

when we have a sequence, we make an element with its index and then we transform its index and group the transformed index. Let me give the code later on.