Friday, December 5, 2014

Microsoft Question: Find the pivot element in an array in which elements are first in strictly decreasing and then in strictly increasing order.

Question: 
You are given an array in which elements are first in strictly decreasing and then in strictly increasing order. You need to find the index of pivot element in that array.
For example: arr = {6, 4, 2, 4, 6} then index of pivot element is 2.

Solution:
Modify binary search for this particular problem.

int findPivotInDecIncArray(int *arr, int left, int right)
{
        int mid = left + (right - left) / 2;
        if(left > right)
                return -1;
        if(arr[mid] < arr[mid - 1] && arr[mid] < arr[mid + 1])
                return mid;
        if(arr[mid] <  arr[mid -1] && arr[mid] > arr[mid + 1])
                return findPivotInDecIncArray(arr, mid + 1, right);
        if(arr[mid] > arr[mid - 1] && arr[mid] < arr[mid + 1])
                return findPivotInDecIncArray(arr, left, mid - 1);
        return -1;

Thursday, November 27, 2014

Suffix Array

A suffix array is a sorted array of all the suffixes of a given string. It does the same thing which suffix tree does.
Advantage of suffix array over suffix trees include improved space requirements, simpler linear time construction algorithms and improved cache locality.

Building Suffix Array - Method 1: Make an array of all suffixes and then sort the array.

Implementation:

struct Suffix
{
        int index;
        char* suff;
};

bool compareSuffixes(const Suffix& s1, const Suffix& s2)
{
        return std::strcmp(s1.suff, s2.suff) < 0 ? true : false;
}

int* buildSuffixArray(char* str, int len)
{
        Suffix* suffixes = new Suffix[len];
        for(int i = 0; i < len; ++i)
        {
                suffixes[i].index = i;
                suffixes[i].suff = str + i;
        }
        std::sort(suffixes, suffixes + len, compareSuffixes);
        int *suffixArr = new int[len];
        for(int i = 0; i < len; ++i)
                suffixArr[i] = suffixes[i].index;
        return suffixArr;

}

Time complexity: O(n^2logn)

Building Suffix Array - Method 2: The idea is to use the fact that strings that are to be sorted are suffixes of a single string. The algorithm is mainly based on maintaining the order of the string’s suffixes sorted by their 2^k long prefixes.

Implementation:

struct Suffix
{
        int index;
        int rank[2];
};

bool compareSuffix(const Suffix& s1, const Suffix& s2)
{
        return s1.rank[0] == s2.rank[0] ? (s1.rank[1] < s2.rank[1] ? true : false) : (s1.rank[0] < s2.rank[0] ? true : false);
}

int* buildSuffixArray(char* text, int len)
{
        Suffix* suffixes = new Suffix[len];
        for(int i = 0; i < len; ++i)
        {
                suffixes[i].index = i;
                suffixes[i].rank[0] = text[i] - 'a';
                suffixes[i].rank[1] = ((i+1) < len) ? (text[i+1] - 'a') : -1;
        }

        std::sort(suffixes, suffixes + len, compareSuffix);

        int* index = new int[len];

        for(int k = 4; k < 2*len; k = k*2)
        {
                int rank = 0, prev_rank = suffixes[0].rank[0];
                suffixes[0].rank[0] = rank;
                index[suffixes[0].index] = 0;

                for(int i = 1; i < len; ++i)
                {
                        if(suffixes[i].rank[0] == prev_rank && suffixes[i].rank[1] == suffixes[i-1].rank[1])
                        {
                                prev_rank = suffixes[i].rank[0];
                                suffixes[i].rank[0] = rank;
                        }
                        else
                        {
                                prev_rank = suffixes[i].rank[0];
                                suffixes[i].rank[0] = ++rank;
                        }
                        index[suffixes[i].index] = i;
                }
                for(int i = 0; i < len; ++i)
                {      
                        int nextIndex = suffixes[i].index + k/2;
                        suffixes[i].rank[1] = (nextIndex < len) ? suffixes[index[nextIndex]].rank[0]: -1;
                }

                std::sort(suffixes, suffixes + len, compareSuffix);

        }

        int *suffixArr = new int[len];
        for(int i = 0; i < len; ++i)
                suffixArr[i] = suffixes[i].index;
        return suffixArr;

}


Searching a Pattern: Now we have a sorted array of all the suffixes, we can use binary search to search pattern in the text.

int search(char *text, char *pattern, int *suffArr)
{
        int len = std::strlen(text);
        int patrnLen = std::strlen(pattern);
        int left = 0, right = len - 1;
        while(left <= right)
        {
                int mid = left + (right - left) / 2;
                int result = std::strncmp(pattern, text + suffArr[mid], patrnLen);
                if(result == 0)
                        return suffArr[mid];
                if(result < 0)
                        right = mid - 1;
                else
                        left = mid + 1;
        }
        return -1;

}

Time complexity: O(mlogn)

________________________________________________

Random Access List

An interesting persistent data structure that combines the singly linked list with the binary tree is Random-Access List. This data structure allows for random access of its items as well as adding and removing items from the beginning of the list. 
                  It is structured as a Singly Linked List of Completely Balanced Binary Trees. The advantage of this data structure is that it allows access, insertion, and removal of the head of the list in O(1) time as well as provides logarithmic performance in randomly accessing its items. Following is a Random-Access list with 13 items --


Insertion: When a node is added to the list, the first two root nodes (if they exist) are checked to see if they both have the same height. If so, the new node is made the parent of the first two nodes; the current head of the list is made the left child of the new node, and the second root node is made the right child. If the first two root nodes do not have the same height, the new node is simply placed at the beginning of the list and linked to the next tree in the list.

Removal: To remove the head of the list, the root node at the beginning of the list is removed, with its left child becoming the new head and its right child becoming the root of the second tree in the list. The new head of the list is right linked with the next root node in the list. Just see the following figure to get clear picture --


Random Access: The algorithm for finding a node at a specific index is in two parts: in the first part, we find the tree in the list that contains the node we're looking for. In the second part, we descend into the tree to find the node itself. The following algorithm is used to find a node in the list at a specific index:
  1. Let I be the index of the node we're looking for. Set T to the head of the list where T will be our reference to the root node of the current tree in the list we're examining.
  2. If I is equal to 0, we've found the node we're looking for; terminate algorithm. Else if I is greater than or equal to the number of nodes in T, subtract the number of nodes in T from I and set T to the root of the next tree in the list and repeat step 2. Else if I is less than the number of nodes in T, go to step 3.
  3. Set S to the number of nodes in T divided by 2 (the fractional part of the division is ignored. For example, if the number of nodes in the current subtree is 3, S will be 1).
  4. If I is less than S, subtract 1 from I and set T to T's left child. Else subtract (S + 1) from I and set T to T's right child.
  5. If I is equal to 0, we've found the node we're looking for; terminate algorithm. Else go to step 3.
Following image illustrates how to find the 10th item in the list --

Algorithm for rest of the operations are straight forward. I don't think, we need to discuss.

______________________________________

Wednesday, November 26, 2014

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;
}

