CareerCup

But where I will determine that the end of word has reached. I mean till which character I would say that the first word has reached. For that the time complexity will get increased to O(n^2) if there are two elements a and b.

Just use a binary search technique to find the first index of 1 in the array. Then return this index as the number of zeroes in the array

Suppose we have to access a particular computer F. But it is not accessible from the outside world. Whereas computer A is accessible from outside and it is connected to computer F by having outgoing ports on A and incoming ports on F from A.
1. We can think of all computers as nodes and the port connections as edges in a graph.
2. Then we can find out the shortest possible distance from computer A to computer F by using Dijkistra's algorithm. And to access some other computer we can think of the same solution

I executed the following code using clock function and it gave me the following result. Based on this the result is while(1) is faster.

#include <stdio.h>
#include <time.h>

int checkFaster()
{
	int a=1;
	clock_t begin,end;
	while(a)
	{
		begin=clock();
		a=0;
	}
	end=clock();
	double time_spent1=(double)(end-begin)/CLOCKS_PER_SEC;
	a=2;
	while(a)
	{
		begin=clock();
		a=0;
	}
	end=clock();
	double time_spent2=(double)(end-begin)/CLOCKS_PER_SEC;
	return (time_spent1>time_spent2?1:0);
}
int main()
{
	if(checkFaster())
		printf("No while2 is faster");
	else
		printf("Yes while1 is faster");
}

Please explain the increasing sequence here as there are others that might be possible of the same sequence.

Yes Mighuel definitely i do not know what i was thinking that was not the correct solution the array part. And Zhia has proposed a correct solution for it and thus i have updated the answer

To find a median of stream of integers we can use the concept of heaps:
Insert the first element in either of the below mentioned heaps and this number is the current median. Then compare the second incoming number with the first one. If the number is more then insert it in the HeapLow and if it less then insert it in the HeapMax.
Keep two heaps and keep on adding the numbers in these heaps as they come. If the numbers in the two heaps are even then you just take the average of the roots of the two heaps. Otherwise if they are unenven and difference is one in both the heaps take the number from the heap which has a higher count. If difference between their counts is more than one then take a number from the heap which has more elements and insert it into the another heap. And then find the median.

1. HeapLow: This heap is the max heap of the smaller of the numbers in the input stream so far
2. HeapMin: This heap is the min heap of the maximum of the numbers in the input stream so far
These are the two heaps to consider while finding the median.

No first find out the sum of the whole array S which turns out to be 30. So now S1 and S2 become 15. So now the problem reduces to finding a pair in the array whose sum is 15. S1 and S2 are just the notations used for sum of two elements (S1) and sum of rest of the elements (S2). Regarding duplicates they are not removed from the array, they are just not considered as we have to find 2 elements whose sum is equal to the rest of the elements of the array.

Sum of 2 elements (S1)=Sum of rest of elements (S2)
So total sum of array S=S1+S2 or S=2S1 so S1=S/2
Now the problem remains of finding two numbers with sum of S1 or S/2.
This can be done as find the sum of whole array and from there get S1 as S/2 and further proceed as:

1. Sort the array in O(nlogn).
For every element arr[i]
a. Binary search for S1-arr[i] in array from i+1 to n-1
b. If element exists then elements found are arr[i] and S1-arr[i].
Complexity: O(nlogn) for sorting and for doing binary search for n elements in logn time which takes total time of O(nlogn)

2. Use self balancing bst (avl trees)
a. Insert all the elements in avl tree. If element is already present then insert it into the left side of the already present element.
b. For each arr[i], search for S1-arr[i] in avl tree. If found then we get our two elements
Complexity: O(nlogn) again.

3. Use hashing.
a. Take a hash table and keep on indexing the elements like hash[arr[i]] to be 1.
b. For every arr[i] if hash[S1-arr[i]] is 1 then we have found our two elements
Complexity: O(n)

This will return the total number of set bits i.e. 1 bits in the number not consecutive set of 1 bits which is the question asked.

This can be done in the following manner by applying goto label in this way:

int count,i=1;
label ptr:
if(count<100&&i<=5)
{	count=count+getCount(dsi);
	i++;
	goto ptr;	
}

Here is a O(n) solution

#include <stdio.h>
#include <conio.h>

