Game of Master Mind !!!!!!!!!!!!!!

Game of master mind: you have four balls, and four different colors, as a
solution. The user tries to guess the solution. If they guess the right
color for the right spot, it counts as a 'hit'. If it's the right color, but
the wrong spot, it counts as a psuedo-hit. For example: if the solution is
'RGGB' and the user guesses 'YRGB' they have 2 hits and one pseudo hit.
Write a program to, given a solution and a guess, calculate the number of
hits and pseudo hits.

Data Structure Used: Array

Algorithm:
1.Take an temp array of length ascii chars(256) , although we need array of length of 4 here
taking above array will give advantage so that we set/reset the 1 or 0 at particular character
position according to their ascii value.
2.scan solution & guess string & set value to 1 in temp array for each matching character of
solution & guess string also increment the hits counter.else increment temp array location of
corresponding character location.
3.in 2nd pass over temp array check for each location if that location value is not equal to 1 &
also temp[location]>0 if yes then increment pseudo-counter & decrement corresponding character
count in temp array.

Above algorithm will take O(N) time & constant space with two passes over three arrays.1 pass over solution & guess string
2nd pas over temp string



Time Complexity O(N)
Space Complexity O(1)
Run Here

WAP to Delete a Character before the Given Index in Character Array (You Have Given Array of Ascii & kanji Characters)

First some definitions for this problem: a) An ASCII character is one byte long and the most significant bit in the byte is always '0'. b) A Kanji character is two bytes long. The only characteristic of a Kanji character is that in its first byte the most significant bit is '1'.

Now you are given an array of a characters (both ASCII and Kanji) and, an index into the array. The index points to the start of some character. Now you need to write a function to do a backspace (i.e. delete the character before the given index).

We have to write an algorithm & a quality working code for this.


Explanation

1. Look at MSB of the previous character. If 1, then delete the previous two bytes. This is because an MSB of 1 can only be part of a Kanjii character.
2. If the MSB is 0 then all you know is that the previous byte ENDs a character. The previous byte could be an Ascii character, the single byte is the start and the end of the character OR the previous byte is the second byte of a Kanjii character. Look the following figures which show the characters to the left the given character, denoted by ‘|’.

xxx10|xxxxx. You cannot decide on the previous character based on the scan so far because there are two possibilities after this
1. xx010|xxxxx - The previous character is a Kanjii character. After first 0 from left we are left with ‘10’ which is Kanjii.
2. xx110|xxxxx - We have to scan even further. Leads to two choices
x1110|xxxxx - We have to scan even further.
x0110|xxxxx - after leftmost 0, we have ‘110’ which break into ‘11’ and ‘0’. So the previous character is Ascii.

Continuing on this logic you will notice that you have to first find the end byte of a previous character and the only way to do that is to find the previous ‘0’ OR start of the file. After you have found the previous end byte of a character, you count the number of ‘1’ in between the 0 before the cursor and the previous end byte.
1. If number of ‘1’s is even then the previous character is Ascii so the backspace should delete one byte.
2. If the number of ‘1’s is odd then the previous character is Kanjii and two bytes should be deleted.


Data Structure Used: Array

Algorithm

Working Code(In progress)


Time Complexity
Space Complexity
Run Here

WAP Check Endianess of Machine & Converting From One Endians To Other

First of all, Do you know what Little-Endian and Big-Endian mean? Little Endian means that the lower order byte of the number is stored in memory at the lowest address, and the higher order byte is stored at the highest address. That is, the little end comes first.
This Question Is Frequently Asked in Top Core Companies Interviews so you need to aware of Computer System Architecture

For example, a 4 byte, 32-bit integer
Byte3 Byte2 Byte1 Byte0
will be arranged in memory as follows:

Base_Address+0 Byte0
Base_Address+1 Byte1
Base_Address+2 Byte2
Base_Address+3 Byte3
Intel processors use “Little Endian” byte order.

“Big Endian” means that the higher order byte of the number is stored in memory at the lowest address, and the lower order byte at the highest address. The big end comes first.

Base_Address+0 Byte3
Base_Address+1 Byte2
Base_Address+2 Byte1
Base_Address+3 Byte0
Motorola, Solaris processors use “Big Endian” byte order.