Monday, September 22, 2014

Hats on a death row.

Question:
A stark raving mad king tells his 100 wisest men he is about to line them up and that he will place either a red or blue hat on each of their heads. Once lined up, they must not communicate among themselves. Nor may they attempt to look behind them or remove their own hat.
The king tells the wise men that they will be able to see all the hats in front of them. They will not be able to see the color of their own hat or the hats behind them, although they will be able to hear the answers from all those behind them.
The king will then start with the wise man in the back and ask "what color is your hat?" The wise man will only be allowed to answer "red" or "blue," nothing more. If the answer is incorrect then the wise man will be silently killed. If the answer is correct then the wise man may live but must remain absolutely silent.
The king will then move on to the next wise man and repeat the question.
The king makes it clear that if anyone breaks the rules then all the wise men will die, then allows the wise men to consult before lining them up. The king listens in while the wise men consult each other to make sure they don't devise a plan to cheat. To communicate anything more than their guess of red or blue by coughing or shuffling would be breaking the rules.
What is the maximum number of men they can be guaranteed to save?

Solution:
The first wise man counts all the red hats he can see(Q) and then answers "blue" if the number is odd or "red" if the number is even. (Probability of living is 1/2)
Each subsequent wise man keeps track of the number of red hats known to have been saved from behind(X) and counts the number of red hats in front(Y) and then apply the following formula -

  1. If Q was even, and if X&Y are either both even or are both odd, then the wise man would answer blue. Otherwise the wise man would answer red.
  2. If Q was odd, and if X&Y are either both even or are both odd, then the wise man would answer red. Otherwise the wise man would answer blue.
