Блог пользователя Mike_Vernik

Google | Phone Screen

Автор Mike_Vernik, история, 5 лет назад, По-английски

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

Spoiler

The solution must be O(n) Time.

  • Проголосовать: нравится
  • +38
  • Проголосовать: не нравится

»
5 лет назад, # |
← Rev. 2   Проголосовать: нравится +57 Проголосовать: не нравится

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

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

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

→ Ответить
  • »
    »
    5 лет назад, # ^ |
    ← Rev. 3   Проголосовать: нравится +22 Проголосовать: не нравится

    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.

    → Ответить
    • »
      »
      »
      5 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится -10 Проголосовать: не нравится

      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 !

      → Ответить
      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится +15 Проголосовать: не нравится

        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.

        → Ответить
      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится +12 Проголосовать: не нравится

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

        → Ответить
  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится -109 Проголосовать: не нравится

    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.

    → Ответить
    • »
      »
      »
      5 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится +42 Проголосовать: не нравится

      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.

      → Ответить
»
5 лет назад, # |
← Rev. 2   Проголосовать: нравится +81 Проголосовать: не нравится

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

Link to one Chinese blog post on this

Chinese slides on this

→ Ответить
»
5 лет назад, # |
  Проголосовать: нравится +35 Проголосовать: не нравится

So it's this all over again?

→ Ответить
»
4 года назад, # |
← Rev. 3   Проголосовать: нравится +5 Проголосовать: не нравится

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

→ Ответить