Mike_Vernik's blog

Google | Phone Screen

By Mike_Vernik, history, 5 years ago, In English

I was being interviewed 4 hours ago and here it is.

Spoiler

The solution must be O(n) Time.

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

Comments Comments (12)
| Write comment?
»
5 years ago, # |
← Rev. 2   Vote: I like it +57 Vote: I do not like it

Not quite convinced an $$$O(N)$$$ solution exists.

By the way, identical problem is already on Codeforces. https://mirror.codeforces.com/problemset/problem/526/F

.. and I know two solutions both of which are $$$O(N \ log \ N)$$$

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

    The problem you mentioned is of 2900 rating and still its NlogN. I highly doubt google will ask such hard problems in phone interviews. As far as I know with my friends their questions revolves around div2 c,d and max e. mostly its c,d. Also in phone interviews their is a high change of geeting a seen leetcode problem.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 2   Vote: I like it -10 Vote: I do not like it

      about >= 2900 not appearing, you cannot be too sure, right? It's the Google! Considering the complexity of Code Jam, I doubt if their problems are mostly simple.

      The only thing that shocks me is this kind of problem happens during a phone interview!!! Maybe he got on the interviewer's nerve, who knows :v !

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

        Nope, he's right. Google interviews are lot easier than Code Jam problems. You can do a quick search for similar problems if you want. I'm not sure about problem ratings but it shouldn't be harder than Div1B in the worst case.

        Source is da web, a few friends and my experience.

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

        The $$$O(N\ log\ N)$$$ solution is considered 2900. The $$$O(N)$$$ solution could be considered a paper xD.

        → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it -109 Vote: I do not like it

    Who upvotes just by seeing red color?

    This problem is one dimensional and the one in codeforces is 2 dimensional.

    Anyway your $$$O(N log N)$$$ is like $$$O(sqrt(N) log (N))$$$ for this problem.

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

      People didn't upvote because he's red. People upvote because he's correct.

      A 2d NxN grid with N objects where no 2 objects share a row or column is the same thing as a 1d permutation.

      Tip: someone with 800 rating points above you is likely to be correct, don't make such a bold claim without thinking.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it -66 Vote: I do not like it

        My bad. I didn't read further after seeing NxN.

        → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +81 Vote: I do not like it

Apparently it is possible to do this in O(n):

Link to one Chinese blog post on this

Chinese slides on this

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

    Can someone explain the main ideas in English?

    → Reply
»
5 years ago, # |
  Vote: I like it +35 Vote: I do not like it

So it's this all over again?

→ Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it +5 Vote: I do not like it

Can someone explain O(nlogn) approach for this problem?

Edit: The best explanation IMO : https://abitofcs.blogspot.com/2015/05/codeforces-526f-pudding-monsters.html

→ Reply