In “Little Endian” form, code which picks up a 1, 2, 4, or longer byte number proceed in the same way for all formats. They first pick up the lowest order byte at offset 0 and proceed from there. Also, because of the 1:1 relationship between address offset and byte number (offset 0 is byte 0), multiple precision mathematic routines are easy to code. In “Big Endian” form, since the high-order byte comes first, the code can test whether the number is positive or negative by looking at the byte at offset zero. Its not required to know how long the number is, nor does the code have to skip over any bytes to find the byte containing the sign information. The numbers are also stored in the order in which they are printed out, so binary to decimal routines are particularly efficient.
Here is some code to determine what is the type of your machine

int num = 1;
if(*(char *)&num == 1)
{
printf("\nLittle-Endian\n");
}
else
{
printf("Big-Endian\n");
}

And here is some code to convert from one Endian to another.

int myreversefunc(int num)
{
int byte0, byte1, byte2, byte3;
byte0 = (num & x000000FF) >> 0 ;
byte1 = (num & x0000FF00) >> 8 ;
byte2 = (num & x00FF0000) >> 16 ;
byte3 = (num & xFF000000) >> 24 ;
return((byte0 << 24) | (byte1 << 16) | (byte2 << 8) | (byte3 << 0));
}

WAP to Find Maximum and minimum of an array using minimum number of comparisons

Write a C function to return minimum and maximum in an array. You program should make minimum number of comparisons.

First of all, how do we return multiple values from a C function? We can do it either using structures or pointers.

We have created a structure named pair (which contains min and max) to return multiple values.

?
struct pair
{
int min;
int max;
};
And the function declaration becomes: struct pair getMinMax(int arr[], int n) where arr[] is the array of size n whose minimum and maximum are needed.


Method 1

Initialize values of min and max as minimum and maximum of the first two elements respectively. Starting from 3rd, compare each element with max and min, and change max and min accordingly (i.e., if the element is smaller than min then change min, else if the element is greater than max then change max, else ignore the element)

/* structure is used to return two values from minMax() */
#include
struct pair
{
int min;
int max;
};

