Data structures and algorithms I actually used while working at tech companies

I've used quite a lot of features from RDBMs, as well as topological sorting, LRU for caches, Unicode normalization, graph traversal, bloom filters, hash maps and so on.

I'm not payed to implement algorithms or data structures, but to solve problems. So for anything non-trivial I tend to use ready-made libraries.

I only implement stuff myself when it's faster and simpler to implement AND TEST it than to draw in another dependency, or if there isn't a well-made off-the-shelf component.

So what I've implemented myself at $work is pretty limited:

* depth-first tree traversal

* graph traversal

* parsers for various non-standard file formats

* maybe a topological sort once, not sure

Finally, many classical algorithms have lesser-known variants that optimize for some practical advantages (reduced memory usage, memory cache friendliness, sequential disk reads/writes etc.). So if I were to implement, say, a substring search, it might not be a by-the-book Boyer-Moore algorithm, but some subsequent paper that builds on it to add a few percent practical performance improvement.

Still, that was a hobby project, I've never had to implement anything similar at my regular job.

[1]: https://github.com/mihaifm/HIBPOfflineCheck

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 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.

Is this really a useful exercise? Why not present them with an actual problem that is relevant to your field and see how they approach it?