dhamu.31954
BAN USER@Erasmus.....if adjacency list is given then u r right ......but in question he mention List of (parent, child ) ...and after that he write adjacency list.....i think adjacency list is not same as List of (parent, child) pairs
consider following small example
A
/ \
B C
adjacency list is
A>{B C}
and (parent,child) is (A,B),(A,C) {(Parent,Child) pairs}
so for constructing adjacency list from (parent,child )pairs we need hashtablet....

dhamu.31954
November 28, 2013 @Vin.....no need for root node.....do dfs from any node...u will able to find whether there is loop or not...for finding loop u have to keep track of visited nodes....once u find node again then loop exist otherwise not....
@Erasmus..how can u do dfs in O(1) space complexity in this case....for dfs u have to construct adjacency list or adjacency matrix from given pairs and also u have to keep track of visited nodes while dfs is running O(V) space
in my method u have to traverse list one time... maintaining hash table for counting unique node... simultaneously count number of edges and we are done
we can do it more efficiently ..........in case of binary tree....
number of edges in n nodes binary tree is equals to (n  1)
count number of nodes in binary tree lets say n
and also count number of edges(numbers of parents child pairs given) lets say e
if(e>n1)
return false
else
return true

dhamu.31954
November 27, 2013 yes this is best solution for this problem......
 dhamu.31954 November 24, 2013i think above code is correct and telling that weather we can make valid dictionary word by breaking giving word....but in your for loop...u are processing some substrings again and again..which is inefficient i think.... following is java code which printing all valid world from dictionary(or we can modified following code if u want only bool value)...my point is making for loop efficient(only processing one substring one time)...correct me if i wrong..or my code is wrong
public void removeword(String s,int j){
int i;
if(s==NULL)
return;
if(s.length()==1){
System.out.println(s);
return;}
if(dic.contain(s))
System.out.println(s);
for(i=j;i<s.length();i++){
removeword(s.substring(0,i)+s.substring(i+1,s.length()),i);
}
}

dhamu.31954
October 01, 2013 we can do this with XOR....suppose 2 elements are present one time....lets take an example
given array is {1,3,1,2,2,5,4,5} our output will be 3 and 4
step 1: XOR all elements...we get 3(XOR)4=111(in binary)
step 2: check first one in binary of XOR from right side....in our example first LSB is one....which means...LSB of required numbers is are not same.....
step 3: divide array in two parts..first part numbers has 1 at LSB and second part number has 0 at LSB
step 4: take XOR of first part we get first number and XOR of second part give second
our example
first part: 1(001),1(001),3(011) ,5(101), 5(101) .....XOR of these give 3
secont part: 2(010),2(010),4(100) XOR of these give 4
output: 3,4....which is required
i think for number more then 2 unique numbers..suppose for 10 unique numbers we have to divide array further to get all 10 element(for further division we can use other bits of xor)
@somebody, is your comment to reffer my code..
then,if counting start from 0 then 52 is BA
or if counting start from 1 then its AZ
my code will give BA for 52(because I start counting from 0)
if u want to start counting from 1....just add num=num1 to my code after raw_input() line
please comment if my code give wrong answer
python code
num=int(raw_input())
result=""
while(num>=0):
t=num%26
result=chr(ord("A")+t)+result
num=num/26 1
print result

dhamu.31954
September 26, 2013 Another possible solution(Python code)
num=int(raw_input())
result=""
while(num>=0):
t=num%26
result=chr(ord("A")+t)+result
num=num/26 1
print result

dhamu.31954
September 26, 2013 you can do like this....extra space is required.....but if extra space is not allowed then apply mergsort on array.....at the time of merging put only one instance of integer by discarding all duplicates....complexity is O(nlogn)
 dhamu.31954 September 20, 2013@Anon....is this comment reffers to my programm
 dhamu.31954 September 20, 2013void strper(char *str,int a,int n,int l){
int i;
if(l==n){
if(a!=2)return;
str[l]='\0';
printf("%s\n",str);
return;
}
if(a!=2){
str[l]='a';
strper(str,a+1,n,l+1);
}
for(i=1;i<26;i++){
str[l]='a'+i;
strper(str,a,n,l+1);
}
}
int main ( ) {
char *str;
int n;
printf("Enter the value of n:");
scanf("%d",&n)
str=(char *)malloc(n+1);
strper(str,0,n,0);
return 0;
}

