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/find-the-maximum-sum-path-in-a-binary-tree/>
.
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;
}
#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[j-2]==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;
}
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*N-1 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(sum-i,i+1,k-1);
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 zig-zag manner starting at top right corner. O(max(m,n))
3) if both m and n large use 2D binary-search 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);
}
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 .
Can "Aho–Corasick_string_matching_algorithm" be used here ?
- singhsourabh90 January 29, 2013