Advanced algorithms in google interview

SkedGo / Eng
UzlM34

SkedGo Eng

BIO
Leetcoding, solved 300 problems
UzlM34more
Jul 3 25 Comments

What should one prep for google interview in terms of advanced algorithms and ds?
Anyone can recommend a list of "should know" knowledge?

Failed Google on-site recently. Got asked a question related to segment tree.

Yoe 3, tc: shit

comments

Want to comment? LOG IN or SIGN UP
TOP 25 Comments
  • Alibaba Group vXQh35
    Hmmm - do you mind sharing a brief description of the questions? (Don’t provide the exact question due to NDA)

    I’m asking since you might be over engineering it. Maybe it’s just a tribal trie, or other basic DS/DP problem.
    Jul 4 4
    • Facebook Hodinkee
      Check also fenwik tree, it’s simpler
      Jul 4
    • SkedGo / Eng
      UzlM34

      SkedGo Eng

      BIO
      Leetcoding, solved 300 problems
      UzlM34more
      OP
      Thanks. will check it out.
      Jul 4
    • Facebook Hodinkee
      But this is a bad question for interview. Unless they are fine with linear solution and trade off between prefix sums vs naive calculation depending on ratio of updates and sumRange invocations.
      Jul 4
    • SkedGo / Eng
      UzlM34

      SkedGo Eng

      BIO
      Leetcoding, solved 300 problems
      UzlM34more
      OP
      Well I think the linear solution is like too easy, where the tree solution is too hard. I came up with prefix sum on the spot, but I think that's not enough.
      Jul 4
  • Nvidia Jfdfhj
    Google interviews were invented by idiots. Not surprisingly, as many other idiocy ideas, it has many followers. They also are trying to follow the ideas of that old fart Robert Martin, who thinks he is Confucius.
    Jul 4 3
    • Amazon / Eng batou
      which idea of Robert Martin is bad?
      Jul 4
    • Nvidia Jfdfhj
      That a software engineer must work 60 hours a week and be paid only for 40?

      In all his ideas he takes a moral stance peppering everything with stories about himself. It's his opinion how to be *righteous* devoted developer or architect. No wonder his books became a gospel. Because it's not science, it's preaching. This is why I compare him to Confucius. It's funny, some of his ideas come from his ADD. He probably even doesn't realize that. He doesn't care about being logical or base everything on science. It's all about the right public roar of support. He is too much like Trump. Check out his "WTF is monad".
      Jul 4
    • Amazon / Eng batou
      thanks for sharing
      Jul 4
  • Google jjack24
    Seriously doubt that using a segment tree was the easiest / intended solution. Can you elaborate on the question? Usually the hardest questions you will get from G will be Union Find, DP, or maybe some complicated bit manipulation.
    Jul 4 1
    • Google jjack24
      Yeah that question is very plausible, I admit I was wrong.
      Jul 4
  • Microsoft / Eng SwitchJobs
    Usually, on advanced algorithms, they don't ask hard questions. Most probably, plain implementation of segment tree would be sufficient. I mean lazy propagation and variations of segment tree won't be asked.

    It's always good to be equipped with Segment tree, Binary Index tree and Tries. To be extra cautious, suffix trees and arrays. Other than this, if asked, Good Luck!

    Bdw, how were your other rounds? What type of questions were asked?
    Jul 3 1
    • SkedGo / Eng
      UzlM34

      SkedGo Eng

      BIO
      Leetcoding, solved 300 problems
      UzlM34more
      OP
      Thanks. I believe other rounds are fine, not great. It starts with a medium problem, I arrive at the optimal solution then code it. No time for follow ups
      Jul 4
  • Goldman Sachs / Eng BePostive
    Which level?
    Jul 3 4
    • SkedGo / Eng
      UzlM34

      SkedGo Eng

      BIO
      Leetcoding, solved 300 problems
      UzlM34more
      OP
      L3/l4
      Jul 3
    • Goldman Sachs / Eng BePostive
      I don’t think they generally ask these advanced DS. I haven’t heard anyone asked a DS more advanced than a Trie! I have tons of friends who work at Google and another bunch who recently interviewed at google! Probably, you had a hard luck!

      P.S.- I cleared Google on-site last week! I have 3 YOE!
      Jul 4
    • Alibaba Group vXQh35
      ^ did you get L3 or l4?
      Jul 4
    • Goldman Sachs / Eng BePostive
      Just started the Team Matching stage. Haven’t gotten an offer yet!
      Jul 4
  • New / IT aove
    Usually segment tree, trie, and udfs. And always prepare for dynamic programming for google
    Jul 4 2
    • Facebook Hodinkee
      What’s udfs?
      Jul 4
    • SkedGo / Eng
      UzlM34

      SkedGo Eng

      BIO
      Leetcoding, solved 300 problems
      UzlM34more
      OP
      I guess he means UFDS which is union-find disjoint set.
      Jul 4
  • New tey
    YOE?
    Jul 3 1
    • SkedGo / Eng
      UzlM34

      SkedGo Eng

      BIO
      Leetcoding, solved 300 problems
      UzlM34more
      OP
      3
      Jul 3
  • Snowflake Computing jIMo27
    Focus on dp and greedy style.
    Jul 4 0
  • Google mtwn38
    Can you iterate through an array without turning it into a complicated mess? It's what the 99% do day to day anyway, and it eliminates a surprising amount.
    Jul 4 0

Salary
Comparison

    Real time salary information from verified employees