That's a big red flag, at least in a Google setting.

The reason is because when your dataset is in the petabytes, any algorithm bigger than O(N log N) is not going to terminate. You're not going to get any answer at all; your MapReduce is going to sit there burning CPU time for a day, and then you'll kill it, and you won't have any idea what went wrong. (This is learned from experience, if you couldn't tell.)

In a startup context, I'd certainly agree with you - that's exactly the approach I'm taking with my startup, where I'm doing a lot of the debugging and code-wrangling on my local laptop after verifying that the data I want exists and calculating its size with a couple cloud-computing passes. It can sometimes be useful to prototype & iterate with a small subset of the data until you've got the algorithms down.

But many of the algorithms Google cares about don't give any useful results on small data sets. I remember running a few collaborative-filtering algorithms and finding that they gave zero answers because within my small sample of 0.01% of the total data, nobody liked anything else that anybody else did.

In my experience as a Google engineer, this is mostly false. None of the work I or any of the people I know well at Google is on petabyte datasets; most people just aren't on the hot path of indexing/websearch/youtube. In fact almost none of the stuff I was asked about in my interview has been relevant to my work. I have thought about complex algorithms two or three times in the past year.

Not only that, but (in my experience as a Google engineer), factors relating to the location of data (distribution and disk vs ram, etc.) often greatly outway algorithmic performance. Constant factors often dominate variable factors.

Exactamundo! Cache/memory/disk locality dominates almost all other factors[1] unless you're doing something very special. (Speaking as a non-Google person who also likes to think that he knows what he's talking about.)

[1] Well, it's really the amazing amount of throughput that modern architectures can achieve. Latency hasn't improved quite as much given the inescapable limitation of the speed of light.

What department? I was in Search and used that knowledge all the time, and also did rotations on GWS, Google+, and GFiber. Certainly I used less of that knowledge for GWS (where everything you need is in-process) and for GFiber (where I was working on marketing & customer signup - the job req for this was actually different, and both interviews & job duties were much more like a traditional SWE job in other companies). But even Google+ needed a lot of algorithmic complexity knowledge; G+'s scaling needs are similar to Twitter's, and we know how that went.

Perhaps it has changed as well; when I left (2014) they had just started encouraging engineers to focus on one particular task, with the architecture already defined, while when I started (2009) there were still a number of problems of the form "here's a feature we want to add; here's the data we have available; how can we build it?"

I'm on Ads and Commerce front-end, and I also know a number of people on Android. These of course are mostly constrained by users' devices, so don't have the scale your talking about. But I also think the trend you're talking about of smaller roles has been continuing and has a lot to do with it as well.

Everyone loves to put Big-O up on a pedestal, however many times the constant costs can outweigh the rest of the algorithm. Cache access times in particular can be brutal for non-linear access patterns.

> What about when you know what the concept of big O is, know why it's often touted as important, and disagree that it's as important as it's touted?

What if you're ​having a conversation with someone about local politics and you're convinced the local zoning rules don't encourage growth in the way they think they do. Do you force the subject of conversation so you can make sure they know just how wrong they are? Not if you want them to walk away having a good impression of you.

Instead if the talk turns to zoning you put out feelers to see if they'll want to talk about the larger issue, and only engage in the conversation if it seems like the time for it.

The analogy isn't perfect, but if the interviewer wants to talk about the larger issue, you're probably well matched and will have a great interview. If not, and you know enough about runtime complexity to discuss the tradeoffs, then you know enough to just answer the textbook big-O question and move on.

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.

> What about when you know what the concept of big O is, know why it's often touted as important, and disagree that it's as important as it's touted?

Let's say you created your own company and you're interviewing engineers.

Would you be comfortable hiring someone who doesn't know the difference between O(n^2) and O(2^n)?

Or someone who doesn't even know what these concepts represent?

I've always called this kind of thing "trying to get the sizzle before the steak". You gotta have a steak first; get that, then work on cooking it - then work on cooking it to perfection if that is what is needed or wanted.

There's also the thing I picked up from playing around with graphics demo coding; get the algorithm working first, even if it takes 10 seconds per frame. Then look for the slow parts, concentrating first on the inner loops. Whatever you do, don't try to prematurely optimize the code as you write it, as tempting as it may be. Because almost certainly you'll make things worse than if you waited until after you have a working first pass.

This applies to way more than just fast graphics code, of course.

The questions about BigO isn't about premature optimization or actual implementation. It's about understanding exactly what a particular program is doing and how it's doing it.

Any sort of technical solution given at a Google interview would generally have the following questions:

1) What big O time does this algorithm run in? Why? What big O space requirements does it take.

2) If space were more/less expensive, or time more/less important, how would you change the solution and why?

Understanding those tradeoffs and being able to analyze code at that level is a big part of most software engineering jobs.