So 99 wise men can be lived guaranteed.

Wednesday, May 21, 2014

Find nth minimum element in an array.

unsigned long partitionArray(int arr[], unsigned long left, unsigned long right)
{
unsigned long pivot = (rand() % (right - left + 1)) + left;
SWAP(arr[left], arr[pivot]);
unsigned long i = left + 1;
for(unsigned long j = left + 1; j <= right; ++j)
{
if(arr[j] < arr[left])
{
swap(arr[j], arr[i]);
++i;
}
}
swap(arr[i-1], arr[left]);
return i-1;
}

int RSelect(int arr[], int left, int right, int n)
{
if(left == right && left == n)
return arr[left];
int pivotIndex = partitionArray(arr, left ,right);
if(pivotIndex + 1 == n)
return arr[pivotIndex];
else if(pivotIndex + 1 > n)
return RSelect(arr, left, pivotIndex - 1, n);
else
return RSelect(arr, pivotIndex + 1, right, n);
}

Friday, May 9, 2014

Find second-largest number in the array in at most n+log2n−2 comparisons.

int* findMax(int *arr, int i, int j, int len)
{
if(i == j)
{
int* comp = new int[len];
comp[0] = 1;
comp[1] = arr[i];
return comp;
}
int *comp1 = findMax(arr, i, i+(j-i)/2, len);
int *comp2 = findMax(arr, 1+i+(j-i)/2, j, len);
if(comp1[1] > comp2[1])
{
int k = comp1[0] + 1;
comp1[0] = k;
comp1[k] = comp2[1];
delete [] comp2;
return comp1;
}
else
{
int k = comp2[0] + 1;
comp2[0] = k;
comp2[k] = comp1[1];
delete [] comp1;
return comp2;
}
}

int findSecondMax(int *arr, int len)
{
int *compared =  findMax(arr, 0, len-1, len);
int *max2Arr = findMax(compared, 2, compared[0], compared[0] + 1);
int max2 = max2Arr[1];
delete [] max2Arr;
return max2;
}

[Gfg] Number of inversions in an array

Problem: Find the number of pairs (i, j) of an array A indices with i < j and A[i] > A[j].

Example:

Input: arr[] = {8, 4, 2, 1}
Output: 6
Explanation: Given array has six inversions: (8, 4), (4, 2), (8, 2), (8, 1), (4, 1), (2, 1).

Input: arr[] = {1, 20, 6, 4, 5}
Output: 5
Explanation: Given array has five inversions: (20, 6), (20, 4), (20, 5), (6, 4), (6, 5). 


Approach: We can use brute force approach using two loops where we go to every index 'i' and count number of indices on its right (i +1... n) where arr[i] > arr[j] where j = i + 1 ... n. This approach will work but is time consuming (O(n^2)).

We can use merge sort here, basically we can take advantage of merge process. Whenever we see there is an element in the left subarray (left...mid) say leftArr[i] which is greater than element in right subarray (mid + 1...right) say rightArr[j] then we can easily say we will get mid - i + 1 inversions right?

This is because both the arrays are sorted and if there is an element at index i,  leftArr[i] is greater than rightArr[j] then it is obvious that all the elements in leftArr[i....mid] will be greater than rightArr[j].

That's all!


Implementation in C#:

    class Solution
    {
        //Complete this function
        //Function to count inversions in the array.
        public long inversionCount(long[] arr)
        {
            long length = arr?.Length ?? 0;
            if (length <= 1)
            {
                return 0;
            }
            return this.CountInversionCount(arr, 0, length - 1);
        }
        
        private long CountInversionCount(long[] arr, long left, long right)
        {
            if (left >= right)
            {
                return 0;
            }
            long mid = left + (right - left) / 2;
            long leftInvCount = this.CountInversionCount(arr, left, mid);
            long rightInvCount = this.CountInversionCount(arr, mid + 1, right);
            long mergeInvCount = this.Merge(arr, left, mid, right);
            return leftInvCount + rightInvCount + mergeInvCount;
        }
        
        private long Merge(long[] arr, long left, long mid, long right)
        {
            List<long> temp = new List<long>();
            long i = left, j = mid + 1;
            long invCount = 0;
            while (i <= mid && j <= right)
            {
                if (arr[i] > arr[j])
                {
                    invCount += (mid - i + 1);
                    temp.Add(arr[j++]);
                }
                else
                {
                    temp.Add(arr[i++]);
                }
            }
            while (i <= mid)
            {
                temp.Add(arr[i++]);
            }
            while (j <=  right)
            {
                temp.Add(arr[j++]);
            }
            i = left;
            for (j = 0; j < temp.Count; ++j)
            {
                arr[i++] = temp[(int)j];
            }
            return invCount;
        }
    }