struct pair getMinMax(int arr[], int n)
{
struct pair minmax;
int i;

/*If there is only one element then return it as min and max both*/
if(n == 1)
{
minmax.max = arr[0];
minmax.min = arr[0];
return minmax;
}

/* If there are more than one elements, then initialize min
and max*/
if(arr[0] > arr[1])
{
minmax.max = arr[0];
minmax.min = arr[1];
}
else
{
minmax.max = arr[0];
minmax.min = arr[1];
}

for(i = 2; i {
if(arr[i] > minmax.max)
minmax.max = arr[i];

else if(arr[i] < minmax.min)
minmax.min = arr[i];
}

return minmax;
}

/* Driver program to test above function */
int main()
{
int arr[] = {1000, 11, 445, 1, 330, 3000};
int arr_size = 6;
struct pair minmax = getMinMax (arr, arr_size);
printf("\nMinimum element is %d", minmax.min);
printf("\nMaximum element is %d", minmax.max);
getchar();
}

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

In this method, total number of comparisons is 1 + 2(n-2) in worst case and 1 + n – 2 in best case.
In the above implementation, worst case occurs when elements are sorted in descending order and best case occurs when elements are sorted in ascending order.



METHOD 2 (Tournament Method) (Efficient)

Divide the array into two parts and compare the maximums and minimums of the the two parts to get the maximum and the minimum of the the whole array.

Pair MaxMin(array, array_size)
if array_size = 1
return element as both max and min
else if arry_size = 2
one comparison to determine max and min
return that pair
else /* array_size > 2 */
recur for max and min of left half
recur for max and min of right half
one comparison determines true max of the two candidates
one comparison determines true min of the two candidates
return the pair of max and min
Implementation

/* structure is used to return two values from minMax() */
#include
struct pair
{
int min;
int max;
};

struct pair getMinMax(int arr[], int low, int high)
{
struct pair minmax, mml, mmr;
int mid;

/* If there is only on element */
if(low == high)
{
minmax.max = arr[low];
minmax.min = arr[low];
return minmax;
}

/* If there are two elements */
if(high == low + 1)
{
if(arr[low] > arr[high])
{
minmax.max = arr[low];
minmax.min = arr[high];
}
else
{
minmax.max = arr[high];
minmax.min = arr[low];
}
return minmax;
}

/* If there are more than 2 elements */
mid = (low + high)/2;
mml = getMinMax(arr, low, mid);
mmr = getMinMax(arr, mid+1, high);

/* compare minimums of two parts*/
if(mml.min < mmr.min)
minmax.min = mml.min;
else
minmax.min = mmr.min;

/* compare maximums of two parts*/
if(mml.max > mmr.max)
minmax.max = mml.max;
else
minmax.max = mmr.max;

return minmax;
}

/* Driver program to test above function */
int main()
{
int arr[] = {1000, 11, 445, 1, 330, 3000};
int arr_size = 6;
struct pair minmax = getMinMax(arr, 0, arr_size-1);
printf("\nMinimum element is %d", minmax.min);
printf("\nMaximum element is %d", minmax.max);
getchar();
}

Number of Instruction Executed less
Time Complexity: O(n)
Space Complexity
Run Here https://ideone.com/jB3tu

Total number of comparisons: let number of comparisons be T(n). T(n) can be written as follows:
Algorithmic Paradigm: Divide and Conquer

T(n) = T(floor(n/2)) + T(ceil(n/2)) + 2
T(2) = 1
T(1) = 0
If n is a power of 2, then we can write T(n) as:

T(n) = 2T(n/2) + 2
After solving above recursion, we get

T(n) = 3/2n -2
Thus, the approach does 3/2n -2 comparisons if n is a power of 2. And it does more than 3/2n -2 comparisons if n is not a power of 2.

WAP to Find Square root of Perfect Square Number Efficiently Yes in O(logn)

As its a perfect square!! So arrange numbers from 1 to n/2 and do a binary search..
ie for i from 1 to n/2

Now compare mind*mid to n

if mid*midrecursively check right half
else
recursively check left half

#include

int sqrtof_perfect(int start,int end,int n)
{
if(start>end)
return 0;
while(start<=end)
{
int mid=(start+end)/2;
//int temp=mid*mid;
if(mid*mid==n)
return mid;
else if(mid*mid>n)
end=mid-1;
else
start=mid+1;

}
return -1;
}


int main()
{
int n=144;//9;//25; // so

printf("\n %d",sqrtof_perfect(1,n/2,n));
getchar();
return 0;
}


TC O(logn)
Sc O(1)

WAP to Calculate The Power x^n Efficiently in O(logn)

Method 1 Using Iterative Method

#include
main()
{
int num, p , result;
printf("Enter the number : ");
scanf("%d",&num);
printf("\nAnd its power also. : ");
scanf("%d",&p);

result = power(num,p);
printf("\nThe result is %d\n", result);
}
power(int x, int y)
{
int i,temp =1;
if(y==0)
return(1);
if(y==1)
return(x);
else
{
for(i=1;i<=y;i++)
temp = temp*x;
return(temp);
}
}

Method 2 Using Recursion

Below solution divides the problem into subproblems of size y/2 and call the subproblems recursively.


#include

/* Function to calculate x raised to the power y */
int power(int x, unsigned int y)
{
if( y == 0)
return 1;
else if (y%2 == 0)
return power(x, y/2)*power(x, y/2);
else
return x*power(x, y/2)*power(x, y/2);

}

/* Program to test function power */
int main()
{
int x = 2;
unsigned int y = 3;

printf("%d", power(x, y));
getchar();
return 0;
}

Time Complexity: O(n)
Space Complexity: O(1)
Algorithmic Paradigm: Divide and conquer.

Method 3 Reducing Instruction to Nearly Half

Above function can be optimized to O(logn) by calculating power(x, y/2) only once and storing it.

/* Function to calculate x raised to the power y in O(logn)*/
int power(int x, unsigned int y)
{
int temp;
if( y == 0)
return 1;
temp = power(x, y/2);
if (y%2 == 0)
return temp*temp;
else
return x*temp*temp;
}

Time Complexity of optimized solution: O(logn)

Method 4 case handled for -Ive Number

Let me extend the pow function to work for negative y and float x.

/* Extended version of power function that can work
for float x and negative y*/
#include

float power(float x, int y)
{
float temp;
if( y == 0)
return 1;
temp = power(x, y/2);
if (y%2 == 0)
return temp*temp;
else
{
if(y > 0)
return x*temp*temp;
else
return (temp*temp)/x;
}
}

/* Program to test function power */
int main()
{
float x = 2;
int y = -3;
printf("%f", power(x, y));
getchar();
return 0;
}

Method 5 Power calculation Using + and - Operator Only

#include



/* assumption: y is greater than or equal to 0*/
int multiply(int x, int y)
{
if(y)
return (x + multiply(x, y-1));
return 0;
}
/* assumption: b is greater than or equal to 0*/
int pow(int a, int b)
{
if(b)
return multiply(a, pow(a, b-1));
return 1;
}
int main()
{
printf("\n %d", pow(3, 2));
getchar();
return 0;
}


Time Complexity O(n)
Space Complexity O(n) if Stack Space else O(1)

Run Here https://ideone.com/BBdU1

How to find if a node/pointer corrupted in a linked list

How would you find out if one of the pointers in a linked list is corrupted or not?
This is a really good interview question. The reason is that linked lists are used in a wide variety of scenarios and being able to detect and correct pointer corruptions might be a very valuable tool. For example, data blocks associated with files in a file system are usually stored as linked lists. Each data block points to the next data block. A single corrupt pointer can cause the entire file to be lost!

1 Discover & Fix Bugs
Discover and fix bugs when they corrupt the linked list and not when effect becomes visible in some other part of the program. Perform frequent consistency checks (to see if the linked list is indeed holding the data that you inserted into it).

2 set Pointer to NUll after Freeing Object
It is good programming practice to set the pointer value to NULL immediately after freeing the memory pointed at by the pointer. This will help in debugging, because it will tell you that the object was freed somewhere beforehand. Keep track of how many objects are pointing to a object using reference counts if required.

3 Use Debugger Tool Like DDD,Purify,
Use a good debugger to see how the datastructures are getting corrupted and trace down the problem. Debuggers like ddd on linux and memory profilers like Purify, Electric fence are good starting points. These tools should help you track down heap corruption issues easily.

4.Avoid Global Variable
Avoid global variables when traversing and manipulating linked lists. Imagine what would happen if a function which is only supposed to traverse a linked list using a global head pointer accidently sets the head pointer to NULL!.

5 Check Add& Delete Node After such Opeartion
Its a good idea to check the addNode() and the deleteNode() routines and test them for all types of scenarios. This should include tests for inserting/deleting nodes at the front/middle/end of the linked list, working with an empty linked list, running out of memory when using malloc() when allocating memory for new nodes, writing through NULL pointers, writing more data into the node fields then they can hold (resulting in corrupting the (probably adjacent) “prev” and “next” pointer fields), make sure bug fixes and enhancements to the linked list code are reviewed and well tested (a lot of bugs come from quick and dirty bug fixing), log and handle all possible errors (this will help you a lot while debugging), add multiple levels of logging so that you can dig through the logs. The list is endless…

6.Keep Track of Number of Nodes After Every Node after Initializing Linked List
Each node can have an extra field associated with it. This field indicates the number of nodes after this node in the linked list. This extra field needs to be kept up-to-date when we inserte or delete nodes in the linked list (It might become slightly complicated when insertion or deletion happens not at end, but anywhere in the linked list). Then, if for any node, p->field > 0 and p->next == NULL, it surely points to a pointer corruption.
You could also keep the count of the total number of nodes in a linked list and use it to check if the list is indeed having those many nodes or not.

The problem in detecting such pointer corruptions in C is that its only the programmer who knows that the pointer is corrupted. The program has no way of knowing that something is wrong. So the best way to fix these errors is check your logic and test your code to the maximum possible extent. I am not aware of ways in C to recover the lost nodes of a corrupted linked list. C does not track pointers so there is no good way to know if an arbitrary pointer has been corrupted or not. The platform may have a library service that checks if a pointer points to valid memory (for instance on Win32 there is a IsBadReadPtr, IsBadWritePtr API.) If you detect a cycle in the link list, it’s definitely bad. If it’s a doubly linked list you can verify, pNode->Next->Prev == pNode.

I have a hunch that interviewers who ask this question are probably hinting at something called Smart Pointers in C++. Smart pointers are particularly useful in the face of exceptions as they ensure proper destruction of dynamically allocated objects. They can also be used to keep track of dynamically allocated objects shared by multiple owners. This topic is out of scope here, but you can find lots of material on the Internet for Smart Pointers.

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 to Implement The Counting Sort Pure O(n)

#include
#include

void counting_sort(int array[], int size)
{
int i, min, max;

min = max = array[0];
for(i = 1; i < size; i++)
{
if (array[i] < min)
min = array[i];
else if (array[i] > max)
max = array[i];
}

int range = max - min + 1;
int *count =(int*)malloc(range * sizeof(int));

for(i = 0; i < range; i++)
count[i] = 0;

for(i = 0; i < size; i++)
count[ array[i] - min ]++;
int j, z = 0;
for(i = min; i <= max; i++)
for(j = 0; j < count[ i - min ]; j++)
array[z++] = i;

free(count);
}

/* Explaination
// CountingSort.
//
// The data to be sorted is in array A with
// subscripts 0..n-1. For example,
//
// subscript: 0 1 2 3 4 5 6 7 8
// A = [ 2, 0, 4, 1, 4, 2, 2, 1, 0 ]
//
// The data values range from 0 to MAX (=4).
// A second array B will hold the sorted data.
//
// Initialize a "counting array" C:
// ---------------------------------------------

for (i = 0; i <= MAX; i++)
C[i] = 0;

// ---------------------------------------------
// Count how often each value occurs in A:
// ---------------------------------------------

for (i = 0; i < n; i++)
C[A[i]]++;

// ---------------------------------------------
// At this point C[i] contains the number
// of occurrences of the value i in A. In
// the example:
//
// 0 1 2 3 4
// C = [ 2, 2, 3, 0, 2 ]
//
// Make C[i] contain the number of
// occurrences of values 0..i in A:
// ---------------------------------------------

for (i = 1; i <= MAX; i++)
C[i] += C[i-1];

// ---------------------------------------------
// In the example:
//
// 0 1 2 3 4
// C = [ 2, 4, 7, 7, 9 ]
//
// Note that now C[i] is such that in the sorted
// array, the last occurrence of value i will be
// just before position C[i] (e.g., the last 2 in
// the sorted array B will be just before position
// C[2]=7).
//
// Move values from A to B, using C to know
// where to put them:
// ---------------------------------------------

for (i = n-1; i >= 0; i--)
B[--C[A[i]]] = A[i];

// ---------------------------------------------
// Now B looks like
//
// 0 1 2 3 4 5 6 7 8
// B = [ 0, 0, 1, 1, 2, 2, 2, 4, 4 ]
//
// Not that it matters, but now C[i] contains the
// subscript of the first occurrence of value i
// in the sorted array B:
//
// 0 1 2 3 4
// C = [ 0, 2, 4, 7, 7 ]
//
*/
void counting_sort_n(int A[],int n)
{

int i, min, MAX;

min = MAX= A[0];
for(i = 1; i < n; i++)
{
if (A[i] < min)
min = A[i];
else if (A[i] > MAX)
MAX= A[i];
}

int range = MAX- min + 1;
int *C =(int*)malloc(range * sizeof(int));
int *B=(int*)malloc(range * sizeof(int));
for (i = 0; i <= MAX; i++)
C[i] = 0;

for (i = 0; i < n; i++)
C[A[i]]++;

for (i = 1; i <= MAX; i++)
C[i] += C[i-1];

for (i = n-1; i >= 0; i--)
B[--C[A[i]]] = A[i];

for(i=0;i<9;i++)
printf( "%d ", B[i]);

}
int main()
{
int a[]={5,1,2,4,3};

//1st Method
counting_sort(a,5);

int i=0;
printf( "\n");
for(i=0;i<5;i++)
printf( "%d ", a[i]);

//2nd Method

int b[]={ 2, 0, 4, 1, 4, 2, 2, 1, 0};
counting_sort_n(b,9);



return 0;

}

Run here https://ideone.com/kLlEa

WAP Create a singly linked list of Leaf nodes from a binary tree

include

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

};


