4 ms·
This is the thing with algorithms and leetcode and the like; I've got about ten years of professional experience, and in all of my career (CRUD apps, full stack
by Cthulhu_ 6y ago
This is the thing with algorithms and leetcode and the like; I've got about ten years of professional experience, and in all of my career (CRUD apps, full stack; sounds boring but I've touched many different industries) I've NEVER had to think about what data structure to use.
Java's ArrayList was good enough in all cases, as was HashMap. Although one interesting thing, ConcurrentHashMap turned out to be faster in all my (bad) benchmarks.
I'm doing Go nowadays, it does not have generics except for its built in lists (arrays/slices) and maps, and that covers 99% of my use cases as well.
Anyway, I'll never work at Google or any company that does leetcode interviews because it's so far removed from (my?) reality.
- ALittleLight 6y agoI've been leetcoding recently and I feel like most leetcode problems have similar requirements to what you describe vis a vis data structures. I've been focusing on Medium difficulty, maybe it's different on hard, but I've been doing the occasional hard too and not noticed it. The problems mostly seem to be about realizing what algorithm you'll need and implementing it. I actually solved a problem recently that I thought would require a QuadTree, and after implementing one and solving the problem I was proud of myself until I looked at the other solutions and realized I didn't need a QuadTree at all. In my notes I recorded the problem as a likely fail, because if I were the interviewer I'd take unnecessary complexity as a red flag. Part of me, I think, just wanted the chance to implement a QuadTree.
- w1nk 6y agoI never enjoy seeing this line of argumentation pop up when we (as the computing industry) discuss practicalities of data structures and algorithm choices. I've got a bit over twice your time in the industry and one of the things that is still very clearly on an upward walk is the size of our N's (think big O) in all of our applications and across all of our data structures. I'm not sure what kinds of applications you're building, but if any of your collections contain on the orders of thousands/10s/100s thousands of items, you really should be considering the impact of how you shape that data for consumption inside your application. You hint at the need to do so, arraylists being good enough until they're not and then hashmaps, etc. I think there is a pretty reasonable line between expecting our engineers and peers to pick proper containers for the data they're consuming without stepping over into purely 'academic' territory. Shutting down the discussions with 'well I've never had to use this' feels a bit icky and not a great way to advance any of the conversation.
- pjmlp 6y agoI think it is crucial to understand data structures and algorithms, more so than whatever way they exposed in each programming language, as Nicklaus Wirth puts it, Algorithms + Data Structures = Programs. However I fully subscribe to not care to apply to companies that disregard professional experience in name of clever leetcode answers, completely irrelevant for the position one is applying for.
- bartread 6y agoI tend to agree even though most of the time for me array like structures are often "enough". The thing is it's the 10%, the 5%, or the 1% of the time where you really see the benefit of using those structures. Many years ago I worked on the early versions of an autocomplete app called SQL Prompt. It needed to be able to filter 1000s, 10000s, or 100000s of items to make completion suggestions without interrupting your typing. It still remains the only time in my 20 year career I've had to implement a trie, but it was absolutely the right data structure for that job. Similarly I've used various kinds of tree and graph structures, different hashing schemes, and all kinds of other pointer - and even bit encoded - structures at different points in my career. It's very much in the minority of the work I've done, to the point where I definitely wouldn't do that well in an off the cuff leetcode interview, but I know what I need to look up when I come across a problem that might require a slightly more adventurous data structure or algorithm, and I've no qualms about using them. People act like picking the right algorithm or data structure up front is too much effort or will take too long, and (this really grinds my gears) casually trot out that tired line about premature optimisation. You know what really takes too long? Figuring out why the system you spent 3 years building runs like absolute garbage in production when all your customers and stakeholders are screaming about it, and you're haemorrhaging sales because of it.
- nmfisher 6y agoData structures are funny, because most of the time they're (a) the last thing you worry about (after feature specification/architecture/implementation/etc), and (b) it's usually pretty obvious which data structures you to use (and which to avoid). In other words, comprehensive knowledge of data structures won't be needed in 99% of the average career, no matter which company you working for. Leetcode doesn't prove you're a good hire, it's just a lazy way of screening out bad hires (because the average applicant who can complete leetcode is going to be more competent than the average applicant who can't). I can understand why big companies (Google scale) use leetcode in hiring - they want a scaleable method that filters out the bad candidates while leaving enough good candidates to pass through. When you have 1000+ applicants for a job, you just need to trim the pool down to a manageable number of good candidates. As long as you end up with 20 good candidates, you don't care that you inadvertently screened out a further 100 good candidates in the process. I still don't think it's an optimal method for hiring, but I at least understand why they do it.
- mypalmike 6y ago> comprehensive knowledge of data structures won't be needed in 99% of the average career, How does one write software professionally without a solid grasp of data structures?
- nmfisher 6y ago...by doing what thousands of people do around the world every day (and what OP was referring to) - using the List, HashMap, Stack and Queue implementations provided by your language of choice. Occasionally, you might need to dig deeper to find an appropriate data structure for your specific use case (maybe something more exotic like a suffix or binary tree), but that's already pretty uncommon. Implementing a data structure from scratch? For the vast majority of developers, it's basically unheard of. One exception to this though, IMO, is dynamic programming - while it's not something that someone like a web developer will need to know, it crops up so often once you go beyond that that I think it's a reasonable expectation (though not necessarily in a whiteboard scenario).
- rottc0dd 6y agoI am not a comp science guy, and I just know next to nothing in case of either data structures and algorithms. But, knowing how and why the data structures work can help you when slapping the code does not work. We had a code base maintained for almost 5 years that has to deal with one type of representation of data to another. The result form allows keeping combining two data points with some differences i.e. calls and arguments. The combining the nodes and finding the differences happens as last step. It was just too much hassle to deal with comparison because, the initial form does not have much complexities but resultant form has much more complex datatypes. And we have to compare it with all potential things that could match. The complexity is inherent to the problem of comparing final representation. Maybe it is obvious to other people here, but when I saw how the hashmap works, I was blown away. It is not just about having any datatype as index, it is about how efficiently you can find the index. It was about REDUCING THE EQUALITY CHECK. Because, it is costly, particularly when you are dealing with very deep tree nodes. That is where hash comes in. So, we traversed the nodes once and created a signature of the structure that cannot be made into arguments and some other metadata determining its type i.e. hash. And we introduced an intermediate representation for effective comparison that is hybrid of initial and final representation. That sped things up so much. Now almost all the work of five years has to be thrown away. I think such things exist in almost all projects. You would not know you need it, until you need it. Edit: Added a point.
- kragen 6y agoYesterday and the day before I wrote this eco-logical simulation: http://canonical.org/~kragen/sw/dev3/qabbits http://canonical.org/~kragen/sw/dev3/qabbits It's fairly simple: "qarrots" spawn nearby qarrots and get eaten when a "qabbit" collides with them; qabbits die if they get too hungry or old; qabbits in a certain age range colliding with each other spawn more qabbits; qarrots and qabbits inherit some attributes with slight mutation, so regional variations develop over time; and so on. I tweaked the parameters so that it's interesting to watch and neither the qarrots nor the qabbits dominate. This is not highly advanced software engineering, and if you've never wanted to do something like this, there is something wrong with the way you are living your life. But the very simple O(NM) collision-detection scheme I'd used the other day to implement Space Invaders was too slow. With even a few thousand qarrots and a few hundred qabbits, I could only simulate like 4 time steps per second, which is ridiculous even given that JS in the browser is not the most performant platform. So now I'm doing a little bit of sorting ("broad-phase collision detection") to cut down on the number of object-to-object collision tests needed, and now performance is around 12–24 time steps per second, which makes the simulation way more fun. But faster would be better. I can afford about 15000 object–object collision tests per time step and still hit 60 time steps per second, but my simpleminded sorting algorithm is only cutting it down to about 20k–80k hit tests per time step, which is still a good improvement over four million or whatever it used to be. I think that, if I use a grid ("spatial hash") and maybe update it incrementally, I should be able to hit 60 time steps per second. If I could get to higher numbers like 1000 or 10'000 time steps per second, I'd be able to see the impact of changed simulation parameters much more quickly. Alternatively, I could run much larger simulations, which might give rise to qualitatively different behavior—if the simulated world is too small, the qabbits tend to wipe out all the qarrots and then die out themselves. ArrayList and HashMap and the Golang intrinsic containers don't really help much here. You probably don't need generics to solve it. But you do need to think about what data structure to use. Your years of professional experience avoiding such problems and posting anti-intellectual comments about how ignorance is just as good as knowledge, well, condolences, but you aren't going to convince these rectangular bunnies to simulate faster.