WAP to Find majority Eelement In Linked lIst In One Pass

you hve a linked list of unknown length n. there is an element which is repeated more than n/2 number of times. find that element... you should use constant extra space and can make only one pass over the list.....

#include
#include
struct node
{
int data;
struct node *next;
};

struct node *head = NULL;
struct node *tail = NULL;

int push(int input)
{
struct node *newnode = (struct node *)malloc(sizeof(struct node));
if(!newnode) return 0;
newnode->data = input;
if(tail) {
tail->next = newnode;
}
newnode->next = NULL;
tail = newnode;
if(!head) head = newnode;
return 1;
}

int display()
{
struct node *current = head;
while(current)
{
printf("%d\n", current->data);
current = current->next;
}
}

int freenodes()
{
struct node *current = head;
if(head) head = head->next;
while(current)
{
free(current);
current = head;
if(head) head = head->next;
}
printf("Linked List Freed\n");
}

int findmaxrepeat()
{
if(!head) return 0;
struct node *current = head->next;
int value = 0;
int count = 0;
int maxvalue = 0;
int maxvaluecnt = 0;
value = head->data; count +=1;
maxvalue = value;
maxvaluecnt = count;
while(current)
{
if(current->data == value) count +=1;
else
{
if(maxvaluecnt < count) { maxvaluecnt = count; maxvalue = value;}
value = current->data; count = 1;
}
current = current->next;
}
return maxvalue;
}

int main()
{
push(1);
push(3);
push(2);
push(3);
push(3);
push(1);
push(1);
push(3);
push(3);
push(1);
push(3);
display();
printf("%d is the maxrepeated value\n", findmaxrepeat());
freenodes();
}

TC O(n)
SC O(1)
Run Here https://ideone.com/qmu7Z

WAP to Find majority Eelement In Linked lIst In One Pass

you hve a linked list of unknown length n. there is an element which is repeated more than n/2 number of times. find that element... you should use constant extra space and can make only one pass over the list.....

#include
#include
struct node
{
int data;
struct node *next;
};

struct node *head = NULL;
struct node *tail = NULL;

int push(int input)
{
struct node *newnode = (struct node *)malloc(sizeof(struct node));
if(!newnode) return 0;
newnode->data = input;
if(tail) {
tail->next = newnode;
}
newnode->next = NULL;
tail = newnode;
if(!head) head = newnode;
return 1;
}

int display()
{
struct node *current = head;
while(current)
{
printf("%d\n", current->data);
current = current->next;
}
}

int freenodes()
{
struct node *current = head;
if(head) head = head->next;
while(current)
{
free(current);
current = head;
if(head) head = head->next;
}
printf("Linked List Freed\n");
}

int findmaxrepeat()
{
if(!head) return 0;
struct node *current = head->next;
int value = 0;
int count = 0;
int maxvalue = 0;
int maxvaluecnt = 0;
value = head->data; count +=1;
maxvalue = value;
maxvaluecnt = count;
while(current)
{
if(current->data == value) count +=1;
else
{
if(maxvaluecnt < count) { maxvaluecnt = count; maxvalue = value;}
value = current->data; count = 1;
}
current = current->next;
}
return maxvalue;
}

int main()
{
push(1);
push(3);
push(2);
push(3);
push(3);
push(1);
push(1);
push(3);
push(3);
push(1);
push(3);
display();
printf("%d is the maxrepeated value\n", findmaxrepeat());
freenodes();
}

WAP to Find Majority Element In Sorted Array Ofcourse It Shoud be Done in O(logn)

/* Program to check for majority element in a sorted array */
#include
# define bool int

/* If x is present in arr[low...high] then returns the index of
first occurance of x, otherwise returns -1 */
int _binarySearch(int arr[], int low, int high, int x);

/* This function returns true if the x is present more than n/2
times in arr[] of size n */
bool isMajority(int arr[], int n, int x)
{
int i = _binarySearch(arr, 0, n-1, x);
printf ( " %d ", i);

/* check if the element is present more than n/2 times */
if(((i + n/2) <= (n -1)) && arr[i + n/2] == x)
return 1;
else
return 0;
}