void LeafLinked(struct node *t, struct node **prevLeaf, struct node **head)
{
if(t)
{

if(t->left == NULL && t->right == NULL)
{ //leaf

if(*head == NULL)
*head = t;

else if(*prevLeaf)
(*prevLeaf)->next = t;

*prevLeaf = t;
}
else { //at least one child
LeafLinked(t->left, prevLeaf, head);
LeafLinked(t->right, prevLeaf, head);
}
}
}


/*Utilities*/

struct node* newNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;

return(node);
}

inline void printList(struct node *t)
{
while(t)
{
printf("%d ", t->data);
t = t->next;
}
printf("\n");
}

int main()
{
/*level 0*/
struct node *t = newNode(10);

/*level 1*/
t->left = newNode(20);
t->right = newNode(30);


/*level 2*/
t->left->left = newNode(40);
t->left->right = newNode(70);
t->right->left = newNode(50);
t->right->right = newNode(60);

/*level 3*/
t->left->left->left = newNode(70);
t->right->right->left = newNode(60);
t->right->right->right = newNode(160);

/*Empty List head*/
struct node *head = NULL, *prevLeaf = NULL;

/*Convert tree to list*/
LeafLinked(t, &prevLeaf, &head);

/*print list*/
printList(head);


return 0;
}

