Fibonacci calculation algorithm

Iterative version:

int fibonacci(int n) {
    if (n < 2)
        return n;
    int prev = 0;
    int last = 1;
    for (int i=2; i<=n; ++i) {
        prev = last;
        last = prev + last;
    }
    return last;
}

The time complexity is O(n) while the space complexity is O(3) or constant.

Recursive version:

int fib(int n) {
    if (n < 2)
      return n;
    return fib(n - 1) + fib(n - 2);
}

However, this straightforward solution for Fibonacci is extremely inefficient. Since the computation complexity would be exponential as many text books indicated. An intelligent solution is given below, which is O(n). The origin of this solution is here.

int fib(int n, int p0=0, int p1=1) {
    if (n==0)
        return 0;
    else if (n==1)
        return p1;
    else
        return fib(n - 1, p1, p0 + p1);
}

There are recursive solutions are doing even better than O(n). See this link.

Find the ith smallest element of the array in O(n)

How to find the ith smallest element of the array in O(n) time is a frequently asked question. The straightforward solution is sorting the array and return the ith element. However, for general cases, it's proven that sorting algorithms like merge sorting, is lower bound to O(nlogn). Thus finding the ith smallest element is unfeasible by a merge sorting. Although for some special cases, such as, the possible values or data range of the array is relatively small, counting sorting can give a O(n) solution, it doesn't work for general cases. The solution below works generally and the expected running time is O(n).

int find_ith_smallest_elem(int* A, int left, int right, int i) {
    if (left==right)  //only one element left, then it's the answer
        return A[left];
    pivot = random_partition(A,left,right);
    left_partition_length = pivot - left + 1; //1 counts for the pivot itself
    if (i==left_partition_length)
        return A[pivot];  //pivot is the answer
    else if (i<left_partition_length)
        return find_ith_smallest_elem(A,left,pivot-1,i);
    else
        return find_ith_smallest_elem(A,pivot+1,right,i-left_partition_length);
}

//randomly choose a pivot and partition the array into two parts, where the left part only
//contains elements smaller than the pivot while the right part only contains larger ones
int random_partition(int* A, int left, int right) {
    int pivot = rand(left,right);
    swap(A,pivot,right); // swap the pivot and the right-most element
    int pivot_value = A[right];
    int i = left - 1;
    for(int j=left; j<right; ++j) {
        if (A[j]<=pivot_value) {
            i++;
            swap(A,i,j); 
        }
    }
    swap(A,i+1,right);
    return i+1;
}

Interview question

Question
Got a phone interview recently. The question is how to find out an integer which appears more than 50% times in an array of integers. For example, [1 1 0 1 2] should return 1, while [1 1 0 2 3] should return nothing.

Solution
The basic idea is finding out a candidate before checking if it repeats more than enough times. The algorithm is described in a paper entitled "Finding Repeated Elements" by Misra and Gries. The algorithm consists of two steps. First, it identifies a candidate value. The candidate value either occurs >50% of the time or there is no element in the array that occurs >50% of the time. The second step verifies whether the candidate element does indeed occur >50% of the time. Here's the algorithm, implemented in C:

#define undefined (-1)
int find_element(int array[], int n)
{
    /* Step 1: Find the element that occurs >50% of the time, if there is one.  */
    int c = 0;
    int candidate = undefined;
    for (int i = 0; i < n; i ++)
    {
        if (array[i] == candidate)  /* Match.  */
            c += 2;
        else if (i == c)  /* New candidate.  */
        {
            c += 2;
            candidate = array[i];
        }
    }

    /* Step 2: Verify that the candidate actually occurs >50% of the time.  */
    for (i = 0, c = 0; i < n; i ++)
        if (array[i] == candidate)
            c ++;

    if (c * 2 > n)
        return candidate;
    else
        return undefined;
}

Compressed Row Storage (CRS)

The Compressed Row Storage format is the most general way to compress a matrix, since it makes absolutely no assumptions about the sparsity structure of the matrix, and it doesn't store any unnecessary elements.

CRS store matrix in the {val, col_ind, row_ptr} format, where val, col_ind and row_ptr are explained below:

• val: vector stores the values of the nonzero elements of the matrix in a row-wise order.
• col_ind: vector stores the column indexes of the elements in the val vector.
• row_ptr: vector stores the locations in the val vector that start a row.

A quick example, matrix A = 

| 7  0  0  2 |

| 0  2  0  4 |

| 1  0  0  0 |

| 3  8  0  6 |

val = [7 2 2 4 1 3 8 6]

col_ind = [1 4 2 4 1 1 2 4]

row_ptr = [1 3 5 6 9]

Covert a matrix A to CSR format in MATLAB, first set A = A' and then run following codes:

[col_ind row_ind val] = find(A);
[row col] = size(A);
val = zeros(1,length(row_ind));
row_ptr = zeros(1,row+1);
row_ptr(1)=1;
row_ptr(row+1)=length(row_ind)+1;
l = 2;
row_ind_temp = row_ind(1);
for i=1:length(row_ind)
    val(i)=A(row_ind(i),col_ind(i));
    if row_ind(i)~=row_ind_temp
        row_ptr(l)=i;
        l=l+1;
        row_ind_temp=row_ind(i);
    end
end