/* Standard Binary Search function*/
int _binarySearch(int arr[], int low, int high, int x)
{
if(high >= low)
{
int mid = (low + high)/2; /*low + (high - low)/2;*/

/* Check if arr[mid] is the first occurrence of x.
arr[mid] is first occurrence if x is one of the following
is true:
(i) mid == 0 and arr[mid] == x
(ii) arr[mid-1] < x and arr[mid] == x
*/
if(( mid == 0 || x > arr[mid-1]) && (arr[mid] == x))
return mid;
else if(x > arr[mid])
return _binarySearch(arr, (mid + 1), high, x);
else
return _binarySearch(arr, low, (mid -1), x);
}

/*Return -1 if element does not appear more than n/2 times*/
return -1;
}

/* Driver program to check above functions */
int main()
{
int arr[] = {1, 3, 3, 3,3,4,10};//sorted
int n = 7;
int x = 3;
if(isMajority(arr, n, x))
printf("%d appears more than %d times in arr[]", x, n/2);
else
printf("%d does not appear more than %d times in arr[]", x, n/2);

getchar();
return 0;
}

Time Complexity O(logn)
Space Complexity O(1)
Run Here https://ideone.com/kEdi4

WAP to Find Two elements in Array whose sum is closest to zero

Algorithm
1) Sort all the elements of the array.
2) Find the index of first positive element, this is initial value of right index r.
3) Initialize: left index l = r – 1. min_sum = INT_MIN
4) In a loop, look for the candidates by comparing sum with minimum sum. If arr[l] + arr[r] becomes negative then increment the right index r, else decrement left index l.

#include
#include
#include


void quickSort(int *, int, int);

/* Function to print pair of elements having minimum sum */
void minAbsSumPair(int arr[], int arr_size)
{
int l, r = 0, min_sum, sum = 0, min_l, min_r;

/* Array should have at least two elements*/
if(arr_size < 2)
{
printf("Invalid Input");
return;
}

/* Sort the elements */
quickSort(arr, 0, arr_size-1);

/* Find the first positive element. Note that we have condition "r < arr_size -1"
-1 is there to handle the cases when all elements are negative */
while(arr[r] < 0 && r < arr_size - 1)
r++;

/* If all elements are positive then first two elements
are the minimum sum elements */
if(r == 0)
{
printf(" The first two elements %d and %d have minimum sum",
arr[0], arr[1]);
return;
}

/* Start looking for the pair from the first positive element
and last negative element */
l = r - 1;
min_sum = arr[l] + arr[r];
min_l = l; /* min_l is for the left element of minimum sum pair*/
min_r = r; /* min_r is for the right element of minimum sum pair*/
while(l >= 0 && r < arr_size)
{
sum = arr[l] + arr[r];

/*If abs(sum) is less then update the result items*/
if(abs(sum) < abs(min_sum))
{
min_sum = sum;
min_l = l;
min_r = r;
}
if(sum < 0)
r++;
else
l--;

printf (" %d %d %d \n ",min_sum,l,r);
}

printf(" The two elements whose sum is minimum are %d and %d",
arr[min_l], arr[min_r]);
}

/* Driver program to test above function */
int main()
{
int arr[] = {1, 60, -10, 70, -80, 85};
minAbsSumPair(arr, 6);
getchar();
return 0;
}

/* FOLLOWING FUNCTIONS ARE ONLY FOR SORTING
PURPOSE */
void exchange(int *a, int *b)
{
int temp;
temp = *a;
*a = *b;
*b = temp;
}

int partition(int arr[], int si, int ei)
{
int x = arr[ei];
int i = (si - 1);
int j;

for (j = si; j <= ei - 1; j++)
{
if(arr[j] <= x)
{
i++;
exchange(&arr[i], &arr[j]);
}
}

exchange (&arr[i + 1], &arr[ei]);
return (i + 1);
}

/* Implementation of Quick Sort
arr[] --> Array to be sorted
si --> Starting index
ei --> Ending index
*/
void quickSort(int arr[], int si, int ei)
{
int pi; /* Partitioning index */
if(si < ei)
{
pi = partition(arr, si, ei);
quickSort(arr, si, pi - 1);
quickSort(arr, pi + 1, ei);
}
}

Tim Complexity O(nlogn)
Space Complexity O(1)
Run Here https://ideone.com/Y4sk0

WAP to Find Median of Two Sorted Array in O(logn) Time