Rune Here https://ideone.com/UOakN

Project Euler Problem 67-Finding Maximum Sum in Triangle

By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.

3
7 4
2 4 6
8 5 9 3

That is, 3 + 7 + 4 + 9 = 23.

Find the maximum total from top to bottom in triangle.txt (right click and 'Save Link/Target As...'), a 15K text file containing a triangle with one-hundred rows.

NOTE: This is a much more difficult version of Problem 18. It is not possible to try every route to solve this problem, as there are 299 altogether! If you could check one trillion (1012) routes every second it would take over twenty billion years to check them all. There is an efficient algorithm to solve it. ;o)




The 18th and the 67th problems in Project Euler are one and the same. The only difference is in the input test case. The problem 18 has a smaller input and 67 has a large input. For the explanation purpose, I’ll consider problem 18. The code without any modification can be extended to 67th problem.

Given a triangle of numbers, the objective is to determine the maximum sum along paths descending from the apex of the triangle to the base. Consider the example:

3

7 4

2 4 6

8 5 9 3

The maximum sum occurs along the path 3-7-4-9.

The problem required us to determine the maximum sum for any given triangle. Also an interesting thing is mentioned about the problem, in case you were considering a brute force method of checking every path:

It is not possible to try every route to solve this problem (where the base of the triangle has 100 numbers), as there are 2^(99) altogether! If you could check one trillion (10^(12)) routes every second it would take over twenty billion years to check them all. There is an efficient algorithm to solve it. ;o)