void printSum(int arr1[],int n,int arr2[],int m)
{
	int diff1=0,diff2=0,sum1=0,sum2=0,final_sum=0,sum3=0,sum4=0,i=0,j=0;
	while(i<n&&j<m)
	{
		diff1=arr1[i]-arr2[j];
		diff2=arr2[j]-arr1[i];
		sum1=sum1+diff1;
		sum2=sum2+diff2;
		sum3=sum3+arr1[i];
		sum4=sum4+arr2[j];
		if(diff1==0&&diff2==0)
		{
			if(sum1>sum2)
			{
				final_sum+=sum3;
			}
			else
				final_sum+=sum4;
			sum3=0,sum4=0;
		}
		i++,j++;
	}
	if(m<n)
	{
		while(i<n)
		{
			sum3=sum3+arr1[i++];
		}
		final_sum+=sum3;
	}
	else if(n<m)
	{
		while(j<m)
		{
			sum4=sum4+arr2[j++];
		}
		final_sum+=sum4;
	}
	else
	{
		if(sum3>sum4)
			final_sum+=sum3;
		else
			final_sum+=sum4;	
	}
	printf("Final sum is %d",final_sum);
}
int main()
{
	int arr1[]={3,5,7,9,20,25,30,40,55,56,57,60,62};
	int arr2[]={1,4,7,11,14,25,44,47,55,57,100};
	int n=sizeof(arr1)/sizeof(arr1[0]);
	int m=sizeof(arr2)/sizeof(arr2[0]);
	printSum(arr1,n,arr2,m);	
}

No it is running. Plese can you provide the case for which it fails..?

Here is the code. It also maintains the order of non-zero elements

void change(int arr[],int n)
{
	int first=0,count=0;
	for(int i=0;i<n;i++)
	{
		if(arr[i]!=0)
		{
			arr[first++]=arr[i];
			count++;
		}
	}
	for(int i=first;i<n;i++)
	{
		arr[i]=0;
	}
	for(int i=0;i<n;i++)
		printf(" %d ",arr[i]);
	printf("\nNo of non zero elements are %d ",count);	
}
int main()
{
	int arr[]={1,0,2,0,0,3,4};
	int n=sizeof(arr)/sizeof(arr[0]);
	change(arr,n);
}

At every alternate level:
1. Put the nodes in an array
2. Reverse the array
3. Put the nodes back in the tree at that level.
Code for the same:

#include <stdio.h>
#include <conio.h>
#include <malloc.h>
typedef struct tree
{
	char data;
	tree *left,*right;
};
tree *newNode(char data)
{
	tree *n=(tree *)malloc(sizeof(tree));
	n->data=data;
	n->left=n->right=NULL;
	return n;
}
int calheight(tree *root)
{
	if(root==NULL)
		return 0;
	else
	{
		int l=calheight(root->left);
		int r=calheight(root->right);
		if(l>r)
			return (l+1);
		else
			return (r+1);	
	}	
}
void reverse(char arr[],int length)
{
	int i=0,j=length-1;
	while(i<j)
	{
		char temp=arr[i];
		arr[i++]=arr[j];
		arr[j--]=temp;
	}
}
void printLevel(tree *root,int level)
{
	if(root==NULL)
		return;
	if(level==1)
		printf(" %c ",root->data);
	else if(level>1)
	{
		printLevel(root->left,level-1);
		printLevel(root->right,level-1);
	}		
}
void changeLevel(tree **root,int level,char arr[],int *index,int flag)
{
	if(root==NULL)
		return;
	if(level==1)
	{
		if(flag==1)
			arr[(*index)++]=(*root)->data;	
		else
			(*root)->data=arr[(*index)++];	
	}
	else if(level>1)
	{
		changeLevel(&((*root)->left),level-1,arr,index,flag);
		changeLevel(&((*root)->right),level-1,arr,index,flag);
			
	}		
}
void changeLevelOrder(tree *root)
{
	int height=calheight(root),j=0;
	char arr[100];
	for(int i=0;i<=height;i=i+2)
	{
		changeLevel(&root,i,arr,&j,1);
		reverse(arr,j);	
		j=0;	
		changeLevel(&root,i,arr,&j,0);
		j=0;
	}
	for(int i=1;i<=height;i++)
	{
		printLevel(root,i);
	}
}
int main()
{
	tree *root=newNode('a');
	root->left        = newNode('b');
	root->right       = newNode('c');
	root->left->left  = newNode('d');
	root->left->right = newNode('e');
	root->right->left = newNode('f');
	root->right->right = newNode('g');
	root->left->left->left = newNode('h');
	root->left->left->right = newNode('i');
	root->left->right->left = newNode('j');
	root->left->right->right = newNode('k');
	root->right->left->left = newNode('l');
	root->right->left->right = newNode('m');
	root->right->right->left = newNode('n');
	root->right->right->right = newNode('o');
  	changeLevelOrder(root);
  
}

