Longest increasing subsequence
People at FANG, if an interviewee comes up with O(n^2) solution for the problem quickly, but couldn't come up with O(nlogn) at all, will it he hire or no-hire for you? I came up with O(n^2) solution quickly for the direct problem and the indirect russian envelopes problems in leetcode.. but, could not come up with that clever O(nlogn) solution at all.. i had to look at the solution. Am I competent enough for interview purpose atleast? Or, would you expect me come up with O(nlogn)?
So while I’m admittedly new (only 3 total YOE) this would be neutral to slightly negative. In my opinion anyone who makes it to that stage should be able to solve the brute force solution.
O(n^2) is not brute force for this problem.. O(2^n) is brute Force
O(n^2) is pretty close to brute force. Start at first point, keep going until you are no longer increasing. Start at second point, keep going until you are no longer increasing. Do this for third, fourth, fifth, etc. Return the longest one.
Did you mean FANG or FAANG?
A definite “No Hire” for Albertsons. They need O(logn)
The interviewer doesn't choose hire / no hire at least at G. The hiring committee would see feedback from all interviews to decide.
From the question, it looks like it was asked to you at Amazon. Its a no hire if it was the single coding question in that round. While preparing for FNG, it is quite expected to know this stuff. Unfortunately.
This depends on how the conversation with interviewer go. I’ve passed candidates who can only code brute force but was able to drive the conversation to the optimal solution with in-depth analysis throughout and crystal-clear communication.
I like to evaluate ones problem solving technique. Not how good at memorizing leedcode. If you have never seen the question before yet be able to solve it even just brutal force. That will be a positive datapoint for me.
Thanks.. 🤗