Being forewarned, I never once gave a thought to the brute force solution.

This problem was not as tricky as they tried to sound it. The solution is quite easy to see. I’ll run you through the idea as it formed in my mind. I used the top-to-bottom approach for forming the idea and coming up with the solution, and then implemented the solution in bottom-to-top sweep. I hope you have realized that a greedy solution will not work here.

Consider the triangle given above. I’ll work out the maximum path for it from top to bottom. We start with 3. We may choose either 7 or 4. To help make this choice, consider the two triangles with apex 7 and the other with 4. So we have two smaller triangles of height 3 each. Say the maximum length for the triangle with apex 7 is x and with apex 4 is y. If x > y, we choose 7 as the next on the path, else 4.

Thus, at every step we form two triangle of height 1 smaller, and choose the apex which has the larger sum. Implemented as it is will give us the recursive solution. To get an iterative solution to this problem, one could traverse from bottom-to-top. The bottom-to-top approach is also simple. It is greedy in approach.

Consider the penultimate row, specifically the triangle with 2 as apex and 8, 5 as the base. The maximum sum in this triangle is 2+8 = 10. Replace 2 with 10. Do the same for all the triangles formed with the penultimate layer as the apex. Thus our triangle reduces to

3

7 4

10 13 15

You know what to do next. Keep applying the same till the apex of the original triangle has the maximum sum.

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;

public class Problem_18 {
private static int heightOfTree = 100;
private final String fileName = "problem_67.in";
private int[][] tree;

public int maxValue() throws IOException {
readTree();

for (int i = Problem_18.heightOfTree - 2; i >= 0; i--)
for (int j = 0; j <= i; j++)
tree[i][j] += tree[i + 1][j] > tree[i + 1][j + 1] ? tree[i + 1][j] : tree[i + 1][j + 1];

return tree[0][0];
}

private void readTree() throws IOException {
tree = new int[Problem_18.heightOfTree][];

BufferedReader bufferedReader = new BufferedReader(new FileReader(fileName));
for (int i = 0; i < Problem_18.heightOfTree; i++) {
tree[i] = new int[i + 1];
String[] values = bufferedReader.readLine().split(" ");
for (int j = 0; j <= i; j++)
tree[i][j] = Integer.parseInt(values[j]);
}
}

public static void main(String[] args) throws IOException {
System.out.println(new Problem_18().maxValue());
}
}

WAP to Calculate The Next Palindrom of Given Number Need not to be a Palindrome

#include
#include
#include

using namespace std;

//result = s + 1
void SumOne (string &s, string &result)
{
int sum, carry = 1;
for (string::reverse_iterator p = s.rbegin(); p != s.rend(); p++)
{
sum = carry + (*p - '0') ;
carry = sum / 10;
result.push_back ('0' + sum%10 );
}
if (carry) result.push_back ('1') ;
reverse (result.begin(), result.end() );
}

