# Longest increasing subsequence

Marvell martiality

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)?

VOTE VIEW RESULT

A definite “No Hire” for Albertsons. They need O(logn)
Jul 16 2
• Marvell martiality
OP
I thought they need O(1)
Jul 16
O(1) if you are applying for senior position. Wait you have experience? Then it’s a definite No for Albertsons. You should be sad for yourself for failing Albertsons
Jul 16
• Apple / Eng
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.
Jul 16 1
• Apple
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.
Jul 16 8
• Oops, my b. I still think that in order to get "average" or higher rating in an interview, you need to either get optimal solution or give some of your ideas that are close to it.
Jul 17
• Apple
Isn’t the solution to this problem just to sort and then process it? Doesn’t seem that hard
Jul 17
• Marvell martiality
OP
@apple...the question is not to find subset.. it is sub sequence.. original order is to be preserved.. but not continuous
Jul 17
• Marvell martiality
OP
Using regular DP, it takes o(n^2).. Using the tail table approach, it take o(nlogn)
Jul 17
• Apple
Ah, the version I found online must have been the wrong one. Still, I would expect you to find the optimal answer or at least be close.
Jul 17
• Pinger / Eng create💻
The interviewer doesn't choose hire / no hire at least at G. The hiring committee would see feedback from all interviews to decide.
Jul 16 2
• Marvell martiality
OP
Ok.. would the HC person say hire or no hire for this solution?
Jul 16
Not exactly true. We can make H/NH recommendations but its up to HC to agree with our recommendations or not.
Jul 16
• Salesforce cornholioo
Did you mean FANG or FAANG?
Jul 16 0
• Microsoft / Eng SwitchJobs
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.
Jul 16 4
• Marvell martiality
OP
Unless one has seen that solution before, do you think one can come up with that solution during interview on the fly?
Jul 16
Nope, but the expectation is that you have seen most of the common classes of problems
Jul 16
• Marvell martiality
OP
@Google, so it is numbers game? The more questions/solution s I see(and understand), more do I have the chance of clearing the interview.. It has less to do with intelligence, if not none.. is that right? I am trying to get a perspective
Jul 16