dhamu.31954
September 19, 2013 we have to convert BST into doubly linked list(instead of single) then merge
and then convert back into balabced BST( DLL to balanced BST can be done inplace)
void p2(int open1,int open2,int open3,int close1,int close2,int close3,int n,char *s){
if(open1==0 && close1==0 && open2==0 && close2==0 && open3==0 && close3==0){
printf("%s\n",s);
return;
}
if(open1==close1 && open2==close2 && open3==close3){
if(open1>0){
s[n]='{';
p2(open11,open2,open3,close1,close2,close3,n+1,s);}
}
if((open1<close1 (open1==0 && close1==0))&& open2==close2 && open3==close3){
if(open1>0){
s[n]='{';
p2(open11,open2,open3,close1,close2,close3,n+1,s);}
if(open2>0){
s[n]='[';
p2(open1,open21,open3,close1,close2,close3,n+1,s);}
if(close1>1){
s[n]='}';
p2(open1,open2,open3,close11,close2,close3,n+1,s);}
}
if((open2<close2  (open2==0 && close2==0)) && open3==close3){
if(open2>0){
s[n]='[';
p2(open1,open21,open3,close1,close2,close3,n+1,s);}
if(open3>0){
s[n]='(';
p2(open1,open2,open31,close1,close2,close3,n+1,s);}
if(close2>1){
s[n]=']';
p2(open1,open2,open3,close1,close21,close3,n+1,s);}
}
if(open3<close3){
if(open3>0){
s[n]='(';
p2(open1,open2,open31,close1,close2,close3,n+1,s);}
if(close3>0){
s[n]=')';
p2(open1,open2,open3,close1,close2,close31,n+1,s);}
}
if(close2==1 && open3==0 && close3==0){
s[n]=']';
p2(open1,open2,open3,close1,close21,close3,n+1,s);
}
if(close1==1 && open2==0 && close2==0 && open3==0 && close3==0){
s[n]='}';
p2(open1,open2,open3,close11,close2,close3,n+1,s);
}
}
int main(){
char *st=malloc(20);
p2(1,4,1,1,4,1,0,st);
}

dhamu.31954
August 03, 2013 but interviewer is looking for better then o(n+m)......better then this approach..there is one more approach which is 'improved binary partition'....this approach is fastest approach for searching element in sorted 2d array....
first we do binary search along either the middle row or middle column and find two element a1 and a2 such that a1< search element > a2 or we find required element if element is present in middle row or column
after this our problem divided into two subproblem
solve these subproblem recursively
for example we have to find 22 in following matrix
[1 14 25 35]
[2 16 28 38]
[5 20 28 40]
[16 22 38 41]
first we do binary search in middle row which is row 2
in binary search if we find required element then return,otherwise we find two element like 16< 22 >28 after this our problem divided in two sub problem
first
[5 20]
[16 22]
second is [25 35]
then we solve this two problem recursively
this approach is much faster
 dhamu.31954 July 26, 2013XOR all elements form given set, let say...X
and XOR elements form 1...n,let say..Y
then repeated element is = X(xor)Y
for example set is 1,2,3,4,4
X=1xor2xor3xor4xor4
Y=1xor2xor3xor4
and repeated element is=X(xor)Y=4
XOR all elements form given set, let say...X
and XOR elements form 1...n,let say..Y
then repeated element is = X(xor)Y
for example set is 1,2,3,4,4
X=1xor2xor3xor4xor4
Y=1xor2xor3xor4
and repeated element is=X(xor)Y=4
@ sK thanks i was also thinking about this case
my iretrative solution wrongly asume that mid point of combined string lies in mid point of LL ,which can,t give correct answer to your case(abcdef > ghihgfed > c > b > a)
in your example mid point of combined string lies in second node
which is not mid point of list so its does not give correct answer
but my recursive solution will work for this but it takes O(n) space due to recursion
i m try to modifie my iretrative soln to work for all case
thanks sK once again for this example because of this i find error on my code
i will back with update soln
we can reach mid point of linklist without knowing its size
just take two pointer fast and slow
initialy
struct node *mid(struct node *head){
struct node *fast=head
struct node *slow=head
while(fast>next!=NULL && fast>next>next!=NULL){
slow=slow>next;
fast=fast>next>next
}
return slow;
}
fast>next!=NULL condition for LL of odd number of node
fast>nex>nextt!=NULL condition for LL of even number of node
after this slow point to mid point of LL
Jay try to run above code post by me u will find it is working properly
 dhamu.31954 October 31, 2012yes u r right
