I'm not at all opposed to companies like Google, Facebook, etc asking Algorithms, Data Structure and Big O related questions. Why? It's very applicable to problems at their scale. That being said, not all engineers there work on such problems.

If I'm asked to do a BFS/DFS, Tree traversal, etc for a small company.. I tend to share high level how I'll solve it then basically not actually code it up and say something like "This is pretty tricky...". Why? It's my way to exit the interview quickly because I question the ability of the company to hire talented engineers. Especially when I test your product out and see all sorts of inconsistencies.

Okay, so when do Data Structures matter to a company?

Are you building a product that needs to perform very efficiently at scale and the system is doing something outside the "norms" of what a data store can provide. Examples: Facebook's TAO system and their type ahead search.

Read the design paper for TAO and you'll see how they use very primitive data structured related to Graphs. Their typeahead system also makes use of some very basic data structures and some probabilistic data structures as well.

When do Algorithms matter to a company?

For most traditional companies, you're not going to do a BFS/DFS search, traverse a tree or a Dynamic Programming solution like Levenshtein distance. So unless these algorithms have a practical use case in your company, you're just creating a sort of monoculture.

Once again, Google and Facebook do apply these algorithms so I respect their interview process.

Big O has its place in such large companies. I think most people fail to understand the purpose of Big O; identify upfront if a solution will be sufficient from a time or space perspective as the data grows. Most people speak about Big O on interviews AFTER they code up the solution. You should do that before you code it up.

e.g, So the data for this problem is <100 items then this quadratic solution would work, but if we scale the data set up to say 10,000 items then it won't work. Then you can look at data structures or sorting algorithms for instance that'll help you get it down to say O(n) or O(n log n) etc

Look, I get the frustration a lot of people feel about this sort of interviewing process. I have a very non-traditional background and it could be very scary when you first start learning about this. My advice? Learn it for your own good. It'll make your a better programmer and it'll help you become more aware of so many things you weren't aware of before!

The moment when you realize why using an array for a Min Heap or why a Min Heap must be a complete tree... you'll step back and go "Now that's sexy!" Or when you realize even stupid stuff like "A balanced binary Tree has this weird reality that the leaf nodes account for 50% of all nodes in the tree" It's just fun if you see it in a positive way.

Let's call technical interviews that ask such questions when it doesn't represent the company "interviewer imposter syndrome". When a company tries to act and look like Google early on.. Google has a million+ candidates a year interviewing with them. They MUST allow good candidates slip through their process.