gXa's blog

Who will win?

By gXa, history, 7 years ago, In English

This is one of Interview Question.

You are given the string of a's and b's, eg. aaabbbaa and some threshold value t which indicates the threshold point, eg if count of a's or count of b's will become equal to t then whose count will be equal to t eg. a or b will win that match, and next game will continue further, eg from that index of a and b new count values will be incremented, and the process will continue, and at the last you have tell who won the match, a or b.

Expected time complexity: O( n*log(n)*log(n) ).

  • Vote: I like it
  • -4
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Why not O(N)?

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

    Yes, I also thought the way that just maintain count of a and b and then check for threshold and later initialise the counts of a and b again( also increment the winner and at the end choose the winner ).

    However, I have seen two-three links which propose it to do using dp and binary search, so I thought I am missing something crucial.

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

      I think you may be missing something crucial in the problem statement rather than the solution. The solution you have given is fine for the question you have given. However, I suspect the problem may be harder than the one you have described.

      Would you care to share any sort of link for the problem please?

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

        Link

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

          Thanks! Heh, I wouldn't worry too much about it then :) It doesn't seem like that interesting of a problem anyway. I am trying to think of solutions with that complexity and it seems just stupid.

          If you want to take something from this, maybe consider a problem with updates to the array, and you query the answer within a range, given that T is small.

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

            Thanks man.

            Red Coder _/\_

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

              I don't know how to arrive at O( n*log(n)*log(n)), as the statement did not mention what n is.

              But if you were to tweak the problem and instead have multiple queries with non-fixed t, then you can have a solution with dp and binary search.

              → Reply