Parixit
BAN USER- 0of 0 votes
Answershow to read a character from console(output screen) in turboc in c++
- Parixit in India| Report Duplicate | Flag | PURGE
C++ - 0of 0 votes
AnswersGiven 2 sorted arrays..
- Parixit in United States
find the median of the merged array without using extra space in O(logn)| Report Duplicate | Flag | PURGE
Algorithm
int isMatching(char *s,char *p)
{
int si=0,pi=0,sl,pl;
sl=strlen(s);
pl=strlen(p);
int star=-2;
while(si<sl&&pi<pl)
{
if(p[pi]=='*')
star=pi++;
else if(p[pi]==s[si])
pi++,si++;
else
{
pi=star+1;
if(p[pi]==s[si]) // if(p[pi]!=s[si]) this will also work, but will take an extra condition check when this 'if' is false
pi++,si++; // si++;
else
si++;
}
}
if(pi==pl)
if(p[pi-1]=='*' || si==sl)
return 1;
else
return 0;
else
if(p[pi]=='*' && pi+1==pl)
return 1;
else
return 0;
}
we can take an extra array which stores the index of heap elements (heap is implemented using array) in sorted order,it will be kind of hashing concept. now applying binary search in this array taking the indices for the heap array - O(logn). and then, if not present, insertion in heap - O(logn)..
- Parixit November 26, 2012
- Parixit November 27, 2012