Bee
BAN USER
Questions (1)
Comments (3)
Reputation -5
- -6of 8 votes
AnswersGiven two Btrees. these trees "may" have right and left branches swapped. Now compare it
- Bee in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Trees and Graphs
Page:
1
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 vote
I have a completly different approach.
What I would suggest is to use Godel numbering to hold the array. we will have 2 Godel numbering. one for the positive numbers, and one for the negative ones.
The godel numbers will be created based on the position of the numbers in the array.
there are some issues in the solution, such as Godel number might grow exponentially with n, and also that if the numbers are not in N, this method won't work.
but still this is a cool approach, maybe someone can develop it a bit more.
Page:
1
CareerCup is the world's biggest and best source for software engineering interview preparation. See all our resources.
i am assuming the minimum sum of a sub array is negative or empty.
and that the maximum sum of a sub array is positive or empty.
the problem can be defined as follow:
1. Find the max sub sum
2. Find the min sub sum
if they do not intersect return their difference; otherwise check if the min sub sum is starting after the max sub sum:
[maxSubSumStart ---------- minSubSumStart ----------------MinSubSumEnd--------maxSubSumEnd]
I want to prove that if intersection is not allowed then either the left max sub sum or the right sub sum is the largest sub sum.
In this case each side of minSubSumArray is larger than the absolute value of minSubSumArray (otherwise their sum is below 0 and we would have taken only one part).
assume the left sub array is the bigger one.
That implies that it is also the biggest sub array in the array (because any other max sub array that wasn't added to the current max array, wasn't added because it is smaller (absolute value)than some minimum sub array, and therefore it is smaller then the minimum sub array and therefor smaller then the left and right parts of the maxsub array.
Therefore the result would be: max sub is the left side of the max array, and the min sub is the minimum sub array.
the same logic is true also in case the max array start in the middle of the min array
this is the code , i still need to do some re-factoring and also I might have some indexing issues:
- Bee October 27, 2013