But the question says no extra memory to be used

Code for
1. Split the second half
2. Reverse the second half
3. Subtract them first and second half and then merge them

#include <stdio.h>
#include <conio.h>
#include <malloc.h>
typedef struct ll
{
	int data;
	ll *next;
};

void print(ll *head)
{
	while(head!=NULL)
	{
		printf(" %d ",head->data);
		head=head->next;
	}
}
void insert(ll **head,int data)
{
	ll *n=(ll *)malloc(sizeof(ll));
	n->data=data;
	n->next=(*head);
	(*head)=n;
}
void diff(ll **head1,ll *head2)
{
	ll *temp=(*head1);
	while(temp&&head2)
	{
		temp->data=temp->data-head2->data;
		temp=temp->next;
		head2=head2->next;
	}
}
void reverse(ll **head)
{
	ll *current=(*head),*prev=NULL,*next;
	while(current!=NULL)
	{
		next=current->next;
		current->next=prev;
		prev=current;
		current=next;
	}
	(*head)=prev;
}
void splitAndSub(ll **head)
{
	ll *slow=*head,*fast=*head,*prev,*head1,*head2;
	while(fast->next&&fast->next->next)
	{
		prev=slow;
		slow=slow->next;
		fast=fast->next->next;
	}
	if(fast->next==NULL)
	{
		head1=*head;
		head2=slow->next;
		prev->next=NULL;
		reverse(&head2);
		diff(&head1,head2);
		reverse(&head2);
		*head=head1;
		prev->next=slow;
	}	
	else if(fast->next->next==NULL)
	{
		head1=*head;
		head2=slow->next;
		slow->next=NULL;
		reverse(&head2);
		diff(&head1,head2);
		reverse(&head2);
		*head=head1;
		slow->next=head2;
	}
	printf("Final List \n");
	print(*head);	
}
int main()
{
	ll *head=NULL;
	insert(&head,6);
	insert(&head,4);
	insert(&head,2);
	insert(&head,6);
	insert(&head,7);
	insert(&head,8);
	insert(&head,9);
	print(head);
	printf("\n");
	splitAndSub(&head);
}

We can make a cron job for the service by specifying the date and time in the job where it would perform the task specified to the job everyday

The black shape consists of one or more adjacent Xs and it checks the boundary cases

Please can you elaborate that because i have checked it and it is working for all the cases i have checked for. Please provide a case for which it is wrong

An elegant solution..;)

Without recursion just count the adjacent elements first row-wise and then column-wise. This can be done without recursion using the loops as:

#include <stdio.h>
#include <conio.h>

int countRows(char a[][7],int n,int m)
{
	int j=0,count=0,flag=0;
	for(int i=0;i<n;)
	{
		if(a[i][j]=='X'&&a[i][j+1]=='X'&&j<m-1)
		{	
			j=j+2;
			flag=1;
		}
		if(a[i][j]=='X'&&a[i][j+1]!='X'&&j<m-1)
		{
			j=j+2;
		}	
		if(a[i][j]=='X'&&j==m-1)
			j++;	
		if(a[i][j]=='O'&&j<m)
		{
			j++;
			if(flag==1)
			{
				count=count+1;
			}
			flag=0;	
		}
		if(j==m)
		{
			i++;
			j=0;
		}
	}
	return count;
}
int countCols(char a[][7],int n,int m)
{
	int i=0,count=0,flag=0;
	for(int j=0;j<m;)
	{
		if(a[i][j]=='X'&&a[i+1][j]=='X'&&i<n-1)
		{	
			i=i+2;
			flag=1;
		}
		if(a[i][j]=='X'&&a[i+1][j]!='X'&&i<n-1)
			i=i+2;
		if(a[i][j]=='X'&&i==n-1)
			i++;	
		if(a[i][j]=='O'&&i<n)
		{
			i++;
			if(flag==1)
			{
				count=count+1;
			}	
			flag=0;	
		}
		if(i==n)
		{
			j++;
			i=0;
		}	
	}
	return count;
}


