gXa's blog

Maximise The Product
By gXa, history, 8 years ago, In English

This is one of the interview question.

Given row on N house, each is marked either R or B and each house having some gems.

You have to collect gems from these house with some constraint: You can choose gems from any blue house but you have to choose even number of red house ( either from 2 Red houses or from 4 red houses)

Each time you take gem from one house, you will multiply gems received with gems currently, you have. 

You have to choose continuous houses and maximise the product.

You have to return start point and end point of house (remember this should be continuous ).

I can think of O(N^2) solution but not better than that. So, can someone recommend a better algorithm.
  • Vote: I like it
  • +1
  • Vote: I do not like it

»
8 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

Since you want to maximise the product, you would like to take as many gems as possible. Ideally you want to take all the gems. So there's 2 case, if there is even number of red house, then just take from the first to last house. If not, then take the maximum of either starting after the first red house and ending at the last house or starting at the first house and ending before the last red house, and we are done. So this is O(n).

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Now what if we allow -ve or 0 gems too( I know its bit difficult to imagine -ve gems but still :P )?

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 7   Vote: I like it +1 Vote: I do not like it

      0 is easy. Just split the houses to left and right of it, and do the algo above and return the max of both and zero.

      For the negative part: instead you need to loop through starting at 4 points and get the max. So you would start at the first point, start at the next point with odd number of red houses passed and odd number of negative, even number of red houses passed and odd number of negative, and odd number of red houses and even number of negative. for each iteration, when there are even number of red houses and even number of negative in the 'set', update the maximum. then we will have the right answer.

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it +6 Vote: I do not like it

        Can you elaborate a bit for -ve part , maybe show what needs to bedone at each iteration?

        → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
          ← Rev. 2   Vote: I like it +3 Vote: I do not like it

          Do I get a job offer for this? I happen to need one :P this code is for each iteration.

          Code
          → Reply
          • »
            »
            »
            »
            »
            »
            8 years ago, # ^ |
              Vote: I like it +6 Vote: I do not like it

            Thanks a lot. I myself in search of job.

            Hopefully you will get it and that asap :)

            Just confirming this code has to be executed for all the 4 cases u provided above( just starting point changes as above ).

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              8 years ago, # ^ |
              ← Rev. 3   Vote: I like it +1 Vote: I do not like it

              np and thank you.

              Yes. To summarise, first find all zero and split the houses. Then for each partition, do the above. actually you can remove the if statement neg%2==0 in case your answer is really negative. and finally from all return value of the partition, get the max of them and zero(assuming there is zero)

              → Reply