singhsourabh90
BAN USER 0of 0 votes
AnswersGiven a Binary Tree (not BST) with integer values . 1) Find path from root to any node with max sum. 2) As there can be many path's find all of them. 3) Print all such paths.
 singhsourabh90 in India
Do this in O(n) : n is number of node's in tree. he wanted an O(n) solution not O(n)+O(n) ie. u can't traverse tree twice . Report Duplicate  Flag  PURGE
Amazon Software Engineer / Developer Algorithm
Let size of A is m and B is n
1) Put all values of B in std::set() . O(nlogn)
2) Check all values of A in the set(). one by one O(mlogn).
overall : O(max(nlogn,mlogn)).
No.
2
/ \
1 4
/ / \
3 3 4
here : max is 6: 2 paths . 2,4  2,1,3
 singhsourabh90 January 19, 2013seems wrong still
 singhsourabh90 January 19, 2013@drv
please read problem statement again . your solution is not doing what is needed.
this is an entirely different problem. do not get confused.
<http://www.geeksforgeeks.org/findthemaximumsumpathinabinarytree/>
.
some issues :
1) you can traverse tree only once .
2) you'll print some path's multiple time .[paths which don't end at leaf . u'll print them for both child branches ].
3) you are not supposed to print 'L' 'R' array. [as u are consedering strcpy() O(1) . which is actually O(n) ]
making your algo O(n^2).
your solution find's only max sum . (1) of problem . what about (2) and (3) ?
 singhsourabh90 January 19, 2013#include <iostream>
#include <vector>
using namespace std;
void Generate(string s)
{ int64_t all=(1LL<<s.size()),i,j;
for(i=0;i<all;i++)
{ printf("(");
for(j=0;j<s.size();j++)
{ if((1LL<<j)&i) printf("%c,",s[j]);
else printf("%c,",'*');
}
printf("\b)\n");
}
}
main()
{
string s="abcd";
Generate(s);
system("pause");
return 0;
}

singhsourabh90
January 11, 2013 #include <iostream>
#include <vector>
using namespace std;
bool is_valid(vector<int> a)
{ int n=a.size(),i,j;
if(n&1) return false;
for(j=3;j<n;j+=2) if(a[j2]==a[j]) return false;
else return true;
}
vector<int> pre_row(vector<int> a)
{ int i,j;
vector<int> ret;
for(i=0;i<a.size();i+=2)
while(a[i]) ret.push_back(a[i+1]);
return ret;
}
main()
{ int b[]={1,3,4,1,1,3};
vector<int> a(b,b+sizeof(b)/sizeof(int));
for(;a.size()>1;)
{
if(is_valid(a)) a=pre_row(a);
else break;
}
puts(a.size()==1?"Valid":"InValid");
system("pause");
return 0;
}

singhsourabh90
January 11, 2013 b=a+++a is not undefined :
a+++a is (a++) + a.
as compiler's follow greedy approach to get operator . hence a+++a is a++ + a and not a + ++a
you are missing the fact that :
if only down and right move's are allowed then you can cover atmost . 2*N1 box for NXN matrix.
if we have already sorted the array . then why we need to do binary search then ??. can't we linearly move from front and back.
 singhsourabh90 July 20, 2012// Another simple code :
#include<iostream>
using namespace std;
int c=0,n;
int sum_set(int sum,int i,int k)
{ if(i>n+1) return 0;
if(k<0) return 0;
if(k==0)
{ if(sum==0) { c++; return 0; }
else return 0;
}
sum_set(sumi,i+1,k1);
sum_set(sum,i+1,k);
}
main()
{ int k;
scanf("%d %d",&n,&k);
sum_set(n,1,k);
printf("%d\n",c);
system("pause");
return 0;
}
 singhsourabh90 July 20, 2012number of solutions are possible :
1) if min(m,n)==1 use binary search.
2) if min(m,n)<<small linear search in zigzag manner starting at top right corner. O(max(m,n))
3) if both m and n large use 2D binarysearch O(log(n)*log(m))
% can't be used on float. so given code won't compile .
 singhsourabh90 July 19, 2012yup , there is a name it's called Young's tableau.
 singhsourabh90 July 18, 2012we can color the graph using BFS and stop at any point if we find it's not Bipartite
 singhsourabh90 July 18, 2012// this shud work :
void ftoa(float num, char *str)
{
int intpart = num;
int intdecimal;
int i;
float decimal_part;
char decimal[20];
memset(str, 0x0, 20);
itoa(num, str, 10);
strcat(str, ".");
decimal_part = num  intpart;
intdecimal = decimal_part * 1000000;
if(intdecimal < 0)
{
intdecimal = intdecimal;
}
itoa(intdecimal, decimal, 10);
for(i =0;i < (PRECISION  strlen(decimal));i++)
{
strcat(str, "0");
}
strcat(str, decimal);
}

singhsourabh90
July 18, 2012 sort the 100 word's :
create trie of sorted words :
now create a function which :
1) take's input word sort's it.[ make a copy of word if changing original is not allowed .]
2) search word in trie
3) return's true or false accordingly .
Open Chat in New Window
Can "Ahoâ€“Corasick_string_matching_algorithm" be used here ?
 singhsourabh90 January 29, 2013