There are 2 sorted arrays A and B of size n each. Write an algorithm to find the median of the array obtained after merging the above 2 arrays(i.e. array of length 2n). The complexity should be O(log(n))


Median: In probability theory and statistics, a median is described as the number separating the higher half of a sample from the lower half.
The median of a finite list of numbers can be found by arranging all the numbers from lowest value to highest value and picking the middle one.

For getting the median of input array { 12, 11, 15, 10, 20 }, first sort the array. We get { 10, 11, 12, 15, 20 } after sorting. Median is the middle element of the sorted array which is 12.

Algo 1 merge both array & return avg of a[n/2]+a[n/2-1]/2;but merging requires extra space of size O(2n)

Algo 2 Linear Time O(n)

Use merge procedure of merge sort. Keep track of count while comparing elements of two arrays. If count becomes n(For 2n elements), we have reached the median. Take the average of the elements at indexes n-1 and n in the merged array. See the below implementation.

if (i==n) base case when all elements of 1st array is less then 1st element of 2nd Array
then m1=m2;
m2=a[0];//obvious
break

if(j==n)
base case when all elements of 2nd array is less then 1st element of 1st Array
then
m1=m2;
m2=a1[0]; //obvious
& break



#include

/* This function returns median of ar1[] and ar2[].
Assumptions in this function:
Both ar1[] and ar2[] are sorted arrays
Both have n elements */
int getMedian(int ar1[], int ar2[], int n)
{
int i = 0; /* Current index of i/p array ar1[] */
int j = 0; /* Current index of i/p array ar2[] */
int count;
int m1 = -1, m2 = -1;

/* Since there are 2n elements, median will be average
of elements at index n-1 and n in the array obtained after
merging ar1 and ar2 */
for(count = 0; count <= n; count++)
{
/*Below is to handle case where all elements of ar1[] are
smaller than smallest(or first) element of ar2[]*/
if(i == n)
{
m1 = m2;
m2 = ar2[0];
break;
}

/*Below is to handle case where all elements of ar2[] are
smaller than smallest(or first) element of ar1[]*/
else if(j == n)
{
m1 = m2;
m2 = ar1[0];
break;
}

if(ar1[i] < ar2[j])
{
m1 = m2; /* Store the prev median */
m2 = ar1[i];
i++;
}
else
{
m1 = m2; /* Store the prev median */
m2 = ar2[j];
j++;
}
}

return (m1 + m2)/2;
}

/* Driver program to test above function */
int main()
{
int ar1[] = {1, 12, 15, 26, 38};
int ar2[] = {2, 13, 17, 30, 45};

printf("%d", getMedian(ar1, ar2, 5)) ;

getchar();
return 0;
}

Time Complexity O(n)
Space Complexity O(1)
Run Here https://ideone.com/er0L7

3rd Algo O(logn)

This method works by first getting medians of the two sorted arrays and then comparing them.

Let ar1 and ar2 be the input arrays.

Algorithm:

1) Calculate the medians m1 and m2 of the input arrays ar1[]
and ar2[] respectively.
2) If m1 and m2 both are equal then we are done.
return m1 (or m2)
3) If m1 is greater than m2, then median is present in one
of the below two subarrays.
a) From first element of ar1 to m1 (ar1[0...|_n/2_|])
b) From m2 to last element of ar2 (ar2[|_n/2_|...n-1])
4) If m2 is greater than m1, then median is present in one
of the below two subarrays.
a) From m1 to last element of ar1 (ar1[|_n/2_|...n-1])
b) From first element of ar2 to m2 (ar2[0...|_n/2_|])
5) Repeat the above process until size of both the subarrays
becomes 2.
6) If size of the two arrays is 2 then use below formula to get
the median.
Median = (max(ar1[0], ar2[0]) + min(ar1[1], ar2[1]))/2

Example:

ar1[] = {1, 12, 15, 26, 38}
ar2[] = {2, 13, 17, 30, 45}

For above two arrays m1 = 15 and m2 = 17

For the above ar1[] and ar2[], m1 is smaller than m2. So median is present in one of the following two subarrays.

[15, 26, 38] and [2, 13, 17]

Let us repeat the process for above two subarrays:

m1 = 26 m2 = 13.

m1 is greater than m2. So the subarrays become

