joe kidd
BAN USER- 1of 1 vote
AnswersYou are given an array, that is sorted, however was rotated to the right by a certain distance. The array may contain duplicated values. Find the index of a given element in the array.
- joe kidd in India
Example: {3, 9, 9, 9, 8, 10, 12, 13, 1, 2, 3}, element = 3, returns, any of indexes that 3 is present.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm
Why not to consider this as Bernoulli trial, where:
1/M - probability of single success (that a value goes to a single slot)
i - expected numbers of success (the success = the value goes exactly to the same slot)
N - numbers of tries
1 - 1/M - a probability of failure:
So then having a Bernoulli trial formula where (N i) stands for binomial coefficient:
P(i)=(N i) * (1/M)^i * (1 - 1/M) ^(N - i)
There is another solution that works as following:
Array = [6, -1, -3, 4, 5, 4, -15, 7] then create another array that for position i - keeps the sum of all elements from [0, i] so that we get something like
SumArray = [6, 5, 2, 6, 11, 15, 0, 7]
Now by looking in the SumArray we can see that:
1) when 0 appears at i-position it means that from the begining of the array till i-th position we have a "zero sequence".
2) if there is a matching (two the same elements, like 6, 6 in our case) then we know that from [i+1,j], where i is the first and j is the second matching, the overall change was equall to zero, so we have a "zero sequence" again.
I think it's not correct as in your case it seems like every path in the tree should start in the root of the tree. I guess print_path_with_sum is the first function to be called, and it start counting the sum from this place. But what if the sum starts later let's say having a following binary tree (you didn't mention it's binary search tree so will keep it just as binary tree) and you look for sum 5?
Obviously the sum is there but looks like 2, 3, and doesn't start from the root. The solution to this problem is described in Cracking Coding Review book AFAIR.
- joe kidd August 19, 2013