n00gler's blog

By n00gler, 4 weeks ago, In English,

Google Kick Start hosts online rounds throughout the year, giving participants the opportunity to test and grow their coding abilities while getting a sample of the programming skills needed for a technical career at Google. Top candidates might be invited for interviews.

I invite you to solve some fun and interesting problems on Jul 28 2019, 05:00 UTC.

Dashboard can be accessed here during the contest. Problem analysis will be published soon after the contest.

 
 
 
 
  • Vote: I like it
  • +22
  • Vote: I do not like it

»
3 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

Bump, less than 12 hours to go!

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it -12 Vote: I do not like it

    Please tell what I asked you earlier.

    upto what ranks candidates are invited for interviews.

    and is it true that if u don't perform well in 3 kickstarts google puts u on hold ?

    • »
      »
      »
      3 weeks ago, # ^ |
      Rev. 2   Vote: I like it +14 Vote: I do not like it

      n00gler is a problem setter. He does not take recruiting decisions and pestering him with such questions does not make sense. There is no fixed number of candidates called for interview from each contest, it is variable over contests according to the requirement.

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it -15 Vote: I do not like it

        what about my 2nd question of max 3 kickstarts?

        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
            Vote: I like it +11 Vote: I do not like it

          Was the previous comment unclear ? He and least of all I don't have that perspective. It's fruitless to ask questions about how ranks for certain contests get used for recruiting. Get in touch with some Google APAC recruiter and shoot your doubts to them.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Bump! Contest has started. Link in original text.

»
3 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I can't enter the contest since half an hour ago. Does anyone have the same problem?

P.S. Everything works fine now

»
3 weeks ago, # |
Rev. 2   Vote: I like it +19 Vote: I do not like it

Solved 0 :)
How to Solve X or What???
I try Segtree with lazy propagation, i think i made it over complicated :)

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    An interval is xor-even if and only if the total set bits of all numbers in the interval is even.

    So if the whole array has a total of even set bits, answer is N.

    Otherwise you discard first number with odd set bits and everything before it, or last number with odd set bits and everything after it.

    • »
      »
      »
      3 weeks ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      JeffreyHo how can you prove that interval sum must be even set bits?

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Let x be set bits count in 'a' and y be set bits count in 'b', then number of set bits in a ^ b will be x + y — 2*(no of sets at same position in both 'a' and 'b'), this will be even only if a + b is even. we can generalize it for more than two bits in same way.

        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
            Vote: I like it -6 Vote: I do not like it

          ok. thanks! how much you solved today?

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    Only the elements having odd number of set bits will make non-xor-even interval. Having even number of these is not an issue though. If there are odd number of such elements, you must exclude one of these (from the extreme end). You can do this using a set. This is the brief idea.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone tell me why I am getting wrong answer on first question. Solution link.

My approach —

(even ^ even) -> even

(odd ^ odd) -> even

(even ^ odd) or (odd + even) -> odd

where even and odd are the parity of the count of the setBits of a number. So, If the whole array contains even number of odd parity elements then the answer will be n , otherwise we have to remove some prefix or suffix from the array such that the resulting subarray contains even number of odd parity elements.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone explain how to solve 2nd problem?

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Where can I find the problem analysis of past kickstart rounds?

  • »
    »
    3 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    i don't think there are editorils of too old kickstarts like 14 , 15. but you can find of 2018 and 2019 till round c. open problem. you can find two columns. problem and analysis. click on analysis

    2017 are also available

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Where can we find some editorial for this round.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    The analyses have been uploaded :)

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it -16 Vote: I do not like it

      Easy round overall :)

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How would one go about solving Problem C — Food Stalls, if two dimension was involved i.e, X and Y coordinates were given in input, insted of one dimension ?

      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        For current problem, i had following observation

        Let i be the index of position where warehouse is located for our minimum cost arrangement.

        then for all j 1<=j<i the cost was decreasing i<j<=n the cost was increasing

        Hence I applied ternary Search on the position of Warehouse such that our cost is minimum.

        Talking about 2 Dimension We can do similar thing as the curve would be a bell shaped curve Hence apply ternary search in 2 Dimension to fetch the optimal position of warehouse and then calculate the cost.