I am a fairly experienced programmer (10 years) and have always worked with startups building prototypes and getting products to product-market fit. I have worked in all kinds of languages Java, C#, Ruby, Elixir. However, I am not good with data structures and algorithms. What do you reckon I should do in order to get good? Any books, tutorials, course, etc that have helped you?
For me implementing the data structure and it's operations made the difference between shallow and deep knowledge. There are a lot of data structures and I did not see anyone post a basic list so let me provide one, because once you know what you should seek things will be much easier.
Data structures:
- linked list (single,double)
- array list
- hash map with different implementations
- binary tree(and tree traversing, depth/breadth first search)
- red-black tree
- self balancing tree
- stack
- heap
- queue
- set (with funny set operations like intersection)
- B and B* tree
Read about their strengths and weaknesses.
With every data structure comes operations. More or less the same with a few speciality but their implementations are vastly different. You should try to implement the same operations at every data structure:
- Find an element
- Find min/max
- Add / delete an element
- Sort the data
Take time to implement the standard sorting algorithms for a list to understand the speed implications: quicksort, bubblesort, heapsort, radix sort, bucket sort
If you look for other algorithmic challenges I suggest checking out graph algorithms. Dijkstra and A* are the most famous.
Depends on do you want to learn DS & Algo for job interviews? Or are you genuinely interested in adding tools in your tool belt.
For the first you learn about a couple common paradigms like dynamic programming, some graph algo & ds like BFS/DFS, shortest path algorithms, backtracking etc... and just do a lot of leet code problems. The more of these you do, the better you get at them, because most of them can be solved faster by knowing techniques (like using two pointers at either end for some array based problems) etc...
For the second one, you try to learn about the landscape of DS & Algo. For example, i know about the existence of red black trees, why they were invented, types of problems you can solve with them, but i won't be able to implement them from memory or without using references (even then it might take me a while). For the second type of learning, i would just do CLRS chapter by chapter, or watch any of the numerous algorithm courses on youtube from MIT, Stanford, ArsDigita. The second type of learning lets you understand and gain an appreciation for the tools you use everyday as a developer. For example, studying B-Trees will let you appreciate how rdbms are able to retrieve information so fast.
Ideally, a good developer would be well versed in DS & Algo landscape and be able to solve leetcode problems fast, but i think #2 is more necessary to becoming a better developer, although #1 helps more in the job market.
Thanks! this is really helpful. I want to both - crack interviews where DS & Algo is considered very important as well as go in depth and learn them. Such companies which give a lot of importance to DS are the ones who actually use it (Amazon fulfillment - for example)
Focus on the structures, leave the algorithms for later. Seek out and study the papers, and build each data structure one by one. You'll know you understand it when you can build it, when you can see its structure. There's a master key hidden embedded within the structures too. Pieces of the key are distributed among them, waiting for its fragments to be connected. Its secrets revealed and retrieved by a select few. One of the secrets you'll discover on this quest is this: Once you get the structures, you get the algorithms for free.
Hundreds of the best papers have been posted on Hacker News over the years. Some of the rare gems too. Look through people's posting history for inspiration. And use Google Scholar [1]. At some point you may discover you're searching Google Scholar more than you're searching Google Proper.
1.) Go to https://leetcode.com It's a whole community built around algorithms and data structures.
2.) Pick an easy problem.
3.) Code it naively/brute force it just to get it 100% correct.
4.) Check the Discuss tab, sort by Most Posts and read the solutions and comments.
5.) Every time you hit a wall or encounter a new term (like space/time complexity, dynamic programming, binary tree etc) find a video on YouTube that explains it really well. Not enough? Ask community, consult a paper or a book.
6.) Go back to 2.) until you're ready for the next level.
Don't let your own mind sabotage you by telling you that 'this is not real world programming', 'this is for college kids'. Embrace it and you'll find it sort of interesting like solving a hard puzzle in a point & click adventure video game.
And if you're even more motivated, upsolving previous contests problems.
Codechef long contests are really interesting for this: after thinking a lot about these problems during more than 1 week, reading the editorial and trying to apply by yourself the idea seems to me an excellent way to learn.
If you want to prep for interviews, it may be most efficient to look through lots of hacker rank problems and learn them in an ad-hoc function, looking up solutions online after you've tried them. If you actually want a good understanding of fundamental data structures and algorithms, I very much recommend reading Cormen et al. First 4 sections (17 chapters) plus Chapter 22 (Elementary Graph algorithms) are the absolute essentials (obviously some people may have some small level of disagreement with this but I think it's fairly accurate). By then you'll have enough knowledge to skim the introductions of the other chapters and decide whether you care about reading them now or just keep the basic premise of what that chapter addresses in the back of your head so if something requiring it comes up later you'll know you can refer back there.
Edit: hah, I type very slow on my phone evidently. strikelaserclaw's advice here is very similar to this :)
I'll recommend: Data Structures and Algorithms in Python by Goodrich et. all, they've also done this series in Java and C++ but I am only familiar with the Python version. It has a great balance in terms of covering everything you need to know in terms of fundamental ADTs, asymptotic complexity, etc. but without the rigorous math in CLRS. Because Python is so concise, every data structure and algorithm is fully implemented.
My only con is that the answer key doesnt seem to be available.
Read books; follow the worked out examples very closely until you completely understand them. Then try programming it on your own from your understanding and memory. You have to put in the time and effort. I suggest studying books where complete implementations are given in a language of your choice and only later studying books with pseudo-code (i.e. go from specific to general). Also the chosen language should be simple without obscuring the core logic in OO/Functional syntactic sugar and structure (C is ideal here). The following are a few chosen books from my collection (used copies of all can be had for cheap online);
1) Data Structures and Program Design in C by Kruse, Leung and Tondo.
2) Algorithms in C (Parts1-4 and Part5 two-volume set) by Robert Sedgewick.
3) Compared to What? An Introduction to the Analysis of Algorithms by Gregory Rawlins.
4) How to think about Algorithms by Jeff Edmonds.
5) Advanced Data Structures by Peter Brass.
Finally, study the ideas, concepts and techniques behind the C++ STL library to see how to design Data Structures and Algorithms in a clean and independent manner and yet can couple them as reqd. in myriad ways for actual usage.
I did read this in college 12 years back. It did get me excited back then. But then I guess I did not get into putting those algorithms into practice when I first started working (working in smaller companies, building simple web applications). I think it will be a good idea to go back to it and start again. Thanks!
Data structures:
- linked list (single,double)
- array list
- hash map with different implementations
- binary tree(and tree traversing, depth/breadth first search)
- red-black tree
- self balancing tree
- stack
- heap
- queue
- set (with funny set operations like intersection)
- B and B* tree
Read about their strengths and weaknesses.
With every data structure comes operations. More or less the same with a few speciality but their implementations are vastly different. You should try to implement the same operations at every data structure:
- Find an element
- Find min/max
- Add / delete an element
- Sort the data
Take time to implement the standard sorting algorithms for a list to understand the speed implications: quicksort, bubblesort, heapsort, radix sort, bucket sort
If you look for other algorithmic challenges I suggest checking out graph algorithms. Dijkstra and A* are the most famous.