Pubmatic Question: Longest Bitonic subsequence

Given an array arr[0 … n-1] containing n positive integers, a subsequence of arr[] is called Bitonic if it is first increasing, then decreasing. Write a function that takes an array as argument and returns the length of the longest bitonic subsequence.

Solution:

int lbs(int *arr, int len)

{

        if(arr == NULL || len == 0)

                return 0;

        int *lis = new int[len];

        for(int i = 0; i < len; ++i)

                lis[i] = 1;

        for(int i = 1; i < len; ++i)

        {

                for(int j = 0; j < i; ++j)

                {

                        if(arr[i] > arr[j] && lis[i] < lis[j] + 1)

                                lis[i] = lis[j] + 1;

                }

        }

        int *lds = new int[len];

        for(int i = 0; i < len; ++i)

                lds[i] = 1;

        for(int i = len-2; i >= 0; --i)

        {

                for(int j = len-1; j > i; --j)

                {

                        if(arr[i] > arr[j] && lds[i] < lds[j] + 1)

                                lds[i] = lds[j] + 1;

                }

        }

        int max = lis[0] + lds[0] - 1;

        for(int i = 1; i < len; ++i)

        {

                if(max < lis[i] + lds[i] - 1)

                        max = lis[i] + lds[i] - 1;

        }       

        return max;

}

Pubmatic Question: Bitonic subarray with maximum length

Given an array A[0 … n-1] containing n positive integers, a subarray A[i … j] is bitonic if there is a k with i <= k <= j such that A[i] <= A[i + 1] ... <= A[k] >= A[k + 1] >= .. A[j – 1] > = A[j]. Write a function that takes an array as argument and returns the length of the maximum length bitonic subarray.

Solution:

int maxBitonicSubArrayLen(int *arr, int len)

{

        if(arr == NULL || len == 0)

                return 0;

        bool isDecreasing = false;

        int max = 1, count = 1;

        for(int i = 0; i < len - 1; ++i)

        {

                if(arr[i] <= arr[i+1])

                {

                        if(isDecreasing)

                        {

                                count = 1;

                                isDecreasing = false;

                        }

                        ++count;

                }

                else

                {

                        if(!isDecreasing)

                                isDecreasing = true;

                        ++count;

                }

                if(max < count)

                        max = count;

        }

        return max;

}

Pubmatic Question: Average of the elements of an array

Only Problem in this question is to tackle integer overflow. Instead of doing
(a[0] + a[1] + ....a [n-1])  /  n
do as following --
a[0]  / n + a[1]  /  n + ..... a[n-1]  /  n