[15, 26] and [13, 17]
Now size is 2, so median = (max(ar1[0], ar2[0]) + min(ar1[1], ar2[1]))/2
= (max(15, 13) + min(26, 17))/2
= (15 + 17)/2
= 16


#include

/* This function returns median of ar1[] and ar2[].
Assumptions in this function:
Both ar1[] and ar2[] are sorted arrays
Both have n elements */
int getMedian(int ar1[], int ar2[], int n)
{
int i = 0; /* Current index of i/p array ar1[] */
int j = 0; /* Current index of i/p array ar2[] */
int count;
int m1 = -1, m2 = -1;

/* Since there are 2n elements, median will be average
of elements at index n-1 and n in the array obtained after
merging ar1 and ar2 */
for(count = 0; count <= n; count++)
{
/*Below is to handle case where all elements of ar1[] are
smaller than smallest(or first) element of ar2[]*/
if(i == n)
{
m1 = m2;
m2 = ar2[0];
break;
}

/*Below is to handle case where all elements of ar2[] are
smaller than smallest(or first) element of ar1[]*/
else if(j == n)
{
m1 = m2;
m2 = ar1[0];
break;
}

if(ar1[i] < ar2[j])
{
m1 = m2; /* Store the prev median */
m2 = ar1[i];
i++;
}
else
{
m1 = m2; /* Store the prev median */
m2 = ar2[j];
j++;
}
}

return (m1 + m2)/2;
}

/* Driver program to test above function */
int main()
{
int ar1[] = {1, 12, 15, 26, 38};
int ar2[] = {2, 13, 17, 30, 45};

printf("%d", getMedian(ar1, ar2, 5)) ;

getchar();
return 0;
}


Time Complexity O(logn)
Space Complexity O(1)
Run Here https://ideone.com/ZE4Vq

Complete Reference From G4G & http://ocw.mit.edu/NR/rdonlyres/Electrical-Engineering-and-Computer-Science/6-046JFall-2005/30C68118-E436-4FE3-8C79-6BAFBB07D935/0/ps9sol.pdf

WAP to Find Median of Two Sorted Array in O(logn) Time

There are 2 sorted arrays A and B of size n each. Write an algorithm to find the median of the array obtained after merging the above 2 arrays(i.e. array of length 2n). The complexity should be O(log(n))


Median: In probability theory and statistics, a median is described as the number separating the higher half of a sample from the lower half.
The median of a finite list of numbers can be found by arranging all the numbers from lowest value to highest value and picking the middle one.

For getting the median of input array { 12, 11, 15, 10, 20 }, first sort the array. We get { 10, 11, 12, 15, 20 } after sorting. Median is the middle element of the sorted array which is 12.

Algo 1 merge both array & return avg of a[n/2]+a[n/2-1]/2;but merging requires extra space of size O(2n)

Algo 2 Linear Time O(n)

Use merge procedure of merge sort. Keep track of count while comparing elements of two arrays. If count becomes n(For 2n elements), we have reached the median. Take the average of the elements at indexes n-1 and n in the merged array. See the below implementation.

if (i==n) base case when all elements of 1st array is less then 1st element of 2nd Array
then m1=m2;
m2=a[0];//obvious
break

if(j==n)
base case when all elements of 2nd array is less then 1st element of 1st Array
then
m1=m2;
m2=a1[0]; //obvious
& break



#include

/* This function returns median of ar1[] and ar2[].
Assumptions in this function:
Both ar1[] and ar2[] are sorted arrays
Both have n elements */
int getMedian(int ar1[], int ar2[], int n)
{
int i = 0; /* Current index of i/p array ar1[] */
int j = 0; /* Current index of i/p array ar2[] */
int count;
int m1 = -1, m2 = -1;

/* Since there are 2n elements, median will be average
of elements at index n-1 and n in the array obtained after
merging ar1 and ar2 */
for(count = 0; count <= n; count++)
{
/*Below is to handle case where all elements of ar1[] are
smaller than smallest(or first) element of ar2[]*/
if(i == n)
{
m1 = m2;
m2 = ar2[0];
break;
}

/*Below is to handle case where all elements of ar2[] are
smaller than smallest(or first) element of ar1[]*/
else if(j == n)
{
m1 = m2;
m2 = ar1[0];
break;
}

if(ar1[i] < ar2[j])
{
m1 = m2; /* Store the prev median */
m2 = ar1[i];
i++;
}
else
{
m1 = m2; /* Store the prev median */
m2 = ar2[j];
j++;
}
}

return (m1 + m2)/2;
}

