Google onsite problem concern

Sep 14, 2019 35 Comments

So I was asked a problem (the 2nd of the round) for which i came up with an N^2 brute force solution, which based on an internet search and my own logic, is the most optimal one (as the output itself is of size N^2, and theres no way of shrinking the requested output even if it were allowed). I coded it quickly at the request of my interviewer.

My interviewer then asked me to optimize in the last 5 minutes, and I mentioned that I dont think we can improve theoretical complexity due to the size of the output, but I obliged by giving another approach (that ultimately would be the same efficiency) and my interviewer rightly pointed out the new approach still has an inefficiency.

I know G interviewers sometimes ask NP-hard problems just to gauge a candidate’s thought processes, but this was a pretty clear-cut N^2 algo as the output itself could be up to N^2 in size. I’ve yet to hear feedback, but if I hear that one round was weak or not great, can I pass a note to my recruiter to give to HC? Or should I just hope HC realizes that brute force was the only way to go due to the size of the output?


Want to comment? LOG IN or SIGN UP
TOP 35 Comments
  • Google hioki
    Sep 14, 2019 18
    • Facebook ⭕w⭕
      haha ok buddy, whatever helps you sleep at night.
      Sep 14, 2019
    • Nuage Networks / Eng

      Nuage Networks Eng

      Oh man, LeetGrind Chill!
      Sep 14, 2019
  • Facebook ⭕w⭕
    You need to chill and just let them take it from there.
    Sep 14, 2019 0
  • Facebook / Eng mturtle
    Short answer is no. You cant give the recruiter a note and expect it to be passed to hiring committe. If the other interviews went well, you will still pass HC.

    You can increase performance of a system without lowering complexity. From what you described, that may have been what they were after.

    IE: computing n factorial using recursive is same complexity as iterative, but iterative is faster.
    Sep 14, 2019 6
    • Amazon TRuc81
      What’s the problem? I’m curious
      Sep 14, 2019
    • Microsoft


      Lincoln! more
      @LeetGrind just an advice for you! I learnt this in the hard way. Never argue with an interviewer. Try to explain your solution to them and don’t argue. After all whatsoever review he/she submits the company will believe the review more than any follow up email you sent to the recruiter. So just chill the f out and know that you will meet so many arrogant interviewer along the way and if you keep arguing with them it’s always an L on you.
      Sep 15, 2019
  • Bloomberg / Eng F.U. money
    I’ve gotten fucked over by interviewers way worse than that before and there was nothing I could do about it.

    Besides, are you certain that there wasn’t a repetitive pattern in the output?
    Sep 14, 2019 2
    • OP
      If I tell you the problem you'll understand. The output can't be shrunk. Dm'ed you.
      Sep 14, 2019
    • Nutanix slashetc
      DM the problem? Just curious.
      Sep 14, 2019
  • OP
    I’m open to chatting about specifics by dm. I think it’ll become pretty clear there’s no where to go with optimization.
    Sep 14, 2019 0
  • Google hioki
    I personally could care less if a candidate solved a problem perfectly. This thread has plenty of red flags that if shown in an interview will be grounds for a no-hire.
    Sep 14, 2019 1
    • OP
      I got along well with my interviewer though. I just find some folks on here arrogant. Is what it is.
      Sep 15, 2019
  • Microsoft GdXH25
    You should have asked the interviewer what type of optimization?

    If the answer is n^2, time complexity can not go lower than that, are you looking for
    1. optimizing steps by avoiding repetitive (storing few outputs) or unnecessary (ex alpha beta pruning) work
    2. Optimized in way like quick sort is better than merge sort (worst case time complexity is larger for quick sort but average run times are better)
    3. Optimize memory

    Can you DM me question and your solutions?
    Sep 16, 2019 0
  • New / Eng

    New Eng

    If the output is N^2 then N^2 is the best you can do time-wise, perhaps you could have optimized your space complexity?

    Or you could have done some constant time optimizations?

    Nobody here knows unless we see the problem and your solution...

    That said sometimes the interviewers are just jerks, when I did an onsite at G, there was this moronic Indian guy who was looking at his computer the entire time (somehow I still got in, but yeah, very unpleasant).
    Sep 15, 2019 0


    Real time salary information from verified employees