Longest increasing subsequence

Marvell martiality
Jul 16 24 Comments

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

60 VOTES SELECT ONLY ONE ANSWER
VOTE VIEW RESULT

comments

Want to comment? LOG IN or SIGN UP
TOP 24 Comments
  • Oracle / R&D TLead
    A definite “No Hire” for Albertsons. They need O(logn)
    Jul 16 2
    • Marvell martiality
      OP
      I thought they need O(1)
      Jul 16
    • Oracle / R&D TLead
      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
    hashset

    Apple Eng

    PRE
    Amazon
    hashsetmore
    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
    economyded

    Apple

    PRE
    Amazon
    economydedmore
    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
      economyded

      Apple

      PRE
      Amazon
      economydedmore
      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
      economyded

      Apple

      PRE
      Amazon
      economydedmore
      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
    • Google / Eng hooli.xyz
      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
    • Google Gigamisu
      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
    • Google Gigamisu
      Atleast the algo/coding round is sort of that way. It tests if you know the common and some uncommon programming paradigms . And can you relate it to the given problem.
      It's not a test of intelligence purely.
      Jul 16
  • Google / Eng hooli.xyz
    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.
    Jul 16 0