Synopsys Question: Sort array which contains only 0 and 1.

Problem: Sort a given array which contains only 0 and 1.

Solution: Take two pointers; one from start and one from end. Move them towards each other until start is pointing to 1 and end is pointing to 0. In this case swap the elements.

Implementation:

void sortArray(int arr[], int len)
{
int l = 0; int r = len - 1;

while(l < r)
{
while(arr[l] == 0 && l < r)
++l;
while(arr[r] == 1 && l < r)
--r;
if(l < r)
{
std::swap(arr[l], arr[r]);
++l;
--r;
}
}
}

Complexity: O(n)

Synopsys Question: Check if any two intervals overlap among the given n intervals

Problem: Given n intervals, each interval having start and end time, check if any two intervals overlap or not.

Solution: 

1. Sort all intervals according to their start time.
2. In the resultant sorted array, if start time of current interval is less than end of previous interval, then there is an overlap.

Implementation:

struct Interval

{

int start;

int end;

};

bool compareInterval(Interval i1, Interval i2)

{

return i1.start < i2.start ? true : false;

}

bool isOverlap(Interval *arr, int len)

{

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

return false;

std::sort(arr, arr + len, compareInterval);

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

{

if(arr[i].start < arr[i-1].end)

return true;

}

return false;

}

Complexity: O(nlogn)

Synopsys Question: Find the maximum sum in an array with no two elements are adjacent

Problem: Find the maximum sum in an array such that no two elements are adjacent.

Solution: 

Maintain two sums for each element of the given array:

1. sum1 = Max sum including the previous element
2. sum2 = Max sum excluding the previous element

Now:

1. Max sum excluding the current element = max(sum1, sum2)
2. Max sum including the current element = arr[i] + sum2

At the end max of the sum1 and sum2 will be our resultant value.

Implementation:

int maxSumWithoutAdjacentElem(int *arr, int len)
{
if(arr == NULL || len == 0)
return -1; //Error value

int sumIncludingCurr = arr[0], sumExcludingCurr = 0;

for(int i = 1; i < len; ++i)
{
int tempExcludingSum = max(sumIncludingCurr, sumExcludingCurr);
sumIncludingCurr = sumExcludingCurr + arr[i];
sumExcludingCurr = tempExcludingSum;
}

return max(sumIncludingCurr, sumExcludingCurr);
}

Complexity: O(n)