int main()
{
	char a[][7]={{'O','O','O','X','O','O','O'},{'O','O','X','X','O','X','O'},
					{'O','X','O','O','O','X','O'}};
	int n=sizeof(a)/sizeof(a[0]);
	int m=sizeof(a[0])/sizeof(a[0][0]),flag=0;
	printf("%d",countRows(a,n,m)+countCols(a,n,m));
}

As x is acting as an index in the array and y is just there to reach the base case in recursion so given x you have to just multiply the numbers in the range from x to y. Because y will also be included as base case is to return 1 when x is greater than y. So if an array is
arr[]={3 5 6 7 8 9} and x is 2 and y is 4
So ans=arr[2]*arr[3]*arr[4]=6*7*8

The program will compile but the output will be empty. If you will replace !p with *p in while loop then it will give you the correct result. Otherwise !p means that the address that is assigned to p we apply a not operator that is if p is 0 only then !p is true and then the loop will execute. If you replace !p with p then the output will be an infinite set of characters as the '\0' is not defined to be any valid address.

Mine is an inplace algo. You can check that

Here is the code in C:)
Remember this is an in place algorithm that is you do not have to create an extra array or extra memory.

The basic algorithm is done here and of course we can do it with the help of already built in functions Like Java but we have to built in our own functions when asked about these questions. So
1. Count the number of words and spaces. If the spaces=words-1 then it is all correct but if its not then
2. Traverse thorough the string and count the number of words and spaces. Then you have to take a variable any variable make it 0 and then whenever there is a letter then put that letter in the variable you first initialized while you also have to take an another variable that is doing the normal traversal
3. Whenever there is an end of a word then put a space after that word and countine with the next word
4. At last put all the spaces n the end. My algo allows to end spaces-1 in the end as it already places an extra space after the last word.
Hope it helps:)

#include <stdio.h>
#include <conio.h>
#include <string.h>
int words=0;
int countWordsAndLetters(char *str)
{
	int wo=0;
	for(int i=0;i<strlen(str);)
	{
		if(str[i]!=' ')
		{
			while(str[i]!=' ')
			{
				i++;
				wo++;
			}
			words++;
		}
		else
			i++;
	}
	return wo;
}
int countSpaces(char *str)
{
	int co=0;
	for(int i=0;i<strlen(str);)
	{
		if(str[i]==' ')
		{	while(str[i]==' ')			
			{
				co++;	
				i++;
			}
		}
		else
			i++;
	}
	return co;	
}
int main()
{
	char str[]="Hello  World ";
	int prevLength=strlen(str);
	int space=countSpaces(str);
	int letters=countWordsAndLetters(str);
	if(space+1==words)
		printf("The entered string is correct ");
	else
	{
		int newLength=letters+words+space;
		int j=0;
		for(int i=0;i<prevLength;i++)
		{
			if(str[i]!=' ')
			{
				str[j]=str[i];
				j=j+1;
			}
			if(str[i+1]==' '&&str[i]!=' ')
			{
				str[j]=' ';
				j=j+1;				
			}
		}
		int s=space-1;
		while(s!=0)
		{
			str[j]=' ';
			j=j+1;
			s--;
		}
		str[j]='\0';
		for(int i=0;str[i]!='\0';i++)
		{
			if(str[i]==' ')
				printf("_");
			else
				printf("%c",str[i]);	
		}
	}
	
}

With KMP algorithm find all occurrences of a particular string in a string and then replace those occurrences with the given string.

Code in c:

#include <stdio.h>
#include <conio.h>
#include <string.h>
static int k;
void reve(char *str,int j)
{
    int i=0;
    while(i<j)
    {
        char temp=str[i];
        str[i++]=str[j];
        str[j--]=temp;
    }
}

void add2(char a,char b,char *sum2)
{
    if(a=='0'&&b=='1')
	{
		sum2[0]='1',sum2[1]='0';
	}
	else if(a=='1'&&b=='1')
	{
		sum2[0]='1',sum2[1]='1';
	}
	return sum2;
}

