aravind646
BAN USERuse level by level traversal n update an array of data values as Darray; and when moving from one level to another set the iterator of the Darray to 1 and sum up with the old value in that array!
- aravind646 November 10, 2010Only the counter example given by soron is wrong, but the solution is correct!
- aravind646 November 09, 2010perfect =)
- aravind646 November 09, 2010This becomes more interesting if -ve numbs are allowed in the input.
Use 3 min-heaps for each of the lists. And check whether the topmost elements sums up to 0.
P.S: this works only if the arrays are sorted, if not you should heapify at the start O(nlogn).
The smallest of n numbers can be found with n − 1 comparisons by conducting a
tournament as follows: Compare all the numbers in pairs. Only the smaller of each
pair could possibly be the smallest of all n, so the problem has been reduced to that
of Þnding the smallest of n/2 numbers. Compare those numbers in pairs, and so
on, until theres just one number left, which is the answer.
To see that this algorithm does exactly n −1 comparisons, notice that each number
except the smallest loses exactly once. To show this more formally, draw a binary
tree of the comparisons the algorithm does. The n numbers are the leaves, and each
number that came out smaller in a comparison is the parent of the two numbers that
were compared. Each non-leaf node of the tree represents a comparison, and there
are n − 1 internal nodes in an n-leaf full binary tree (see Exercise (B.5-3)), so
exactly n − 1 comparisons are made.
In the search for the smallest number, the second smallest number must have come
out smallest in every comparison made with it until it was eventually compared
with the smallest. So the second smallest is among the elements that were compared
with the smallest during the tournament. To Þnd it, conduct another tournament
(as above) to Þnd the smallest of these numbers. At most lg n (the height
of the tree of comparisons) elements were compared with the smallest, so Þnding
the smallest of these takes lg n − 1 comparisons in the worst case.
The total number of comparisons made in the two tournaments was
n − 1 + lg n − 1 = n + lg n − 2
in the worst case.
Source: CLRS :)
can u explain why you are using "a[0] < a[1]" ?
- aravind646 November 06, 2010frm example:Sbig = "hello what are you doing"
Ssmall= "eo"
answer is "ello"
max=count=0;
while(Sbig[i]!=null)
{
while(Sbig[i]!=' ')
{
if(Ssmall[i]!=Sbig[i])
i++;
else
{
count++;
while(Ssmall[i]!=' ')
{
count++; // similarily we can track the starting n ending positions of the subset along wid the elements
if(Ssmall[len]==Sbig[i])
{
max=count;
break while loop;
}
i++;
}
}
}
max=count=0;
}.
@zhizhi2007
ban such hectic morons frm this wonderful website!!
i agree wid this sol. LL is the best way to solve tis question! tat was a nice suggestion :)
- aravind646 November 03, 2010the solu is correct, just modified a little
maxweight(currNode)
{
if (currNode== NULL)
return 0; // provided no negative weights are given in the tree
if (currNode.weight > maxWeight(left)+maxWeight(right))
return currNode.weight;
else
return maxWeight(left)+maxWeight(right);
}.
@Krishna
no point in writing this code, given tree is not a BST.
Morons!!
definitely greater than O(nlogn)
- aravind646 November 02, 2010you moron, read the question "don't use substring"
- aravind646 November 02, 2010hashing is the best method (if collision avoidance is implemented effectively) as lookup operation if required will be of O(1) but whereas binary tree has O(log n) for the same operation + time to scan and load from the disks.
- aravind646 November 02, 2010ur code fails fr the array {-3,-7,-1,-1}
it shld return -2, but here its 0.
Its a DP problem,
let,
a[j]->given array
m[j]->max value array
m[j]=max(m[j],m[j-1]+a[j])-------> O(n)
call it recursively and scan m[] to get the maximum---------> O(n)
@ramu: think it twice before posting!!
- aravind646 September 23, 2010any solution of solving this 'in place'?
- aravind646 September 23, 2010Algo seems to be OK till the 6th step. But in the next step, how will u identify the root for the corresponding siblings if the tree gets bigger??
- aravind646 September 23, 2010stop pasting bunch of codes! Algos r better!
- aravind646 September 23, 2010select salary,deptid from employee where salary=(select max(salary) from employee where salary<(select max(salary) from employee
where salary<(select max(salary) from employee)))
just tried! Correct me if i am wrong :)
O(n) can be reduced in some cases by splitting the array in to (n/2) and check whether the first < (n/2 + 1 th) element and continue in the second part if it is true or do the same in the first part of the array
tis might reduce O(n)!!
-->if(currNode.getLeftPointer()!=null){
- aravind646 November 10, 2010columnSum(currNode.getLeftPointer(), a, collevel-1)<--
when the 1st child is encountered the collevel is set to -1 and as you can see the root collevel was set to 0.