Pages

Friday, March 11, 2011

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.

Sunday, March 6, 2011

Use sequence to solve the problem

When I went through a problem which requires to find the maximum of difference between two elements. The 2nd element's index must greater than the 1st element. So the way to solve the problem is two steps:

1. generate the sequence
2. filter the element which meet the requirement.

Before we start, somebody might want to ask, what is the performance of the code if we generate a whole list and then filter it. Do not worry, the sequence is not holding any memory or resource. It is just a lazy evaluation, so it will just return one element at one time.

Now we can concentrate on how to solve the sequence problem. We need to find a function to generate
    output = sequence of (element0, element1)
from
    input  = sequence of element

when we get the output, we need to find the element where (element1-element0) is the maximum.

the sequence is IEnumerable < (element, element) > by using yield return statement

for ( i = 0 ; i < input.Length; i++)
    for (j=i; j < input.Length; j++)
        yield return ( input[ j ], input[ i ] );

After we have this output sequence, we try to get the maximum by using output.Max(n => n.element1 - element.0)

The way I like functional programming is it more like human's thinking. The closer we think like human (or in a mathematical way), the less chance we generate an error. If we can represent a program in a mathematical way, it'll be much easier to verify it as well. In this solution, I still got some FOR loop, in this solution, let me come back later to get rid of this FOR.

Today seems a good time to get rid of FOR.

the idea is simple: we need two sequence, one is [1..count], the other has to use the element from first sequence as a parameter.

Enumerable.Range(0, count).SelectMany(i => Enumerable.Range(i, count - i).Select(j => new Tuple(i, j)));