void add3(char a,char b,char c,char *sum)
{
	if(a=='0'&&b=='0'&&c=='0')
	{
		sum[0]='0';
		sum[1]='0';
	}
	else if((a=='1'&&b=='0'&&c=='0')||(a=='0'&&b=='1'&&c=='0')
		||(a=='0'&&b=='0'&&c=='1'))
	{
		sum[0]='1';
		sum[1]='0';
	}
	else if((a=='1'&&b=='1'&&c=='0')||(a=='0'&&b=='1'&&c=='1')
		||(a=='1'&&b=='0'&&c=='1'))
	{
		sum[0]='0';
		sum[1]='1';
	}
	else if(a=='1'&&b=='1'&&c=='1')
	{
		sum[0]='1';
		sum[1]='1';
	}
}

void traverse(char *str1,char *str2,char *s,char *str3,char c)
{
    int i,j;
    for(i=strlen(str2)-1,j=strlen(str1)-1;i>=0;i--,j--)
		{
			add3(str1[j],str2[i],c,s);
			if(s[1]=='0')
				str3[k++]=s[0];
			else if(s[1]=='1')
			{
				str3[k++]=s[0];
				c='1';
			}
		}
		for(i=j;i>=0;i--)
		{
			if(c=='1')
			{
				add2(str1[i],c,s);
				if(s[1]=='0')
					str3[k++]=s[0];
				else
				{
					str3[k++]=s[0];
					c='1';
				}
			}
			else
			{
				str3[k++]=str1[i];
			}
		}

}
char *sum(char *str1,char *str2)
{
	char str3[30],s[2],c='0';
	int j,i;
	if(strlen(str1)>strlen(str2))
	{
        traverse(str1,str2,s,str3,c);
	}
	else if(strlen(str1)<strlen(str2))
    {
         traverse(str2,str1,s,str3,c);
    }
    else
    {
        int i,j;
        for(i=strlen(str2)-1,j=strlen(str1)-1;i>=0&&j>=0;i--,j--)
		{
			add3(str1[j],str2[i],c,s);
			if(s[1]=='0')
				str3[k++]=s[0];
			else if(s[1]=='1')
			{
				str3[k++]=s[0];
				c='1';
			}
		}
		if(c=='1')
            str3[k++]=c;
    }
	reve(str3,k-1);
	for(i=0;i<k;i++)
        printf("%c",str3[i]);
    return str3;
}
int main()
{
	char str1[]="1001";
	char str2[]="100";
    char *str3=sum(str1,str2);
}

Can you elaborate your question more?

Here is the code in C :)

#include <stdio.h>
#include <conio.h>
#include <string.h>

int row=4,col=5;

int occur(char a[][5],int x,int y,char targ[],int index,int n)
{
	if(x<0||y<0||x>=row||y>=col)
		return 0;
	if(index>n)
		return 0;
	if(a[x][y]!=targ[index])
	{
			return 0;
	}
	if(index==strlen(targ)-1)
	{
		return 1;
	}
	return (occur(a,x,y+1,targ,index+1,n)	
		+occur(a,x+1,y,targ,index+1,n)
		+occur(a,x-1,y,targ,index+1,n)
		+occur(a,x,y-1,targ,index+1,n));
		
}
int count(char a[][5],char targ[])
{
	int d=0;
	for(int i=0;i<row;i++)
	{
		for(int j=0;j<col;j++)
		{
			if(a[i][j]=='S')
				d+=occur(a,i,j,targ,0,strlen(targ)-1);
		}
	}
	return d;
}

int main()
{
	char a[][5]={{'S','N','B','S','N'},{'B','A','K','E','A'},{'B','K','B','B','K'},{'S','E','B','S','E'}};
	char c[]={"SNAKES"};
	printf("No of occurences are %d ",count(a,c));

}

You can use a trie data structure. That is while traversing the array add the string to a trie and if that string already exists in trie then continue else you have to add the element in the trie. At last you have to traverse the trie and get all the strings from it. Advantage:
1. No key collusion as it can be there in a hash.
2. Trie can be traverses in O(m) time where m is the length if the string

First of all the difference between 15 and 7 is 8 not 9 so the answer should be 17. And here is the solution
Just keep all the dates in order in an array
arr[]={7,15,12,16,16,24}
Take a diff variable as 0 and add all the differences among consecutive elements as:
Diff=Diff+arr[i+1]-arr[i].
So Diff=8-3+4+0+8=17. Here you can apply the loop as:

