>I still don't get why such questions are even asked as most jobs I've ever had not even remotely touched those and I've touched quite a few industries, technologies and types of companies.
I've had to work on tree traversal stuff multiple times in my life, anything low level GUI related will work with trees a ton.
I've also had to work with hash tables directly, and with memory caching layers.
I really should learn to write a proper parser, as I've had to write parsers multiple times now and they are always an ugly hack job.
Yep. In a project I’m working on at the moment (collab text editing), I’ve implemented 2 different b-trees, a skip list, 2 custom file formats and a dozen or so algorithms which do various graph traversals.
I get that this is uncommon, but if you scratch beneath the surface, most software (browsers, databases, compilers, OSes) are full of this stuff.
Even while I was consulting stuff like this would come up. At one company we were using a custom graphql wrapper around a CMS, and it was missing some functions we needed. The wrapper was implemented like a compiler from the cms’s data format to a set of query functions. Fixing it to do what we needed it to do was really hard and broke my brain a bit. But I did it. And I wouldn’t have been able to without understanding compilers and algorithms.
You can spend your whole career walking the beaten path adding features to apps and websites, and never traversing a tree at all. There’s lots of work like that out there. But if you ever want to go deeper, you’ve gotta understand data structures and algorithms. I know not everyone is suited to it, and that’s fine. But there’s definitely a reason big tech asks about this stuff.
> But if you ever want to go deeper, you’ve gotta understand data structures and algorithms.
I don't think this is quite right. I think it's more like:
If you ever want to go deeper, you've gotta be able to recognize when the problem you're solving fits a pattern for which good data structures and/or algorithms exist, and you've gotta be able to find, understand, and apply good reference material.
Solving this "knowing what you don't know" problem is the best and most important role of formal education, in my opinion. It's not as important to know a topic as it is to know that it exists, and some of the basic terminology necessary to get started researching it further.
Yeah I think that’s what I mean by “understand data structures and algorithms”. Or, I think your description is exactly what a useful working understanding looks like. You should know broadly what’s out there so if a problem comes up, you know where to look. (Would a hash table help? A priority queue? etc). And you should be skilled enough such that if you decide to use a red-black tree, you can find a good library or implement it yourself - with access to the whole internet as reference material. (And test it).
Nobody expects you to memorise a text book. But if an API gives you a list of items and you want to count the occurrences of each item, you should be able to figure out how to do that. And ideally in less than O(n^2) time if necessary. It’s surprising how many otherwise productive coworkers I’ve had who struggle with stuff like that.
But this isn't what the leetcode interview tests for. Reversing a binary tree, or figuring out how to arrange the parking lot to fit the most cars or whatever isn't a working understanding, it's essentially memorization. Being able to memorize something like that takes intelligence and dedication, so it does a pretty good job selecting for that, but it also filters out a lot of people who for good and valid reasons don't want to spend hours and hours studying. Not even doctors/lawyers do this: they do it exactly once and never again.
> isn't a working understanding, it's essentially memorization
Boring questions that you've seen before are memorization. But there's thousands of interesting questions out there that will never show up on leetcode.
Two examples from times I've been interviewed:
- One time my interviewer gave me about 15 lines of C code that used multiple threads and asked me if it was threadsafe (it wasn't). Then he gave me some threading primitive I hadn't seen before and asked me to fix it. Well, I had no idea what the threading primitive was so I was a bit stuffed. I asked him to explain it and he did, and then I (successfully) used it to solve the problem. He wanted to hire me, saying the fact that I hadn't seen that primitive before and still managed to figure out the answer within the interview impressed him more than anything else.
- Another time I was asked some more classic algorithm problem, where (in hindsight) the answer was clearly to use a priority queue. I didn't think of that, and under pressure I came up with some weird alternative in the interview. The interviewer messaged privately after the interview - he'd gone back to his desk and spent the next hour trying to figure out if my hairbrained idea would work, and he was as surprised as I was to realise it would. I told him I'd realised a priority queue was a good approach as soon as I walked out the door of the interview. I was offered the job.
I've never "crammed leetcode problems" in my life. I don't think thats what any interviewers are looking for. They're looking for people who can think on their feet and use DSA to solve real problems. AFAIK algorithm puzzle interviews predate leetcode. Algorithms have been used since the very early days of google and (I think) microsoft.
There's not a lot of difference between the algorithm interview and the leetcode interview--leetcode is just a story problem around some kind of basic algorithmic problem.
I've done multiple interviews where they use some site and you're expected to plow through 10 questions or whatever in 60 minutes. You can subscribe to the site to practice. Gazillions of employers use this site or one like it.
I agree that I think this is what most experienced people mean when they think of understanding data structures and algorithms.
The problem is that this kind of understanding is very rarely what coding interviews check for. They either don't check for this at all - instead just making sure people can write simple code while reasoning through a simple problems under time pressure - or they check for whether people memorized a textbook, looking for a specific non-obvious data structure and algorithm.
What I try to do, because I think it almost ticks all the boxes without asking for memorization, is ask questions that start with the simple "can you program at all" part, with follow up parts that end up in a place where we can have a conversation (without implementation) about how different tradeoffs could be improved, which often leads to discussing what useful prior art might exist.
Unfortunately I think this still has very high false negative issues. I've worked with people who prove to be perfectly capable of noticing when an appropriate data structure will make a big difference in their actual work, without that coming out in their interview.
My recommendation is to have a lot of different stuff in an interview, so you aren't making a final judgement on someone over any individual part of the interview. That means the candidate can stuff up one or more parts of the interview, and you can still get good signal.
For example, do all the things you suggest. Get them to write some simple code. Talk to them about an algorithm problem. Also, give them some simpleish code with some failing unit tests and ask them to debug the code. (This requires some prep, but its a fabulous assessment to do.) Ask them about their prior work. Just do everything you can think of, and don't give any specific part of the interview too much time or attention.
In my experience, this gives candidates a lot more opportunities to impress me. I don't really care if one person on our team is particularly weak on data structures. Its kinda better if we have someone who's an absolute gun at debugging, and someone else who's amazing at data structure work. That creates a better team than if everyone is impressive in the same way.
I think about time complexity and DSA all the time when programming. My personal view is that the people who claim it is unnecessary don't understand it and probably would be better off if they did.
I've seen lots of code that would be better if the author knew some basics. For example a report that took over half an hour to generate, I made a one-line change and cut the time to a few minutes - pretty sure I could have made it practically instant if I had taken the time to go through all of it.
And it's not like I'm some genius, I just understand the stuff I've been taught. Pretty sure most of my peers are supposed to have learned the same stuff, I think they just didn't really understand it.
In my experience, whether this is top of mind has a lot more to do with what people work on and with what tools than with level of understanding. For instance, in your example:
> For example a report that took over half an hour to generate, I made a one-line change and cut the time to a few minutes
In essentially all the work I've done in my career, this would be the result of expertise in SQL and the relational model, not in data structures and algorithms. I don't recall ever working on reporting code that isn't a dumb pipe between a SQL query and a mature library for writing CSV (or parquet or whatever). Sure, there are tons of data structures and algorithms on both the database server and client side, but that's not what I'm working on.
And I think this is pretty typical for people who mostly build "applications", that expertise in tools is more of a value-add than expertise in data structures and algorithms.
But having said that, I do agree with you that everyone benefits from these kinds of "fundamentals". Not just this, but also other fundamentals like computer hardware and systems, networking, etc. I think fundamentals are very useful, while also thinking that many people are good at their jobs without them.
In my case the processing was happening in our backend. I can't remember exactly why it couldn't be SQL, actually it's possible it could have been sql. But changing it to sql would have been a bigger change and this wasn't really the task I was working on, I just happened across it while doing something else.
I have also seen and fixed similar travesties where someone iterates through a huge list making one query per element, where it was fairly trivial to rewrite it to a swl join.
Point is just that understanding what you're doing is is valuable and in my mind DSA is a fundamental part of understanding what you're doing. Anyway I think we agree :)
Unsurprisingly we've now reached the perennial "is premature optimization actually premature" of it all :)
Would it have been better for the person who originally wrote that just-iterate-the-list implementation to have been thinking about data structures and algorithms that would perform better? Opinions on this vary, but I tend to come down on the side of: Optimize for human productivity (for both the writer and the many future readers) first, then profile, then optimize any bottlenecks.
My assumption when I come across something that turns out to be a performance bottleneck that is easy to fix with a better data structure or algorithm, is that the person who wrote that was consciously doing a simple implementation to start, in lieu of profiling to see where the actual bottlenecks are.
But I also understand the perspective of "just do simple performance enhancements up front and you won't have to spend so much time profiling to find bottlenecks down the line". I think both philosophies are valid. (But from time to time I do come across unnecessarily complicated implementations of things in code paths that have absolutely no performance implications, and wish people wouldn't have done that.)
> Optimize for human productivity (for both the writer and the many future readers) first, then profile, then optimize any bottlenecks.
I don't agree. The problem with this approach is that there are some optimisations which require changes to how data flows through your system. These sort of refactorings are much more difficult to do after the fact, because they change what is happening at the abstraction / system boundaries.
Personally, my approach is something like this: Optimise first for velocity, usually writing as little code as possible to get something usable on the screen. Let the code be ugly. Then show people and iterate, as you feel out what a better version of the thing you made might look like - both internally (in code) and externally (what you show to humans or to other software systems). Then rewrite it piece by piece in a way thats actually maintainable and fast (based on your requirements).
I've moved both ways along the continuum between these perspectives at different times. I don't think there is a single correct answer. I'm at a different place than you on it currently, but who knows where I'll be in a year.
Totally fair :) I have the same relationship with static typing. Right now I couldn't imagine doing serious work in a dynamically typed language, but who knows what I'll think in a year too. From where I'm standing now, it could be ghastly.
Actually I think you're misunderstanding me. I'm not saying you should profile and optimize all the code you write, I'm saying that a basic understanding of algorithms, data structures and complexity analysis allows you to write better code without any extra tools.
I didn't profile this report to find out why it took 30+ minutes to run. I just happened across some code, read it, saw that it was essentially two nested loops iterating through two huge (50-80k elements each) lists matching items by name, changed it to use a dictionary instead of the inner loop and that was that.
It's a trivial change, it wouldn't have taken any longer to write this the first time around. There is no excuse for doing this, it's just a dev who doesn't understand what they're doing.
That's my point. Understanding these fundamentals allows you to avoid these types of pitfalls and understand when it's okay to write something inefficient and when it isn't.
Traversing trees recursively is so trivial. I have to do this kind of stuff all the time. Just last week actually (in some frontend code no less).
Graph search and B-trees I haven't done professionally since I left college though. But it is still good to know the theory when dealing with databases.
A lot of these algorithms is more about knowing their characteristics than knowing how to implement them. For example cryptographic algorithms can be complex, but having a good lib and knowing each crypto algorithm characteristics is usually good enough for almost everyone.
Bingo. You forgot to add "with someone literally looking over your shoulder," though.
I've written AVL trees, B-trees, red black trees, and a bunch of other things people have named here. But, right now, without looking at any references, I couldn't even tell you how to balance an AVL tree, much less sit down and write out code for it.
That's why these interviews select for recent grads. Or leet code studiers.
Yes we've all done this in university. We've learned the theory. We had to write an implementation of this or that algorithm in whatever language the university made us use.
And we also know that great minds took a long time to come up with these in the first place. These "basic algorithms" are not something you think up in 5 minutes after first learning that computers exist or that some problem exists.
Bin packing algorithms are another such thing. Sure ask me interview "questions" like "please prove whether P=NP".
The exact same number of times I've been asked that during an interview: 0!
I do ask tree traversal questions when interviewing because I've had to traverse a lot of trees so I think being able to do an in order traversal of an already sorted binary tree (which is only a handful of lines of code) is fair game.
I've had to work on tree traversal stuff multiple times in my life, anything low level GUI related will work with trees a ton.
I've also had to work with hash tables directly, and with memory caching layers.
I really should learn to write a proper parser, as I've had to write parsers multiple times now and they are always an ugly hack job.