There are situations in which you want to just get a right answer and ship, like at an early-stage startup. Then there are situations where the code you write

There are situations in which you want to just get a right answer and ship, like at an early-stage startup. Then there are situations where the code you write must play nicely within a massive, already-complex system, wherein it will work with potentially huge inputs. Like at Google. So, saying in a Google interview that you don't think Big Oh is super important, and that you prefer shipping whatever correct solution you come up with first and then worrying about efficiency if it ends up being slow, would likely not get you very far.