Find the equilibrium point
Find a point in an array where sum of left side array members(wrt to that point) and right side(wrt to that point) are equal..in other words equilibrium point.
[AMAZON] Vertical sum of nodes
Given a Binary Tree, find vertical sum of the nodes that are in same vertical line. Print all sums through different vertical lines. Examples: 1 / \ 2 3 / \ / \ 4 5 6 7 The tree has 5 vertical lines Vertical-Line-1 has only one node 4 => vertical sum is 4 Vertical-Line-2: has only one node 2=> vertical sum is 2 Vertical-Line-3: has three nodes: 1,5,6 => vertical sum is 1+5+6 = 12 Vertical-Line-4: has only one node 3 => vertical sum is 3 Vertical-Line-5: has only one node 7 => vertical sum is 7 So expected output is 4, 2, 12, 3 and 7
SL[i] = sum of numbers from 0 to i (i.e. running sum from left)
ReplyDeleteSR[i] = sum of numbers from n-1 to n-i-1 (i.e. running sum from right)
You can build the above two SR,SL in O(n) by doing simple scans from left and right respectively.
Now again do another O(n) check to see if there is an x such that SL[x] = SR[n-x-1].
@Wrick so for every i ,you will find out SL[i] and SR[i] which is o(n) so overall it will take o(n^2).we need less than that.
ReplyDelete