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 32-bit 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
@Anthony
Thanks for your comment but this algorithm works for this question where you have to find 2 or 4 pairs of numbers with the same difference. That's why i said earlier that 9-1=8 there can be only one such pair with 8 as difference not any other pair. Similarly other optimizations work like this. So this algo works for finding out 2 or 4 pairs of numbers with the same difference. But if you want to see all such couples which are greater than 2 or 2 as you say that 2,3,4,5,6,7,8. Well for it works but here as it would wont calculate the difference of those whose not more than one pair eixsts so it only calculates the difference of those which have more pairs than 2. So here it will only print the difference till 4. I hope it is clear.Thanks
@Anthony Mays
No every element is not to be considered. Now read the below explanation:
arr={1,2,3,4,5,6,7,8,9}. Here I am taking the simplest array with difference of just 1.
Now 9-1=8 this difference cannot be found in the subarray{2,3,4,5,6,7,8} . Further
8-2=6 This difference cannot be found in the subarray {3,4,5,6,7} And further:
7-3=4 this difference cannot be found in subarray {4,5,6}. And also:
9-2=7 Note this difference only needs to be compared with high-1 which is 8 and low+1 which is 1 that is 7. and also 9-3=6 is only to be compared with high-1 and low+1 or high-2 and low. Thus for 9-2 only need to compare 8-1 and for 9-3 need to compare 8-1 or 8-2 or 7-1 . No element can further exist for this difference. Thus here the optimizations are made and the complexity is reduced. For array having 2 or 3 or 4 elements I have handled them seperately else for 5 or more elements further the array is divided into 2 or 3 or 4 elements to handle all the cases.
Yes it is calculating all possible set of differences.
Consider:
{1,2,3}
it is handled by first case low+2==high and returned no need to further call the function
{1,2,3,4}
it is handled by second case low+3==high and then returned so that no further function calls are made:
But if there are 5 elements and more then the last case handles it and further the function calls do the difference of arr[high]-arr[high-1] similarly for arr[low] with arr[low+1].
It is done like this
Just keep on checking for the difference by
a. First dividing the array into two halves
b. Check for left half
c. Check for right half.
d. But also check for the crossing sum that is one that passes through the middle element
e. At last when any two elements are left calculate the difference
f. At every point keep on storing the difference in the array they are the steps mentioned in the code of whom to calculate the differences
g. At last sort the array to check for pairs. Note this is the difference array and if at any consecutive positions four elements with same number are obtained then we have obtained the couple.
I know that the total number of couples are n*(n-1)/2. But you have to calculate the difference and also given the sorted array you have to make some optimizations to check for the required difference:
Like:
{10,20,30,40,50,60,70,80,90}. Further
Now {10,90 is a couple} but no need to calculate this difference because the difference of 80 cannot be made by any other couple. Further optimizations like this are made to check for the couples. I am just using the advantage of the sorted array. And i am having all the "POSSIBLE" differences in the array after which i am checking further. I know some one has downvoted it without even considering the approach and I respect his/her reviews but he/she altleast should give the reason for "DOWNVOTNG".
An approach of binary search is considered although it takes O(nlogn) time in the end because of sorting.First store all possible set of differences in the array and then sort it and check for pairs Here is the code you can test it and ask for any queries:
#include <stdio.h>
#include <conio.h>
int compare(const void *a,const void *b)
{
return ((*(int *)a)-(*(int *)b));
}
void findCouple(int arr[],int arr1[],int *i,int low,int high)
{
if(low==high)
{
return;
}
else if(low+1==high)
{
arr1[*i]=arr[high]-arr[low];
*i=*i+1;
return;
}
else
{
int mid=low+(high-low)/2;
if(low+2==high)
{
arr1[*i]=arr[mid]-arr[mid-1];*i=*i+1;
arr1[*i]=arr[mid+1]-arr[mid];*i=*i+1;
arr1[*i]=arr[mid+1]-arr[mid-1];*i=*i+1;
return;
}
else if(low+3==high)
{
arr1[*i]=arr[mid]-arr[mid-1];*i=*i+1;
arr1[*i]=arr[mid+1]-arr[mid];*i=*i+1;
arr1[*i]=arr[mid+1]-arr[mid-1];*i=*i+1;
arr1[*i]=arr[high]-arr[mid-1];*i=*i+1;
arr1[*i]=arr[high]-arr[mid];*i=*i+1;
return;
}
else
{
arr1[*i]=arr[mid]-arr[mid-1];*i=*i+1;
arr1[*i]=arr[mid+1]-arr[mid];*i=*i+1;
arr1[*i]=arr[mid+1]-arr[mid-1];*i=*i+1;
arr1[*i]=arr[high]-arr[mid-1];*i=*i+1;
arr1[*i]=arr[high]-arr[mid];*i=*i+1;
arr1[*i]=arr[mid]-arr[low];*i=*i+1;
}
findCouple(arr,arr1,i,low,mid-1);
findCouple(arr,arr1,i,mid+1,high);
return;
}
}
int main()
{
int arr[]={1,5,8,11,14,17,20,23,27};
int arr1[30];
int i=0;
int n=sizeof(arr)/sizeof(arr[0]);
findCouple(arr,arr1,&i,0,n-1);
int j,count1=0,count2=0,diff1=0,diff2=0;
qsort(arr1,n+2,sizeof(int),compare);
for(j=0;j<i;)
{
if(arr1[j]==arr1[j+1])
{
count1++;
if(count1==2)
{
diff1=arr1[j];
}
count2++;
if(count2==4)
{
diff2=arr1[j];
}
j=j+2;
}
else
{
j=j+1;
}
}
if(diff1==diff2)
printf(" The 4 couples occur with difference of %d ",diff1);
else if(diff1!=diff2&&(diff1!=0&&diff2!=0))
{
printf(" The two couples are there with difference of %d and 4 couples with %d",diff1,diff2);
}
else if(diff1!=0&&diff2==0)
{
printf(" The 2 couples with difference is %d ",diff1);
}
else if(diff2!=0&&diff1==0)
{
printf(" The 4 couples with difference is %d ",diff1);
}
}
@yolo read this : This i am pasting from wikipedia to clarify your doubt search for the same by typing trees in the wikipedia i cannot paste the link here:
A subtree of a tree T is a tree consisting of a node in T and all of its descendants in T.[c][1] Nodes thus correspond to subtrees (each node corresponds to the subtree of itself and all its descendants) – the subtree corresponding to the root node is the entire tree, and each node is the root node of the subtree it determines; the subtree corresponding to any other node is called a proper subtree (in analogy to the term proper subset).
Here is the code you can test it. Just do a normal inorder traversal and for every level just dequeue all the elements there and then add all the elements of that level to get the sum:
#include <stdio.h>
#include <conio.h>
#include <malloc.h>
typedef struct tree tree_t;
struct tree
{
int data;
tree_t *left;
tree_t *right;
};
tree_t *newNode(int data)
{
tree_t *n=(tree_t *)malloc(sizeof(tree_t));
n->data=data;
n->left=n->right=NULL;
return n;
}
typedef struct q q_t;
struct q
{
int front;
int rear;
tree_t **array;
};
q_t *createQueue(int size)
{
q_t *n=(q_t *)malloc(sizeof(q_t));
n->front=n->rear=0;
n->array=(tree_t **)malloc(size*sizeof(tree_t *));
return n;
}
void enqueue(q_t *s,tree_t *t)
{
s->array[(s->rear)++]=t;
}
tree_t *dequeue(q_t *s)
{
s->front++;
return s->array[s->front-1];
}
int isQueueEmpty(q_t *s)
{
return (s->front==s->rear);
}
int power(int a,int b)
{
int temp;
if(b==0)
return 1;
temp=power(a,b/2);
if(b%2==0)
return temp*temp;
else
{
if(b>0)
return a*temp*temp;
else
return (temp*temp)/a;
}
}
int printAllSum(tree_t *root,int k)
{
q_t *s=createQueue(30);
tree_t *temp=root;
int i=0,j=1,sum=0;
enqueue(s,temp);
while(temp)
{
if(power(k,i)==j)
{
while(!isQueueEmpty(s))
{
temp=dequeue(s);
sum=sum+temp->data;
}
printf(" %d level sum is %d",j,sum);
printf("\n");
}
if(temp->left)
enqueue(s,temp->left);
if(temp->right)
enqueue(s,temp->right);
j=j+1;
i=i+1;
sum=0;
}
return 0;
}
int main()
{
tree_t *t=newNode(1);
t->left=newNode(2);
t->right=newNode(3);
printAllSum(t,2);
}
The binary search will work like like this:
a. First find the start index of the number
b. Then find its end index
c. Thus we have find the start and the end index
#include <stdio.h>
#include <conio.h>
int firstIndex(int arr[],int low,int high,int key,int n)
{
if(high>=low)
{
int mid=low+(high-low)/2;
if((mid==0||key>arr[mid-1])&&arr[mid]==key)
return mid;
else if(arr[mid]<key)
return firstIndex(arr,mid+1,high,key,n);
else
return firstIndex(arr,low,mid-1,key,n);
}
return -1;
}
int lastIndex(int arr[],int low,int high,int key,int n)
{
if(high>=low)
{
int mid=low+(high-low)/2;
if( ( mid == n-1 || key < arr[mid+1]) && arr[mid] == key )
return mid;
else if(key < arr[mid])
return lastIndex(arr, low, (mid -1), key, n);
else
return lastIndex(arr, (mid + 1), high, key, n);
}
return -1;
}
int main()
{
int arr[]={1,2,2,2,3};
int n=sizeof(arr)/sizeof(arr[0]);
int fi=firstIndex(arr,0,n-1,2,n);
int si=lastIndex(arr,fi,n-1,2,n);
printf(" The first and last indices are %d %d ",fi,si);
}
Yeah its working here is the code. You can test it. Just keep a track of max palindrome substring occured so far and also take two pointers low and high and if the substring is palindrome and high-low+1 is greater than max so far then update max and print the substring:
#include <stdio.h>
#include <stdlib.h>
#include<string.h>
void print(char *str,int low,int high){
int i;
for(i=low;i<=high;i++)
printf("%c",str[i]);
}
int longsub(char *str){
int maxl=1,start=0,i,low,high;
int n=strlen(str);
for(i=1;i<n;i++){
//for odd palindrome
low=i-1;high=i;
while(low>=0&&high<n&&str[low]==str[high]){
if(high-low+1>maxl){
start=low;
maxl=high-low+1;
}
--low;++high;
}
//for even palindrome
low=i-1;high=i+1;
while(low>=0&&high<n&&str[low]==str[high]){
if(high-low+1>maxl){
start=low;
maxl=high-low+1;
}
--low;++high;
}
}
printf("Longest Palindrome substring is is ");
print(str,start,start+maxl-1);
}
int main()
{ char str[] = "FourscoreandsevenyearsagoourfaathersbroughtforthonthiscontainentanewnationconceivedinzLibertyanddedicatedtothepropositionthatallmenarecreatedequalNowweareengagedinagreahtcivilwartestingwhetherthatnaptionoranynartionsoconceivedandsodedicatedcanlongendureWeareqmetonagreatbattlefiemldoftzhatwarWehavecometodedicpateaportionofthatfieldasafinalrestingplaceforthosewhoheregavetheirlivesthatthatnationmightliveItisaltogetherfangandproperthatweshoulddothisButinalargersensewecannotdedicatewecannotconsecratewecannothallowthisgroundThebravelmenlivinganddeadwhostruggledherehaveconsecrateditfaraboveourpoorponwertoaddordetractTgheworldadswfilllittlenotlenorlongrememberwhatwesayherebutitcanneverforgetwhattheydidhereItisforusthelivingrathertobededicatedheretotheulnfinishedworkwhichtheywhofoughtherehavethusfarsonoblyadvancedItisratherforustobeherededicatedtothegreattdafskremainingbeforeusthatfromthesehonoreddeadwetakeincreaseddevotiontothatcauseforwhichtheygavethelastpfullmeasureofdevotionthatweherehighlyresolvethatthesedeadshallnothavediedinvainthatthisnationunsderGodshallhaveanewbirthoffreedomandthatgovernmentofthepeoplebythepeopleforthepeopleshallnotperishfromtheearth";
printf("\nLength is: %d\n", longsub( str ) );
return 0;
}
Modify the stack by keeping an extra value frequency in the stack that is modify the structure of the stack like:
struct stack
{
int top;
int arr[size];
int freq;
}; Then further increment this value for every element in the stack and if for a particular element the frequency is greater than the previous element then push this element to the stack and thus the pop operation will lead to the most frequent element
This approach of binary search is considered as:
a. Find the middle element in the array. If the middle element is equal to the number then we have find our minimum difference of that number that is 0
b. If the number is less than the middle element then find the difference and then search further in the left half.
c. If the number is more than the middle element then find the difference and then search in the right half.
d. Here the variable difference is static for comparing this diff with other scenarios.
You can test this code below:
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
int leastDiff(int a[],int low,int high,int n)
{
static int diff=INT_MAX;
if(low>high)
{
return diff;
}
if(low==high)
{
if(a[low]>n)
{
int b=a[low]-n;
if(b<diff)
diff=b;
}
else
{
int b=n-a[low];
if(b<diff)
diff=b;
}
return diff;
}
else
{
int mid=low+(high-low)/2;
if(a[mid]==n)
{
int b=a[mid]-n;
if(b<diff)
diff=b;
return diff;
}
else if(a[mid]>n)//search in the left half to find min difference.
{
int b=a[mid]-n;
if(b<diff)
diff=b;
leastDiff(a,low,mid-1,n);
return diff;
}
else if(a[mid]<n)//search in the right half to find min difference
{
int b=n-a[mid];
if(b<diff)
diff=b;
leastDiff(a,mid+1,high,n);
return diff;
}
}
}
int main()
{
int arr[]={10,20,30,40,50};
int n=sizeof(arr)/sizeof(arr[0]);
printf(" Minimum difference is %d ",leastDiff(arr,0,n-1,11));
}
This problem can be solved by using binary search to get the first position of 1 in the list. Here is the logic:
a. First check for the middle position of the array. If the mid is not 1 then you do not have to check in the left subarray as it will contain only 0s. For it you just have to check the right subarray.
#include <stdio.h>
#include <stdlib.h>
int firstPosOfOne(int arr[],int low,int high)
{
if(low==high)
{
if(arr[low]==1)
return low;
}
if(low+1==high)
{
if(arr[high]==1)
return high;
else if(arr[low]==1)
return low;
}
else
{
int mid=low+(high-low)/2;
if(arr[mid]==1)
return mid;
firstPosOfOne(arr,mid+1,high);
}
}
int main()
{
int arr[]={0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1};
int n=sizeof(arr)/sizeof(arr[0]);
printf(" First position of one occurs at %d location in the array ",firstPosOfOne(arr,0,n-1));
}
For every possible permutation of the string where here every permutation of the string means an anagram then for a particular permutation or anagram we check whether it is a palindrome or not in the following way:
a. Divide the string into two halves.
b. Check for the left half if it is palindrome by again recursively dividing that left half further. Note that here the base case would be when at last two characters are are left and they are palindrome. Then when the recursive call returns check for the right half of this left half. And also note that when a single character is left then it is already a palindrome. (Single characters are always palindromes of themselves).
c. Similarly check for the right half.
d. Thus if this anagram is palindrome increase the count of palindromes.
e. At last return the number of palindromes that can occur with all the anagrams of the string.
It can be done with recursion. Just check for adjacent elements while also keeping track of out of bounds of array. Here is the code. You can test it:
#include <stdio.h>
#include <stdlib.h>
void convertToNextColor(char arr[4][6],int i,int j)
{
if(i<0||j<0)
return;
else if(i>5||j>5)
return;
else
{
if(arr[i][j]=='B')
{
convertToNextColor(arr,i,j-1);
arr[i][j]='W';
convertToNextColor(arr,i,j+1);
arr[i][j]='W';
convertToNextColor(arr,i-1,j);
arr[i][j]='W';
convertToNextColor(arr,i+1,j);
arr[i][j]='W';
}
else
return;
}
}
int main()
{
char a[4][6]={{'W','B','W','W','B','W'},{'B','B','W','W','B','W'},{'W','B','B','B','W','B'},{'W','B','W','W','B','B'}};
int i,j;
convertToNextColor(a,1,1);
for(i=0;i<4;i++)
{
for(j=0;j<6;j++)
printf(" %c ",a[i][j]);
printf("\n");
}
}
but to mention here please mention that m is not the length of the array but it is m-1 as in that case the array will take the addresses as the elements as you are doing while(i<m) but actually i is only to be run till m-1 that is:
while(i<m-1)
but just to mention you can only call the function with m-1 rather than making changes to the whole function..
This problem can be solved by using an approach of binary search:
a. Every time the array is divided into 2 parts and then solve for the left half and the right half as:
b. If the current element is less than the key then enter it into one array and if the current element is greater then enter it into second array. If both are equal then enter into the 2nd array. At last combine the or concatenate the two arrays .Thus the solution O(n). You can test it:
#include <stdio.h>yuh
#include <stdlib.h>
void numberPrintLess(int arr[],int arr1[],int arr2[],int low,int high,int *left,int *right,int key)
{
if(low==high)
{
if(key<arr[low])
{
arr2[*right]=arr[low];
*right=*right+1;
}
else
{
arr1[*left]=arr[low];
*left=*left+1;
}
return;
}
if(low+1==high)
{
if(key<arr[low]&&key<arr[high])
{
arr2[*right]=arr[low];
*right=*right+1;
arr2[*right]=arr[high];
*right=*right+1;
}
else if(key>arr[low]&&key>arr[high])
{
arr1[*left]=arr[low];
*left=*left+1;
arr1[*left]=arr[high];
*left=*left+1;
}
else if(key>arr[low]&&key<arr[high])
{
arr1[*left]=arr[low];
*left=*left+1;
arr2[*right]=arr[high];
*right=*right+1;
}
else if(key<arr[low]&&key>arr[high])
{
arr1[*left]=arr[high];
*left=*left+1;
arr2[*right]=arr[low];
*right=*right+1;
}
else if(key==arr[low]&&arr[low]<arr[high])
{
arr1[*left]=arr[low];
*left=*left+1;
arr2[*right]=arr[high];
*right=*right+1;
}
else if(key==arr[low]&&arr[high]<arr[low])
{
arr1[*left]=arr[high];
*left=*left+1;
arr2[*right]=arr[low];
*right=*right+1;
}
else if(key==arr[high]&&arr[high]<arr[low])
{
arr1[*left]=arr[high];
*left=*left+1;
arr2[*right]=arr[low];
*right=*right+1;
}
else if(key==arr[high]&&arr[low]<arr[high])
{
arr1[*left]=arr[low];
*left=*left+1;
arr2[*right]=arr[high];
*right=*right+1;
}
else if(key==arr[low]&&arr[high]==arr[low])
{
arr1[*left]=arr[high];
*left=*left+1;
arr1[*left]=arr[low];
*left=*left+1;
}
}
else
{
int mid=low+(high-low)/2;
if(arr[mid]<key)
{
arr1[*left]=arr[mid];
*left=*left+1;
}
else if(arr[mid]>key)
{
arr2[*right]=arr[mid];
*right=*right+1;
}
else if(arr[mid]==key)
{
arr2[*right]=arr[mid];
*right=*right+1;
}
numberPrintLess(arr,arr1,arr2,low,mid-1,left,right,key);
numberPrintLess(arr,arr1,arr2,mid+1,high,left,right,key);
}
return;
}
void concatenate(int arr1[],int arr2[],int *left,int *right)
{
int i,arr[25];
for(i=0;i<*left ;i++)
{
arr[i]=arr1[i];
}
int j=i;
for(i=0;i<*right;i++)
{
arr[j]=arr2[i];
j++;
}
for(i=0;i<j;i++)
printf(" %d ",arr[i]);
}
int main()
{
int arr[]={0,-1,-2,0,3,5};
int arr1[25],arr2[25];
int n=sizeof(arr)/sizeof(arr[0]);
int left=0;
int right=0;
numberPrintLess(arr,arr1,arr2,0,n-1,&left,&right,0);
concatenate(arr1,arr2,&left,&right);
}
As there are 52 weeks in a given year and each day appears once a week so by sure all the days appear atleast 52 times in a year. But as 52*7=364 and as there are 365 days a year in a non leap year and 366 days in a leap year so 2 situations arise.
a. If today is monday and it is 1st january of a non leap year so next year 1st january will be on tuesday. So monday will appear 53 times and the rest days 52 times thus accounting for 365 days
b. If today is monday and it is 1st january of a leap year then next year 1st january will occur on wednesday that is monday and tuesday will occur for 53-53 times thus accounting for 2 extra days of 366 days and the rest appears 52 times.
@Sunny This is binary search everytime i am dividing the array into two parts and whenever the element satisfies the given condition i am returning the index so the comparison of the rest of the elements is avoided. And please first read or explore about binary search recursive version in wikipedia or somewhere else.Since i cannot post the link here i am copying the code for a recursive binary search given in wikipedia. Please read it:
int binary_search(int A[], int key, int imin, int imax)
{
// test if array is empty
if (imax < imin)
// set is empty, so return value showing not found
return KEY_NOT_FOUND;
else
{
// calculate midpoint to cut set in half
int imid = midpoint(imin, imax);
// three-way comparison
if (A[imid] > key)
// key is in lower subset
return binary_search(A, key, imin, imid-1);
else if (A[imid] < key)
// key is in upper subset
return binary_search(A, key, imid+1, imax);
else
// key has been found
return imid;
}
}
The jobs in the printer are basically kept in a queue and if only one instance is there and several jobs to be printed are there then the printer prints the jobs on a first come first serve basis.
But when two or more instances of the word are running and simultaneous instructions are provided to print the job to the printer then the priority to the jobs should be given according to the size of the job. Suppose the size of one job is 100 kb and size of another job is 50 kb then the priority to first job should be given. Thus the printer driver could be designed on the basis of priority queue. To ensure it more we can use a counting semaphore where the less-size job holds the resources that is the printer driver until it is completely printed after which the resource becomes available to the next job for printing.
It is a problem of longest palindrome sub-string.
#include <stdio.h>
#include <stdlib.h>
#include<string.h>
int max(int x,int y){
return (x>y)?x:y;
}
int lps(char* seq,int i,int j){
if(i==j)
return 1;
if(seq[i]==seq[j]&&i+1==j)
return 2;
if(seq[i]==seq[j])
return lps(seq,i+1,j-1)+2;
return max(lps(seq,i,j-1),lps(seq,i+1,j));
}
int main()
{ char arr[]="BBABCBCAB";
int n=strlen(arr);
printf("the length of the longest substring is %d ",lps(arr,0,n-1));
return 0;
}
You can use the following approach.
a.Take one pointer increment it by 2
b.Take another pointer increment it by 1.
c.If at any time first that is fast pointer reaches null then return false as loop does not exist.
d.If at any time second one that is the slow becomes equal to the first one then break.
e.Take the slow pointer to the start and then increment both by one till they become equal .That becomes the starting point of a loop in the linked list.
You can refer to the following logic:
a.If zero does not exist in the array then number is not possible.
b.Sort the whole array and then calculate the sum of the whole array.If the sum of the digits is divisible by 3 then the number can be formed and generate the number.
c.If sum of digits is not divisible by 3 then as the array is sorted take every number and subtract it from the sum just calculated above. If sum is divisible by 3 then generate the number and if not then continue further in this fashion.
d.The array is sorted to get the largest number formed from the array.
Here is the below code:
#include <stdio.h>
#include <stdlib.h>
int compare(const void *a,const void *b)
{
return (*(int *)a-*(int *)b);
}
int calculateSum(int arr[],int n)
{
int i,sum=0;
for(i=0;i<n;i++)
sum=sum+arr[i];
return sum;
}
int generateNumber(int arr[],int j,int n)
{
int i;
int num=0,power,k=0;
for(i=j;i<n;i++)
{
power=(arr[i]*pow(10.0,k));
num=power+num;
k=k+1;
}
//to include last zero in the number
return (num+1)*10;
}
void findSum(int arr[],int n)
{
int i=0,sum,num;
if(arr[i]!=0)
{
printf("\nNumber not possible");
return;
}
else
{
sum=calculateSum(arr,n);
if(sum%3==0)
{
num=generateNumber(arr,1,n);
printf("The number is %d ",num);
return;
}
else
{
for(i=0;i<n;i++)
{
int c=sum;
sum=sum-arr[i];
if(sum%3==0)
{
num=generateNumber(arr,i+1,n);
printf("The number is %d ",num);
return;
}
else
{
sum=c;
}
}
}
}
}
void printArray(int arr[],int n)
{
int i;
for(i=0;i<n;i++)
printf(" %d ",arr[i]);
}
int main()
{
int arr[]={6,7,8,0,1,2};
int i;
int n=sizeof(arr)/sizeof(arr[0]);
qsort(arr,n,sizeof(int),compare);
printArray(arr,n);
findSum(arr,n);
}
I think it can simply be done using recursion in the following way.It just traverse the bst in a recursive way which will take the same time as that required to traverse a bst. You can test the below code:
#include <stdio.h>
#include <stdlib.h>
typedef struct node node_t;
struct node
{
int data;
node_t *left;
node_t *right;
};
node_t *newNode(int data)
{
node_t *n=(node_t *)malloc(sizeof(node_t));
n->data=data;
n->left=NULL;
n->right=NULL;
}
void findCeil(node_t *root,int data)
{
if(root->data==data)
findCeil(root->right,data);
else if(root->data<data)
findCeil(root->right,data);
else if(root->data>data)
{
printf("The value found is %d ",root->data);
return;
}
}
int main()
{
node_t *tree=newNode(3);
tree->left=newNode(2);
tree->left->left=newNode(1);
tree->right=newNode(6);
tree->right->right=newNode(7);
tree->right->left=newNode(5);
findCeil(tree,6);
}
The ancestor matrix can be calculated as below. You can test the below code:
#include <stdio.h>
#include <stdlib.h>
typedef struct node node_t;
struct node
{
int data;
node_t *left;
node_t *right;
};
node_t *newNode(int data)
{
node_t *nn=(node_t *)malloc(sizeof(node_t));
nn->data=data;
nn->left=NULL;
nn->right=NULL;
return nn;
}
void findAncestor(node_t *root,int arr[][4],int temp[],int index)
{
if(root==NULL)
return;
int i;
for(i=0;i<index;i++)
arr[root->data][temp[i]]=1;
temp[index]=root->data;
findAncestor(root->left,arr,temp,index+1);
findAncestor(root->right,arr,temp,index+1);
}
int main()
{
node_t *nn=newNode(1);
nn->left=newNode(2);
nn->right=newNode(3);
int temp[4],i,j;
int arr[4][4]={0};
findAncestor(nn,arr,temp,0);
printf("The ancestor matrix is\n");
for(i=0;i<4;i++)
for(j=0;j<4;j++)
{
if(arr[i][j]==1)
printf("The ancestor of %d is %d ",i,j);
}
}
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 ...
Here is the code in O(n):
a. Make an array of size 256 to hold all the character count
b. Find the max count in the array
c. Find the second max count in the array by storing all counts less than max in another array and finding the max of those counts which becomes the second count
d. At last print the character
- vgeek July 15, 2013