techInterview Discussion

Hi all, I came across this problem in a book and couldn't solve it. I know the obvious answer that takes O(n^2). Is there any other solution that can solve the problem in O(n)?

Basically we have a sequence of real numbers (positive and negative), we have to find a minimum positive sub sequence.

for example:

1 3 -5 6 Minimum positive subsequence is: -5, 6

1 5 8 -7 3 6 Minimum positive subsequence is 8, -7

Thanks in advance.

n log n is reasonably straightforward. I suspect this is optimal for algorithms that can be translated into an algebraic decision tree.

Please be more specific.
When you say subsequence do you mean not-necessarily-contiguous, or must it be contiguous?
What is a positive subsequence?  One that sums to a positive number?
What is minimal?  Minimum length? Minimum sum? One that cannot be contracted?

I mean contiguous subsequence that sums to a least possible positive value. The length of the subsequence can be as long as the size of the given sequence it self, but the sum of the subsequence should be minimum positive value.

hope this pseudo code helps in understanding the problem...


minSum = 0;
for(i=0;i<n;i++)
{
  subSum = 0;
  for(j=0;j<i;j++)
  {
    subSum+=a[j];
  }
  if(subSum>0 && minSum>subSum)
    {
      minSum = subSum;
    }
}
return minSum;

@d.

Yes, Omega(nlogn) is correct. Element distinctness raises its head again. I will leave the reduction to you.

Why isn't 1 a minimum positive subsequence for each example?

Sincerely,

Gene Wirchenko

Hello,
pardon my ignorance,
What is the O(nlogn) approach to solve this problem..
thnx

@Gene Wirchenko

Yeah, I am sure 1 is minimum positive sub sequence in both the examples I posted as are -5,6 and 8,-7 .  I am sorry to say that they are not solid examples, but I tried to come up with some example to give the idea.....


Some seem to suggest that O(nlogn) is a optimal solution, but please can some one explain in more detail. May be some hints will be helpful. Pseudocode would be really helpful.

Note: This is not any of my homework problems or any thing like that, I am trying to solve this problem out of my interest and sooner or later I will solve this problem.

The key to an O(n log n) algorithm is that given a sequence

x(1) x(2) x(3) ... x(n)

we compute partial sums

y(0) = 0
y(1) = y(0) + x(1)
y(2) = y(1) + x(2) = x(1) + x(2)
y(3) = y2 + x3 = x(1) + x(2) + x(3)
...

so that x(i) + x(i+1) + x(i+2) + ... + x(j) = y(j) - y(i-1). We now are trying to find y(i-1) and y(j) such that i <= j and y(j) - y(i-1) > 0 is minimized, which can be accomplished e.g. by inserting each y value into a balanced binary search tree and determining its predecessor among previously inserted values. I don't know how to reduce the storage requirement from Theta(n) without increasing the running time.

The reduction from element distinctness is in essence to apply the reverse transformation (there are some technical but straightforward details that I don't care to sort out at the moment).

(If we make some assumptions about the representation of the input numbers, then e.g. van Emde Boas trees can be used to answer the predecessor queries in o(log n) time.)

@d

thanks a lot :)

http://www.carsinsurancecompanies.com/ car insurance 075 http://www.free-home-insurance-quotes.net/ cheap homeowners insurance 8-PP http://www.homeinsurance4u.net/ home insurance =-OO http://www.getaffordablehealthinsurance.net/ new york health insurance 117077

http://www.healthinsurancemate.com/ cheap health insurance 8-)) http://www.slotsguidance.com/ slots 001954 http://www.carsinsurancecompanies.com/ state auto insurance :DD http://www.getcheaphealthinsurance.net/ cheap health insurance pfc

http://tramadol911.com buy tramadol szl http://viagracomparisons.com/ buy viagra cheap =D http://weightlosspillsonline.org/ buy acomplia bxuush

http://tramadol911.com/ besked buy hjemmeside navn tramadol cccmpt http://viagracomparisons.com/ buy viagra >:-PPP http://weightlosspillsonline.org/ acomplia :-))