int diff=0;
for(int i=0;i<n-1;i++)
{	
	diff=diff+arr[i+1]-arr[i];
}
return diff;

All right i have included that check in code..:)

Yes this code is only for the cases where we have to move a character. Of course for other cases we can call for checkPalindrome first and if it is already then we will not proceed. It can be included easily

I know its a bit large but just want it to code in C..:)

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <math.h>
int primeNo(int n)
{
	for(int i=2;i<=n/2;i++)
	{
		if(n%i==0)
		{
			return 0;
		}
	}
	return 1;
}
int compare(const void *a,const void *b)
{
	return (*(int *)a-*(int *)b);
}
int getNo(int n)
{
	int dig[20],j=0,k=0,flag=0,prod=1,num[20],no=0;
	for(int i=2;i<=9;)
	{
		if(n%i==0)
		{
			n=n/i;
			if(n>9&&primeNo(n)==1)
			{
				printf("Sorry not possible as we have a factor of prime greater than 9");
				flag=1;
				break;
			}
			else
				dig[j++]=i;	
		}
		else
			i++;
	}
	for(int i=0;i<j;i++)
		printf("%d",dig[i]);
	printf("\n");	
	
	for(int i=j-1;i>=0;)
	{
		if(dig[i]*dig[i-1]<10)
		{
			prod=dig[i]*dig[i-1];
			num[k++]=prod;
			i=i-2;
			while(prod<10&&i>=0)
			{
				prod=prod*dig[i];
				if(prod<10)
				{
						num[k++]=prod;
						i--;
				}	
			}	
		}
		else
		{
			num[k++]=dig[i];
			i--;
		}	
	
	}	
	if(flag==0)
	{
		qsort(num,k,sizeof(int),compare);
		int j=k-1;
		for(int i=0;i<k;i++)
		{
			no=no+num[i]*pow(10,j);
			j--;
		}	
	}
	if(n!=0)
		printf("%d",no);
}
int main()
{
	int n;
	printf("Enter the number to find product for ");
	scanf("%d",&n);
	getNo(n);
}

All right its right this problem is solved with 8 races by considering the following approach.
Let us suppose that after the first 5 races we get the following results as:

H1 H2 H3 H4 H5
H6 H7 H8 H9 H10
H11 H12 H13 H14 H15
H16 H17 H18 H19 H20
H21 H22 H23 H24 H25

Now we again do the 6th race among the group leaders and get the following result as:

1st- H1, 2nd- H6, 3rd- H11, 4th- H16 and 5th- H21

After the 6th race we can safely eliminate the following horses as:

1. H22 H23 H24 H25 from the last group as among the top 5 their group leader will be considered first and also they cannot win from H4, H3 , H2 and H1 which will be considered first.

2. H18, H19 and H20 from the 4th group as the top 5 would be considered as
H1 H6 H11 H16 and H17. So clearly their group leader and H17 would be considered and these horses have no chance of coming up

3. H14 and H15 from the 3rd group as the top 5 would first be
H1 H6 H11 H12 and H13 as H12 and H13 could be faster than both H16 and H17 and also H21

4. H10 from 2nd group as first the top 5 would come up as:
H1 H6 H7 H8 H9.

5. And no one from 1st group as they all are eligible to beat the group leaders from the next group
So we are left with:
H1 H2 H3 H4 H5
H6 H7 H8 H9
H11 H12 H13
H16 H17
H21

Clearly as H1 came first in all of the races so this is one of the top 5 horses.
Now we do a 7th race among H3 H7 H12 H11 and H16 as:

1. To consider H7 is faster than those of third group members

2. Make a competition among 3rd and 4th group members

3. H21 is not considered as first the 3rd and 4th group members and leaders will compete.

4. H6 is not considered to consider the competition between its group member with the corresponding group leaders as we know H6 is already faster than H11 H16 and H21 from the 6th race we did

5. Similarly eliminate H12 and H13 and H8 H9 are eliminated
So let the results of the 7th race be the following:
1st- H3 2nd- H7 3rd- H11 4th- H12 and 5th- H16
We can safely eliminate the following horses

1. H21 definitely cannot come in the top 5

2. H17 definitely cannot come in the top 5

3. H16 cannot come as first these horses would be considered as
H1 H2 H3 H4 H5 H6 H7 H11 as H7 is both better than H11 and H16 because of the results of the 7th race

