msankith
BAN USER- 0of 0 votes
AnswersTest cases for chat application (lyk MSN ,YAHOO CHAT,GTALK etc).
- msankith in India| Report Duplicate | Flag | PURGE
Microsoft Developer Program Engineer Testing - 0of 0 votes
AnswersQuestion 3)
- msankith in -
Given an crypted array obtain the original text . Should be implemented without extra space .
Eg: Crypt array : a3b4c3
decrypt array : aaabbbbccc
Imagine the array contains sufficient memory to hold the decrypt ?| Report Duplicate | Flag | PURGE
Microsoft Developer Program Engineer Arrays - 0of 0 votes
AnswersQuestion 2)
- msankith in India
Given a binary tree which contains values at each node , find whether the path exist from root to the "LEAF NODE" such that sum of the values of d path nodes is equal to the GIVEN SUM. if so return true or else return false| Report Duplicate | Flag | PURGE
Microsoft Developer Program Engineer Trees and Graphs
Check this soln
void sortSe(char a[],int low,int high)
{
int mid = (low+high)>>1;
int j=mid+1,i=mid;
if(high-low<=1)
return;
swap(a[mid],a[mid+1]);
while(i>low+1)
{
swap(a[i],a[i-1]);
swap(a[j],a[j+1]);
j++;
i--;
}
sortSe(a,low+2,high-2);
}
How the above code works - >
1 2 3 4 a 5 b c d
1 2 3 a 4 5 b c d
1 2 3 a 4 b 5 c d
1 2 a 3 4 b 5 c d
1 2 a 3 4 b c 5 d
1 a 2 3 4 b c 5 d
1 a 2 3 4 b c d 5
1 a 2 3 b 4 c d 5
1 a 2 b 3 4 c d 5
1 a 2 b 3 c 4 d 5
Solution for problem 1
char * replace(char *str,char *find,char *replace)
{
char *temp = (char *)malloc((sizeof(char)*(strlen(str)+strlen(replace)-strlen(find))));
char *i;
i=strstr(str,find);
if(i>=0)
{
strncpy(temp,str,(i-str));
strcat(temp,replace);
strcat(temp,i+strlen(find));
return temp;
}
return str;
}
Using only one stack
struct node {
int num;
struct node *link;
};
typedef struct node node1;
struct node *getnode()
{
return (struct node*)malloc(sizeof(struct node));
}
void Display(struct node *p)
{
while(p)
{
printf("%d \n",p->num);
p=p->link;
}
}
void QInsert(node1 **top,int num)
{
node1 *temp = getnode();
temp->num=num;
temp->link=*top;
*top=temp;
}
int QDelete(node1 **top)
{
node1 *f=*top;
int num;
if(*top==NULL)
{
printf("empty\n");
return -1;
}
if(f->link==NULL) //if pop element is first element of the stack
{
num=f->num;
*top=NULL;
return num;
}
while(f->link->link!=NULL) //traverse the stack till you find the last element
f=f->link;
num = f->link->num;
f->link=NULL;
return num;
}
1) Find the avg of combined array(i.e (4+10+15+20+1+13..+29)/10 = 13.9)
2) Using binary search find two elements from each array,1st element larger than avg ,2nd element smaller than average.
3) so at max we ll need to find the "min" of combination of the above 2+2+2 numbers
So complexity ll be O(n) i.e for finding avg.
Correct me if am wrong .
Reversing the stack is similar to reversing the singly linked list..
void ReverseStack(struct stack *oldtop,struct stack **newtop)
{
if(oldtop->next==NULL)
*newtop=oldtop;
else {
ReverseStack(oldtop->next,newtop);
oldtop->link->link=oldtop;
oldtop->link=NULL;
}
}
Pseduo code -
- msankith November 18, 2011