int main()
{

string number, left, right, revLeft ;
int tcase=0;
cin >>tcase;

int i=0;

for(i=0;i {

cin >> number ;
int n = number.size();

left = n/2 > 0 ? number.substr (0, n/2) : "0" ;
right = n/2 > 0 ? number.substr ((n+1)/2, n/2): "0" ;

revLeft = left;
reverse (revLeft.begin(), revLeft.end() );

if ( revLeft.compare (right) > 0 )
{
number.replace ((n+1)/2, n/2, revLeft );
}
else
{
if ( number[(n-1)/2] != '9' )
{
number[(n-1)/2]++; //for number of even digits this modifies "left"
revLeft = number.substr (0, n/2) ;
reverse (revLeft.begin(), revLeft.end() );
number.replace ((n+1)/2, n/2, revLeft);
}
else
{
string nextSum ;
SumOne ( left, nextSum);

if ( nextSum.size() > left.size() ) { //for special pattern: "99999" or "999999"
number = "11";
number.insert (1, n-1, '0');
}
else {
if ( n % 2 ) number [(n-1)/2] = '0'; //for number like 52960
number.replace (0, nextSum.size(), nextSum);
reverse (nextSum.begin(), nextSum.end());
number.replace ( (n+1)/2, nextSum.size(), nextSum );
}
}
}

cout << number << endl;

}

return 0;
}

TC O(n)
Sc O(1)
Run Here http://ideone.com/sOkFE

WAP to Generate Unique Combination from Given Set ot String

What is combination and how is it different from a permutation?

The mathematics' gurus would know this by heart, but I am going to refer to the Wikipedia for a proper definition.

"A combination is an un-ordered collection of unique sizes. (An ordered collection is called a permutation.)" from the Wikipedia article.

For example,

For a given String "ABCD",
a combination of un-ordered collection of unique sizes will be
[ABCD, BCD, ABD, ABC, ACD, AC, AD, AB, BC, BD, CD, D, A, B, C]

From my quick Google search, I also found out

"Number of ways of selecting zero or more things from ‘n’ different things is given by:- ( 2 ^ n - 1 ) "(from this article).

If we apply this formula in the above example, String "ABCD" with length of 4 should have ( 2 * 2 * 2 * 2 ) - 1 = 15 combinations.

This is exaclty what we are going to acheive in our code - Finding all possible combinations of characters from a given String. Note that for simplicity, we are going to assume that the input String (whose different combinations are going to be found) would not have any repetitive characters in it.
What is recursive programming?

Lets get a formal definition from Wikipedia:

"Creating a recursive procedure essentially requires defining a "base case", and then defining rules to break down more complex cases into the base case. Key to a recursive procedure is that with each recursive call, the problem domain must be reduced in such a way that eventually the base case is arrived at."

In very simple terms, a method calling itself again and again until a particular condition is met is called recursive programming.
Implementation:

The algorithm discussed below to solve this problem is chosen for its simplicity and ease of understanding. It may not be the most effective algorithm but it definitely solves this particular problem and is extremely simple.

Some points to note about this problem.

1. The given String itself is one of the combinations. For example, one of the combinations of the String "ABCD" is "ABCD" itself.

2. Every character in the String will be a combination. For example, for the String "ABCD" -- > "A", "B", "C", "D" will be some of the combinations.
Algorithm

To find the combinations of a String:

Step 1: Add the String to the combination results.
Step 2: If the String has just one character in it,
then stop the current line of execution.
Step 3: Create new sub-words from the String by removing one letter at a time.
If the String is "ABCD", form sub-words like "BCD", "ACD", "ABD", "ABC"
Step 4: For each of the sub-word, go to Step 1


import java.io.IOException;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

class StringCombinations
{
private Set combinations = new HashSet();

public StringCombinations(String sInputString)
{
generate(sInputString);
System.out.println("*** Generated " + combinations .size() + " combinations ***");
System.out.println(combinations);

}

public void generate(String word)
{
// Add this word to our combination results set
// System.out.println(word);
combinations.add(word);

// If the word has only one character we break the
// recursion
if (word.length() == 1)
{
combinations.add(word);
return;
}

// Go through every position of the word
for (int i = 0; i < word.length(); i++)
{
// Remove the character at the current position
// all call this method with that String (Recursion!)
generate(word.substring(0,i) + word.substring(i+1));
}
}

public static String readCommandLineInput(String inputMessage)
{

String inputLine ="abcd";
return inputLine;
}

public static void main(String args[])
{
// Request and read user input
String sInstruction = "Enter a String: \n";
String sInputString = readCommandLineInput(sInstruction);
new StringCombinations(sInputString);
}

}// End of StringCombinations

Run Here https://ideone.com/EPV9i

Another Informative Link http://www.codeguru.com/cpp/cpp/algorithms/combinations/article.php/c5117

WAP to Remove The Node From Binary Search Tree

#include
#include

/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct node
{
int data;
struct node* left;
struct node* right;
};

/* Helper function that allocates a new node
with the given data and NULL left and right
pointers. */
struct node* newNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;

return(node);
}

