vgeek
BAN USER 0of 0 votes
AnswersYou are required to parse the xml file:
 vgeek in United States
<ledger>
<person>
<name>Jai</name><location>Bangalore</location>
</person>
<entries>
<entry><day>1</day><credit>50</credit><debit>40</debit></entry>
….
…
multiple entries were there, and multiple people were there.
We were required to validate the XML file.Open and Close tags matching.
We were required to parse, maintain the max balance for each person, the longest span of days each person had the max balance, and report queries such as who had the overall max balance , his span and location. Span must contain the day numbers, not length. Report Duplicate  Flag  PURGE
Yahoo Software Engineer / Developer  0of 2 votes
AnswersConvert a base 2 number to a base 4 number
 vgeek in United States Report Duplicate  Flag  PURGE
Microsoft Software Engineer / Developer  1of 1 vote
AnswersI have heard this question many times in microsoft interviews. Given two arrays find the intersection of those two arrays. Besides using hash table can we attain the same time complexity that is O(m+n) by using some other approach.
 vgeek in United States Report Duplicate  Flag  PURGE
Microsoft Software Engineer / Developer  0of 0 votes
AnswersGiven a dl representing the spiral level order traversal of a binary tree,convert it to a binary tree using one stack. In Last level, nodes will be either to the right or left only. complete code in C. It is usually done using two stacks. Can it be done using one stack?
 vgeek in United States Report Duplicate  Flag  PURGE
Amazon Software Engineer / Developer  0of 0 votes
AnswersConsider the problem of sorting in ascending order of an array of numbers where each number is in the range 50000 to 50000000. What sorting algorithm is the best choice for the above problem. What is the best case time complexity of sorting available to this problem.
 vgeek in United States
Options are:
a. Merge Sort
b. Insertion Sort.
c. Quick Sort.
d. Counting Sort.
e. Bubble Sort Report Duplicate  Flag  PURGE
Yahoo Software Engineer / Developer  1of 1 vote
AnswersTwo 32bit integers n and m are given and positions i,j,k,l are given.Write a method to copy the contents of m from position k to l into n from position i to j.
 vgeek in United States
(example n=1010000000,m=10101010,i=3,j=5,k=5,l=7..output=10'101'00000) Report Duplicate  Flag  PURGE
Microsoft
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)(endbegin)/CLOCKS_PER_SEC;
a=2;
while(a)
{
begin=clock();
a=0;
}
end=clock();
double time_spent2=(double)(endbegin)/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");
}

vgeek
July 20, 2014 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.
 vgeek July 06, 2014Sum 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 S1arr[i] in array from i+1 to n1
b. If element exists then elements found are arr[i] and S1arr[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 S1arr[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[S1arr[i]] is 1 then we have found our two elements
Complexity: O(n)
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);
}

vgeek
June 30, 2014 Here is the code. It also maintains the order of nonzero 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);
}

vgeek
June 26, 2014 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=length1;
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,level1);
printLevel(root>right,level1);
}
}
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),level1,arr,index,flag);
changeLevel(&((*root)>right),level1,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);
}

vgeek
June 25, 2014 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>datahead2>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);
}

vgeek
June 25, 2014 Without recursion just count the adjacent elements first rowwise and then columnwise. 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<m1)
{
j=j+2;
flag=1;
}
if(a[i][j]=='X'&&a[i][j+1]!='X'&&j<m1)
{
j=j+2;
}
if(a[i][j]=='X'&&j==m1)
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<n1)
{
i=i+2;
flag=1;
}
if(a[i][j]=='X'&&a[i+1][j]!='X'&&i<n1)
i=i+2;
if(a[i][j]=='X'&&i==n1)
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));
}

vgeek
June 19, 2014 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.
 vgeek June 13, 2014Here 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=words1 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 spaces1 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=space1;
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]);
}
}
}

vgeek
June 11, 2014 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,k1);
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);
}

vgeek
June 09, 2014 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<0y<0x>=rowy>=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,x1,y,targ,index+1,n)
+occur(a,x,y1,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));
}

vgeek
June 07, 2014 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=83+4+0+8=17. Here you can apply the loop as:
int diff=0;
for(int i=0;i<n1;i++)
{
diff=diff+arr[i+1]arr[i];
}
return diff;

vgeek
June 07, 2014 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=j1;i>=0;)
{
if(dig[i]*dig[i1]<10)
{
prod=dig[i]*dig[i1];
num[k++]=prod;
i=i2;
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=k1;
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);
}

vgeek
June 05, 2014 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..
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,j1)&&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,j1);
if(str[i]!=str[j])
{
if(checkForPalindrome(str,i,j1))
{
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;
}

vgeek
June 03, 2014 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);
}

vgeek
May 31, 2014 @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);
}

vgeek
May 27, 2014 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);
}

vgeek
March 09, 2014 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.
 vgeek September 22, 2013The 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=sumarr[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);
}

vgeek
September 22, 2013 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<=nk+1;i++)
{
j=i+k1;
if(str[i]==str[j]&&k==2)
L[i][j]=2;
if(str[i]==str[j])
L[i][j]=L[i+1][j1]+2;
else
L[i][j]=max(L[i+1][j],L[i][j1]);
}
return L[1][n1];

vgeek
September 01, 2013
RepGayle L McDowell, CEO at CareerCup
Gayle Laakmann McDowell is the founder / CEO of CareerCup, which provides programming interview prep for candidates interviewing with Microsoft, Google ...
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.
 vgeek November 26, 2014