Google onsite problem concern

Sep 14 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?

comments

Want to comment? LOG IN or SIGN UP
TOP 35 Comments
  • Google hioki
    Lol
    Sep 14 18
    • OP
      Why does me obsessing about an onsite spark such bully-like responses from you? Just calm down and be nice. Sheesh.
      Sep 14
    • Facebook ⭕w⭕
      My bad, I should just have just written "lol" like the other guy and mock you instead of trying to give you advice.
      Sep 14
    • OP
      lol isn’t a mocking response. It’s just an expression about the absurdity of the situation. You’re a douche buddy. Just stop.
      Sep 14
    • Facebook ⭕w⭕
      haha ok buddy, whatever helps you sleep at night.
      Sep 14
    • Nuage Networks / Eng
      NoDrama

      Nuage Networks Eng

      PRE
      Apple
      NoDramamore
      Oh man, LeetGrind Chill!
      Sep 14
  • Facebook ⭕w⭕
    You need to chill and just let them take it from there.
    Sep 14 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 6
    • Facebook / Eng mturtle
      That was really painful. Everyone else is just trolling you, and I actually tried to help you, and I told you the solution. And you kept arguing with me in DM until I block you.

      You probably did the same thing to the google interviewer. That looks really bad to the HC. You need to get a fucking grip.
      Sep 14
    • OP
      Look at my dms. Your code assumes only one parent. Your solution is for a binary tree, not a DAG. If you weren’t so arrogant you wouldn’t just end the conversation but have seen my follow ups explaining that. Numbskull.
      Sep 14
    • OP
      I even wrote examples that your code isn’t accounting for (nodes with multiple parents) and you just arrogantly filter it out. Your solution is literally irrelevant but you insist on it and cut off any conversation because I didn’t immediately agree with you. I’m sure you won’t respond since it’s clear you solved for a binary tree and your defensiveness about your “solution” looks pretty lame now.
      Sep 14
    • Amazon TRuc81
      What’s the problem? I’m curious
      Sep 14
    • Microsoft
      Lincoln!

      Microsoft

      PRE
      Google
      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 16
  • 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 2
    • OP
      If I tell you the problem you'll understand. The output can't be shrunk. Dm'ed you.
      Sep 14
    • Nutanix slashetc
      DM the problem? Just curious.
      Sep 14
  • 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 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 15 1
    • OP
      I got along well with my interviewer though. I just find some folks on here arrogant. Is what it is.
      Sep 15
  • 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 0
  • New / Eng
    xoogler420

    New Eng

    PRE
    Google
    xoogler420more
    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 0