/* Give a binary search tree and a number,
inserts a new node with the given number in
the correct place in the tree. Returns the new
root pointer which the caller should then use
(the standard trick to avoid using reference
parameters). */
struct node* insert(struct node* node, int data)
{
/* 1. If the tree is empty, return a new,
single node */
if (node == NULL)
return(newNode(data));
else
{
/* 2. Otherwise, recur down the tree */
if (data <= node->data)
node->left = insert(node->left, data);
else
node->right = insert(node->right, data);

/* return the (unchanged) node pointer */
return node;
}
}

struct node* search(struct node* tmp, struct node** parent,struct node* item)
{
struct node* root;
root=tmp;

if(!root)
{
//*parent=NULL;
return NULL;
}
if(root->data==item->data)
{
return root;
}

*parent=root;

if(item->data<=root->data)
{
return search(root->left,parent,item);
}
else
{

return search(root->right,parent,item);
}

}

void deletes(struct node* root,struct node* srch)
{
struct node* parent;
struct node* succ=NULL;

if(!root)
return;

parent=NULL;

struct node* x=search(root,&parent,srch);

/* if the node to be deleted has no child */
if(x->left==NULL && x->right==NULL)
{

if(parent->left==x)
parent->left=NULL;
else
parent->right=NULL;

free(x);
return;
}


/* if the node to be deleted has only rightchild */
if (x->left == NULL && x->right!= NULL )
{
if ( parent->left == x )
parent->left = x->right ;
else
parent->right= x->right;

free ( x ) ;
return ;
}

/* if the node to be deleted has only left child */
if (x->left != NULL && x->right== NULL )
{
if ( parent->left == x )
parent->left= x->left ;
else
parent->right = x->left ;

free ( x ) ;
return ;
}


/* if the node to be deleted has two children */

if(x->left!=NULL && x->right!=NULL)
{
parent=x;
succ=x->right;

while(succ->left!=NULL)
{
parent=succ;
succ=succ->left;
}

x->data=succ->data;
x=succ;
free(x);//free(succ).....problem Might be here I dont Know why
}
}

/* Given a binary tree, print its nodes in inorder*/
void printInorder(struct node* node)
{
if (node == NULL)
return;

/* first recur on left child */
printInorder(node->left);

/* then print the data of node */
printf("%d ", node->data);

/* now recur on right child */
printInorder(node->right);
}


/* Driver program to test sameTree function*/
int main()
{
struct node* root = NULL;
root = insert(root, 4);
insert(root, 2);
insert(root, 1);
insert(root, 3);
insert(root, 6);
insert(root, 5);

struct node* parent= NULL;

root=search(root,&parent,root->left->right);
printf(" %d %d ", root->data, parent->data);

deletes(root,root->left->right);

printInorder(root);

getchar();
return 0;
}

Page Replacement Algorithm Using FIFO (Queue)

#include
#include
void main()
{
int a,b,ct=0,co=0,pf=0,list[30],arr[10],i,j,l;
clrscr();
printf("\n enter no fo processors:");
scanf("%d",&a);
printf("\n enter the series:");
for(i=0;i
scanf("%d",&list[i]);
printf("\n enter the no of frames:");
scanf("%d",&b);
for(i=0;i
arr[i]=0;
for(i=0;i
{
co=0;
if(ct==b)
ct=0;
for(int j=0;j
{
if(arr[j]==list[i])


{
co=1;
break;
}
}
if(co==0)
{
arr[ct]=list[i];
pf++;
ct++;
printf("\nf");
}
for(int l=0;l
printf("%d",arr[l]);
printf("\n");
}
printf("\n no of page faults are : %d",pf);
getch();
}



----------------------------------------------------------
OUT PUT:
----------------------------------------------------------
Enter no of processors: 3
Enter the series:
3
5
7
Enter the no of frames: 3
F400
F450
F457
No of page faults are :3