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?
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.
I really don’t think there’s much room for runtime improvement with the problem. I dm’ed you if you’d like to chat a bit
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.
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?
If I tell you the problem you'll understand. The output can't be shrunk. Dm'ed you.
DM the problem? Just curious.
I’m open to chatting about specifics by dm. I think it’ll become pretty clear there’s no where to go with optimization.
Lol
Hehe, it’d be funnier if it weren’t so important :(
It's funny because you seriously put a Google interview on a golden pedestal.
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.
I got along well with my interviewer though. I just find some folks on here arrogant. Is what it is.
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).
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?
You need to chill and just let them take it from there.