a=y2y1
b=x2x1
no. of path is c(a+b,a)=c(a+b,b)
first reached at mid point
then reverse last half
then start comparing from head to last half reversed list
then again reverse last half to retain orignal list
try to run this code u will understand
now space complexity is O(1)
please comment if something seems wrong
with out recursion we have to reverse half list
following isolution is with out recursion
struct nodes *reverse(struct nodes *head){
struct nodes *p=NULL;
struct nodes *c=head;
struct nodes *n=head>next;
while(c!=NULL){
c>next=p;
p=c;
c=n;
if(n!=NULL)
n=n>next;
}
return p;
}
int checkpalindrom2(struct nodes *head){
char *r;
struct nodes *t=head;
struct nodes *s=head;
struct nodes *f=head;
int ri,li,a,b;
while(f>next!=NULL && f>next>next!=NULL){
s=s>next;
f=f>next>next;
}
s>next=reverse(s>next);
f=s>next;
li=0;
while(f!=NULL){
ri=strlen(f>c);
while(ri>0){
if((t>c)[li]!=(f>c)[ri1]){
s>next=reverse(s>next);
return 0;
}
ri;
li++;
if((t>c)[li]=='\0'){
t=t>next;
li=0;
}
}
f=f>next;
}
if((t>c)[li]!='\0'){
r=malloc(strlen(&(t>c)[li]));
strcpy(r,&(t>c)[li]);
li=0;
ri=strlen(r);
while(ri>li){
if(r[li]!=r[ri1]){
s>next=reverse(s>next);
return 0;
}
li++;
ri;
}
}
s>next=reverse(s>next);
return 1;
}

dhamu.31954
October 26, 2012 try to run following code u will get your answer
struct nodes {
char *c;
struct nodes *next;
};
struct nodes *newnodes(char *c){
struct nodes *temp=malloc(sizeof(struct nodes));
temp>c=malloc(sizeof(*c));
strcpy(temp>c,c);
temp>next=NULL;
return temp;
}
void pushs(struct nodes **head,char *c){
struct nodes *temp=*head;
if(*head==NULL){
*head=newnodes(c);
return;
}
*head=newnodes(c);
(*head)>next=temp;
return;
}
void prints(struct nodes *head){
struct nodes *t=head;
while(t!=NULL){
printf("%s>",t>c);
t=t>next;
}
printf("NULL \n");
}
int checkpalindrom(struct nodes **left,struct nodes *right){
static int a=1,b=0,ri=0;
int li,r;
if(right==NULL)
return 1;
b=b+1;
r=checkpalindrom(left,right>next);
if(r==0)
return 0;
li=strlen(right>c);
if(ba<0)
return 1;
while(li>0){
if(((*left)>c)[ri]!=(right>c)[li1])
return 0;
li;
ri++;
if(((*left)>c)[ri]=='\0'){
(*left)=(*left)>next;
a=a+1;
b=b1;
ri=0;
}
}
return 1;
}
void main(){
struct nodes *head=NULL;
struct nodes *left;
struct nodes *right;
//a>bcd>ef>g>f>ed>c>ba.
//a>bcd>efgf>edc>ba
pushs(&head,"ba");
pushs(&head,"edc");
pushs(&head,"efgf");
pushs(&head,"bcd");
pushs(&head,"a");
//pushs(&head,"zgy");
//pushs(&head,"ef");
//pushs(&head,"bcd");
//pushs(&head,"a");
left=head;
right=head;
prints(head);
printf("\n%d\n",checkpalindrom(&left,right));
prints(head);
}

dhamu.31954
October 26, 2012 its not going backward
first right pointer reached at end
till now left still pointing to head
after this compare
right>data to left>data
if not same return not a link list not palindrom return 0
if same increment (*left)=(*left)>next
return 1
after return 1 left pointing to 2nd node and right pointing to 2nd from last
and so on till ba>=0
'b' increment from 1
and ' a' decrement from n(number of nodes in list)
when ba=0 both left and right pointing to middle node
after this we do not need to do nothing simply return 1
this is the idea
this is my code to check palindrome
this is just modified version of checking link list palindrom which contain only one character per node
left=head ot LL
right=head of LL
int checkpalindrom(struct nodes **left,struct nodes *right){
static int a=1,b=0,ri=0;
int li,r;
if(right==NULL)
return 1;
b=b+1;
r=checkpalindrom(left,right>next);
if(r==0)
return 0;
li=strlen(right>c);
if(ba<0)
return 1;
while(li>0){
if(((*left)>c)[ri]!=(right>c)[li1])
return 0;
li;
ri++;
if(((*left)>c)[ri]=='\0'){
(*left)=(*left)>next;
a=a+1;
b=b1;
ri=0;
}
}
return 1;
}

dhamu.31954
October 25, 2012
Repjoycejflora, Android Engineer at ABC TECH SUPPORT
I am excited about cooperation and interesting projects. Last year I work for a person who provides the black magic ...
Repmanueladturner, Associate at Accenture
I am a content writer with years of successful track record of writing concise and factfilled content on different topics ...
Repmadan@kukooo.in, Analyst at Absolute Softech Ltd
I am a content writer with years of successful track record of writing concise and factfilled content on different topics ...
Open Chat in New Window
Step 1 : Create prefix sum array
Step 2: apply binary search to find reqired box
 dhamu.31954 July 15, 2016