4. We can also eliminate H11 as this would not be faster than both H6 and H7 as from 6th and 7th race and also H3 is faster than it as due to 7th race.
So we are left with
H1 H2 H3 H4 H5
H6 H7
Now we know that

H3 is better than H7 so H2 is also better. But we dont know which is better among H3 and H6 and H2 and H6. Dont worry as no matter what H2 will be there among the top 5 horses. So we do an 8th race among
H3 H4 H5 H6 H7 and the top 3 horses along with H2 and H1 will come up in the top 5 horses and thus we are done..

And read d answer its done for top 5 only

Please do not down vote it again and again. I have provided the correct explanation above
This can be done in 7 races consider the following steps;
1. Suppose we have the following horses as;
S1 S2 S3 S4 S5
S6 S7 S8 S9 S10
S11 S12 S13 S14 S15
S16 S17 S18 S19 S20
S21 S22 S23 S24 S25
Now we first carried out 5 races on these 5 groups and let the winners be S1,S6,S11,S16,S21.
Now further we eliminate the bottom 2 horses from every group and we are left with the remaining 15 horses as:
S1 S2 S3
S6 S7 S8
S11 S12 S13
S16 S17 S18
S21 S22 S23
Now we consider the 6th race among the group leaders to get the top three as:
S1 S6 and S11. Since S16 and S21 lost so we eliminate these two groups and we are left with:
S1 S2 S3
S6 S7 S8
S11 S12 S13
Now we take S1 as the winner horse for all the races so this horse is the fastest and it will definitely come in top 5 horses. So we eliminate it and keep it in the winning set.
We are left with
S2 S3
S6 S7 S8
S11 S12 S13
Further we also eliminate S12 and S13 as they cannot come in the top 5 as their group leader came 3rd itself so how could S12 and S13 can be included in the top 5. Similarly we eliminate S8 as it also cannot appear in the top 5 according to their group leader So we are left with
S2 S3
S6 S7
S11
So we do a 7th race and take out the top 4 horses combined with S1 to give us top 5 horses. We can also give this same explanation for top 3,4 horses. This can give us upto top 6 horses as these 5 horses as mentioned above combined with S1.

Code for removal of character to make palindrome

#include <iostream>
#include <string>
using namespace std;
int checkForPalindrome(string str,int i,int j)
{
	if(i==j)
		return 1;
	if(str[i]==str[j])
		return 1;
	if(str[i]!=str[j])
		return 0;
	return checkForPalindrome(str,i,j-1)&&checkForPalindrome(str,i+1,j);			
}
string removeChar(string str,int i,int j)
{
	if(i==j)
		return str;
	if(str[i]==str[j]&&i+1==j)
		return str;
	if(str[i]!=str[j]&&i+1==j)
	{
		str.erase(i,1);
		return str;
	}
	if(str[i]==str[j])
		return removeChar(str,i+1,j-1);
	if(str[i]!=str[j])
	{
		if(checkForPalindrome(str,i,j-1))
		{
			str.erase(j,1);
			return str;
		}
		else if(checkForPalindrome(str,i+1,j))
		{
			str.erase(i,1);
			return str;
		}
	}				
}
int main()
{
	string str="fbbfe";
         if(checkForPalindrome(str,0,str.length()-1)!=1)
	         str=removeChar(str,0,str.length()-1);
	cout<<str;
}

Here is the recursive approach:

void removeQm(char *s,int ind,int len)
{
	if(ind==len)
		return;
	if(s[ind]!='0'||s[ind]!='1')
	{
		ind=ind+1;
		removeQm(s,ind,len);
	}
	if(s[ind]=='0')
	{
		s[ind]='1';
		for(int i=0;i<len;i++)
			printf("%c",s[i]);
		printf("\n");	
		ind=ind+1;
		removeQm(s,ind,len);
	}
	if(s[ind]=='1')
	{
		s[ind]='0';
		for(int i=0;i<len;i++)
			printf("%c",s[i]);
		printf("\n");	
		ind=ind+1;
		removeQm(s,ind,len);
	}
		
}
int main()
{
	char s[]="a?b?c?d?";
	int len=strlen(s);
	for(int i=0;i<len;i++)
	{
		if(s[i]=='?')
			s[i]='0';
	}
	for(int i=0;i<len;i++)
		printf("%c",s[i]);
	printf("\n");
	removeQm(s,0,len);
}