/* Driver program to test above function */
int main()
{
int ar1[] = {1, 12, 15, 26, 38};
int ar2[] = {2, 13, 17, 30, 45};

printf("%d", getMedian(ar1, ar2, 5)) ;

getchar();
return 0;
}

Time Complexity O(n)
Space Complexity O(1)
Run Here https://ideone.com/er0L7

3rd Algo O(logn)

This method works by first getting medians of the two sorted arrays and then comparing them.

Let ar1 and ar2 be the input arrays.

Algorithm:

1) Calculate the medians m1 and m2 of the input arrays ar1[]
and ar2[] respectively.
2) If m1 and m2 both are equal then we are done.
return m1 (or m2)
3) If m1 is greater than m2, then median is present in one
of the below two subarrays.
a) From first element of ar1 to m1 (ar1[0...|_n/2_|])
b) From m2 to last element of ar2 (ar2[|_n/2_|...n-1])
4) If m2 is greater than m1, then median is present in one
of the below two subarrays.
a) From m1 to last element of ar1 (ar1[|_n/2_|...n-1])
b) From first element of ar2 to m2 (ar2[0...|_n/2_|])
5) Repeat the above process until size of both the subarrays
becomes 2.
6) If size of the two arrays is 2 then use below formula to get
the median.
Median = (max(ar1[0], ar2[0]) + min(ar1[1], ar2[1]))/2

Example:

ar1[] = {1, 12, 15, 26, 38}
ar2[] = {2, 13, 17, 30, 45}

For above two arrays m1 = 15 and m2 = 17

For the above ar1[] and ar2[], m1 is smaller than m2. So median is present in one of the following two subarrays.

[15, 26, 38] and [2, 13, 17]

Let us repeat the process for above two subarrays:

m1 = 26 m2 = 13.

m1 is greater than m2. So the subarrays become

[15, 26] and [13, 17]
Now size is 2, so median = (max(ar1[0], ar2[0]) + min(ar1[1], ar2[1]))/2
= (max(15, 13) + min(26, 17))/2
= (15 + 17)/2
= 16




Complete Reference From http://ocw.mit.edu/NR/rdonlyres/Electrical-Engineering-and-Computer-Science/6-046JFall-2005/30C68118-E436-4FE3-8C79-6BAFBB07D935/0/ps9sol.pdf & geeksForgeeks

WAP to print 2D array matrix in Spiral Order

Question: Given a 2D array / matrix of integers. Write a program to print the elements in spiral order. Consider a matrix as show in the diagram to the right. The desired output of the program should be as: 1,2,3,4,8,12,16,20,19,18,17,13,9,5,6, 7,11,15,14,10.




Solution: There are several ways to solve this problem, but I am mentioning a method that is intuitive to understand and easy to implement. The idea is to consider the matrix similar to onion which can be peeled layer after layer. We can use the same approach to print the outer layer of the matrix and keep doing it recursively on a smaller matrix (with 1 less row and 1 less column).

Refer to the image below for a visual explanation. We start by printing the top-right layer of the matrix by calling the print_layer_top_right. It will print 1,2,3,4,8,12,16,20. The print_layer_top_right method then calls the print_layer_bottom_left method which will print 19,18,17,13,9,5. If you observe the size of the target matrix is reducing after each call. Each method basically calls the other method and passes the matrix indexes for the reduced matrix. Both methods take 4 index parameters which represent the target matrix. When the target matrix size is such that there is only one layer left the recursion terminates and by this time the code has printed all the numbers in the full matrix.




Code (C language):