Complexity: O(nlogn)

Tuesday, February 11, 2014

Rotate a Linked List

Problem:
Given a singly linked list, rotate the linked list counter-clockwise by k nodes. Where k is a given positive integer.

Approach:
To rotate the linked list, we need to change next of kth node to NULL, next of last node to previous head node, and finally change head to (k+1)th node. So we need to get hold of three nodes: kth node, (k+1)th node and last node.

Solution:
void rotateList(Node *&head, int k)
{
     if (k == 0)
       return;

    Node* curr = head;

    int count = 1;
    while (count < k && curr != NULL)
    {
        curr = curr->next;
        count++;
    }

    if (curr == NULL)
        return;

    Node *kthNode = curr;

    while (curr->next != NULL)
        curr = curr->next;

    curr->next = head;
    head = kthNode->next;
    kthNode->next = NULL;
}

Pairwise swap nodes of a given linked list.

void pairWiseSwap(Node *&head)
{
    if (head == NULL || head->next == NULL)
        return;

    Node *prev = head;
    Node *curr = head->next;

    head = curr;

    while (1)
    {
        Node *next = curr->next;
        curr->next = prev;

        if (next == NULL || next->next == NULL)
        {
            prev->next = next;
            break;
        }

        prev->next = next->next;
        prev = next;
        curr = prev->next;
    }
}

Average salary of n people in the room.

Question:
How can n people know the average of their salaries without disclosing their own salaries to each other?

Solution:
Let's say salaries of n people (P1, P2, P3.....Pn) are S1, S2, S3.....Sn respectively. To know the average of the salary i.e. (S1 + S2 + S3 + ..... + Sn) / n, they will follow the following steps -

  1. P1 adds a random amount, say R1 to his own salary and gives that to P2 (P2 won't be able to know P1's salary as he has added a random amount known to him only). In this case, P2 will receive the figure (S1 + R1) from P1.
  2. P2 does the same and gives the final amount to P3 (without showing that to anyone). Now P3 will get the figure (S1 + R1 + S2 + R2).
  3. Rest of the persons (P3, P4, P5.....Pn) do the same. Pn will give the final amount to P1. Now P1 will have (S1 + R1 + S2 + R2 + S3 + R3 + ...... + Sn + Rn).
  4. Now P1 subtracts his random amount (R1) and gives the final figure to P2 (without showing that to anyone). P2 will now receive the figure (S1 + R1 + S2 + R2 + S3 + R3 + .... Sn  + Rn) - R1 = (S1 + S2 + R2 + S3 + R3 + ...... + Sn + Rn).
  5. P2 subtracts his random amount (R2) and gives the final figure to P3 (without showing it to anyone). P3 will receive the amount (S1 + S2 + S3 + R3 + ..... Sn + Rn).
  6. In the same way every person remaining except (Pn) will subtract their random amount and give it to the next one. Now Pn will have (S1 + S2 + S3 + ..... Sn + Rn).
  7. Now Pn subtracts his random amount (Rn) and then the figure becomes (S1 + S2 + S3 + .... + Sn). Pn will divide this amount by n and get the average i.e. (S1 + S2 + S3 + ..... + Sn) / n and show to every one in the room.
(Puzzle was asked in the Yahoo interview)

Friday, January 24, 2014

MAZ Digital: Implement push, pop, findmin in O(1) without using extraspace

Maintain a variable min which will contain the minimum element.

push(n):     if(n < min)
                 {
                      stack.push( n - (min - n) );
                      min = n
                 }
                 else
                 {
                       stack.push(n)
                 }

pop():        retVal = stack.pop();
                 if( retVal < min)
                 {
                       temp = min;
                       min = min + ( min - retVal);
                       retVal =  temp
                 }
                 return retVal;

findMin():  return min;