@Ravio, although I have changed the code now but for your query of char *str. No we do need to allocate space for this. Compiler does automatically when the program is compiled. Because if you will write char str[20] then this is also equivalent to
char *(str+20). In char *str i just allocates the base address of an array and then from that base address you can further expand the array by indexing it

Sorry for the inconvenience. I thought we have to remove simultaneous occurring characters. But now i have changed it for removing single occurrence of a character

#include <stdio.h>
#include <conio.h>
#include <string.h>
void removeSingleChar(char *s,char c,int i,int pos,char prev)
{
	if(s[i]=='\0')
	{
		s[pos]='\0';
		for(int j=0;j<pos;j++)
			printf("%c",s[j]);
		return;
	}
	else if(prev==s[i])
	{
		s[pos++]=s[i];
	}		
	else if((s[i]!=s[i+1]&&s[i]!=c)||(s[i]==s[i+1]))
	{
		s[pos++]=s[i];
		prev=s[i];
	}
	i++;
	removeSingleChar(s,c,i,pos,prev);		
}
int main()
{
	char str[]="a000b000";
	char prev='\0';
	removeSingleChar(str,'0',0,0,prev);
	
}

import org.*

The maximum subset with negative set of integers can be found out by first eliminating negative numbers and then finding out maximum subset using Kadane's algorithm. If all the numbers are negative that is the sum <= 0 then return 0 as described above

Cut and paste this code into your editor to get the answer

#include <stdio.h>
#include <conio.h>
#include <malloc.h>
typedef struct tree
{
	tree *left;
	tree *right;
	int data;
}tree_t;
tree_t *makeNode(int data)
{
	tree_t *n=(tree_t *)malloc(sizeof(tree_t));
	n->left=n->right=NULL;
	n->data=data;
	return n;
}
int increment(tree_t *n)
{
	if(n==NULL)
		return 0;
	if(n->left==NULL&&n->right==NULL)
		return n->data;
	n->data=increment(n->left);
	n->data=n->data+increment(n->right);
	return n->data;
}
void printTree(tree_t *n)
{
	if(n==NULL)
		return;
	printf(" %d \n",n->data);
	printTree(n->left);
	printTree(n->right);
}
int main()
{
	tree_t *node;
	node=makeNode(20);
	node->left=makeNode(6);
	node->right=makeNode(2);
	node->left->left=makeNode(2);
	node->left->right=makeNode(3);
	printTree(node);
	increment(node);
	printf("\n");
	printTree(node);
}

Yes external merge sort is used to sort the 10 digit numbers as we have been provided with the memory constraint of 20 megabyte

If extra space is not to be used then use simple merge sort for the array and then as the array is sorted then all duplicate elements will appear consecutively. So they can be easily removed and then return the array . Time complexity is O(nlogn). But if it is to be done in O(n) then I think that we have to use an extra space in the form of a hash.

The question is similar to find pairs that sum up to a given number. This problem can be solved in O(n) as:

#include <stdio.h>
#include <conio.h>

void findPairs(int arr[],int n,int sum)
{
	int temp,bin[1000]={0},i;
	for(i=0;i<n;i++)
	{
		temp=sum-arr[i];
		if(temp>=0&&bin[temp]==1)
		{
			printf(" %d %d ",temp,arr[i]);
		}
		bin[arr[i]]=1;
	}
}
int main()
{
	int arr[]={0,1,2,3,5,6,9};
	int n=sizeof(arr)/sizeof(arr[0]);
	findPairs(arr,n,9);
}

You can use dynamic programming to find the palindrome in the substring. Here n is the length of the string

int i,j,k,L[n][n];
for(i=0;i<n;i++)
L[i][i]=1;
for(k=0;k<n;k++)
for(i=0;i<=n-k+1;i++)
{
	j=i+k-1;
	if(str[i]==str[j]&&k==2)
	L[i][j]=2;
	if(str[i]==str[j])
	L[i][j]=L[i+1][j-1]+2;
	else
	L[i][j]=max(L[i+1][j],L[i][j-1]);
}
return L[1][n-1];

The code is:

#include <stdio.h>
#define CHAR_SIZE 8
unsigned char rotate(unsigned char c,int m)
{
	return (c>>m|c<<(CHAR_SIZE-m));
}

int main()
{
	printf(" %u ",rotate(5,1));
}