<script type="syntaxhighlighter" class="brush: html"><![CDATA[

#include
void print_layer_top_right(int a[][4], int x1, int y1, int x2, int y2);
void print_layer_bottom_left(int a[][4], int x1, int y1, int x2, int y2);

int main(void)
{
int a[5][4] = {
{1,2,3,4},
{5,6,7,8},
{9,10,11,12},
{13,14,15,16},
{17,18,19,20}
};

print_layer_top_right(a,0,0,3,4);
}

//
// prints the top and right shells of the matrix
//
void print_layer_top_right(int a[][4], int x1, int y1, int x2, int y2)
{
int i = 0, j = 0;

// print the row
for(i = x1; i<=x2; i++)
{
printf("%d,", a[y1][i]);
}

//print the column
for(j = y1 + 1; j <= y2; j++)
{
printf("%d,", a[j][x2]);
}

// see if we have more cells left
if(x2-x1 > 0)
{
// 'recursively' call the function to print the bottom-left layer
print_layer_bottom_left(a, x1, y1 + 1, x2-1, y2);
}
}

//
// prints the bottom and left shells of the matrix
//
void print_layer_bottom_left(int a[][4], int x1, int y1, int x2, int y2)
{
int i = 0, j = 0;

//print the row of the matrix in reverse
for(i = x2; i>=x1; i--)
{
printf("%d,", a[y2][i]);
}

// print the last column of the matrix in reverse
for(j = y2 - 1; j >= y1; j--)
{
printf("%d,", a[j][x1]);
}

if(x2-x1 > 0)
{
// 'recursively' call the function to print the top-right layer
print_layer_top_right(a, x1+1, y1, x2, y2-1);
}
}

]]></script>

Run Here https://ideone.com/ut0Hx

WAP to Write Find MaximumSize Sub-Matrix From Given Matrxi having Size of R*C

Maximum size square sub-matrix with all 1s
April 4, 2010

Given a binary matrix, find out the maximum size square sub-matrix with all 1s.

For example, consider the below binary matrix.

0 1 1 0 1
1 1 0 1 0
0 1 1 1 0
1 1 1 1 0
1 1 1 1 1
0 0 0 0 0

The maximum square sub-matrix with all set bits is

1 1 1
1 1 1
1 1 1

Algorithm:
Let the given binary matrix be M[R][C]. The idea of the algorithm is to construct an auxiliary size matrix S[][] in which each entry S[i][j] represents size of the square sub-matrix with all 1s including M[i][j] and M[i][j] is the rightmost and bottommost entry in sub-matrix.

1) Construct a sum matrix S[R][C] for the given M[R][C].
a) Copy first row and first columns as it is from M[][] to S[][]
b) For other entries, use following expressions to construct S[][]
If M[i][j] is 1 then
S[i][j] = min(S[i][j-1], S[i-1][j], S[i-1][j-1]) + 1
Else /*If M[i][j] is 0*/
S[i][j] = 0
2) Find the maximum entry in S[R][C]
3) Using the value and coordinates of maximum entry in S[i], print
sub-matrix of M[][]

For the given M[R][C] in above example, constructed S[R][C] would be:

0 1 1 0 1
1 1 0 1 0
0 1 1 1 0
1 1 2 2 0
1 2 2 3 1
0 0 0 0 0

The value of maximum entry in above matrix is 3 and coordinates of the entry are (4, 3). Using the maximum value and its coordinates, we can find out the required sub-matrix.


C program

#include
#define bool int
#define R 6
#define C 5

/* UTILITY FUNCTIONS */
/* Function to get minimum of three values */

int min(int a, int b, int c)
{
int m = a;
if (m > b)
m = b;
if (m > c)
m = c;
return m;
}

void printMaxSubSquare(bool M[R][C])
{
int i,j;
int S[R][C];
int max_of_s, max_i, max_j;

/* Set first column of S[][]*/
for(i = 0; i < R; i++)
S[i][0] = M[i][0];

/* Set first row of S[][]*/
for(j = 0; j < C; j++)
S[0][j] = M[0][j];

/* Construct other entries of S[][]*/
for(i = 1; i < R; i++)
{
for(j = 1; j < C; j++)
{
if(M[i][j] == 1)
S[i][j] = min(S[i][j-1], S[i-1][j], S[i-1][j-1]) + 1;
else
S[i][j] = 0;
}
}

/* Find the maximum entry, and indexes of maximum entry
in S[][] */
max_of_s = S[0][0]; max_i = 0; max_j = 0;
for(i = 0; i < R; i++)
{
for(j = 0; j < C; j++)
{
if(max_of_s < S[i][j])
{
max_of_s = S[i][j];
max_i = i;
max_j = j;
}
}
}

printf("\n Maximum size sub-matrix is: \n");
for(i = max_i; i > max_i - max_of_s; i--)
{
for(j = max_j; j > max_j - max_of_s; j--)
{
printf("%d ", M[i][j]);
}
printf("\n");
}
}



/* Driver function to test above functions */
int main()
{
bool M[R][C] = {{0, 1, 1, 0, 1},
{1, 1, 0, 1, 0},
{0, 1, 1, 1, 0},
{1, 1, 1, 1, 0},
{1, 1, 1, 1, 1},
{0, 0, 0, 0, 0}};

printMaxSubSquare(M);
getchar();
}

Run Here https://ideone.com/oFXO6

WAP for Given a binary tree, write a program to find the cousin nodes of the given node.

//find the level and print the cousins
#include
#include

using namespace std;

struct node{
struct node* left;
struct node* right;
int data;
};

void inorder(struct node* root,int present_level,int level,struct node* parent)
{
if(root!=NULL)
{
if(parent!=root)
inorder(root->left,present_level+1,level,parent);
if(level==present_level)
cout<data<<" ";
if(parent!=root)
inorder(root->right,present_level+1,level,parent);
}

}

void make_tree(struct node **root,int data)
{
if((*root)==NULL)
{
(*root)=new node;
(*root)->left=NULL;
(*root)->right=NULL;
(*root)->data=data;
return;
}
else
{
if(((*root)->data)make_tree(&((*root)->right),data);
else
make_tree(&((*root)->left),data);
}


}

struct node* find_level_and_parent(struct node* root,int data,int* level)
{
struct node* parent=NULL;
struct node* child=root;

while(1)
{

if(child==NULL)
return NULL;
if(child->data==data)
{
return parent;

}
if(data>child->data)
{
parent=child;
child=child->right;
*level=*level+1;

}
else if(data<=child->data)
{
parent=child;
child=child->left;
*level=*level+1;
}


}

}

int main()
{
struct node* root=NULL;
make_tree(&root,6);
make_tree(&root,8);
make_tree(&root,3);
make_tree(&root,4);
make_tree(&root,44);
make_tree(&root,34);
make_tree(&root,12);
make_tree(&root,8);
make_tree(&root,2);
make_tree(&root,1);
make_tree(&root,33);

int level=0;
struct node* temp=find_level_and_parent(root,12,&level);
if(temp!=NULL)
{
cout<<"Level="<return 0;
}

Solution Provide By Ankit From CareerCup
Run Here https://ideone.com/ybavU

WAP to Populate The next Higher in Singly Linked List

struct node
{
int data;
struct node *next;
struct node *next_larger;
}

initially next_larger of every node is point to NULL.
now write a c code which set all node's next_larger pointer.
where next_largest point to the next larger then its own value and largest value node's next_larger pointer points to NULL

i.e.
if LL is 3->1->5->6->4
then 3's next_larger points to 4
and 1's next_larger points to 3
and 5's next_larger points to 6
and 6's next_larger points to NULL
and 4's next_larger points to 5

#include
#include


struct node
{

int data;
struct node *next;
struct node *next_higher;

};

struct node* setNextHigher(struct node** head)
{
if(head==NULL)
return NULL;

struct node *start=*head;

(*head)=(*head)->next;

while((*head))
{

if((*head)->datadata)
{

(*head)->next_higher=start;
start= (*head);

}
else
{
struct node *p=start;
while(p->next_higher&&(*head)->data>=p->next_higher->data)
p=p->next_higher;

(*head)->next_higher=p->next_higher;
p->next_higher=(*head);

}
(*head)= (*head)->next;
}

return start;
}

void push(struct node** head_ref, int new_data)
{
/* allocate node */
struct node* new_node =
(struct node*) malloc(sizeof(struct node));

/* put in the data */
new_node->data = new_data;

/* link the old list off the new node */
new_node->next = (*head_ref);

/* move the head to point to the new node */
(*head_ref) = new_node;
}

/* Function to print linked list */
void printList(struct node *node)
{
while(node != NULL)
{
printf("%d ", node->data);
node = node->next_higher;
}
}

int main()
{
/* Start with the empty list */
struct node* head = NULL;

push(&head, 4);
push(&head, 6);
push(&head, 5);
push(&head, 1);
push(&head, 3);

head=setNextHigher(&head);

printList(head);

getchar();
}


Run Here https://ideone.com/fARV8