Help with learning data structures

[memepapa]

Dear all,

currently, the only book i have for learning data structure is
< C++ Data Structures and Algorithms > by Wisnu Anggoro (published by Packt> )

apart from that, I'm practicing leetcode questions, looking up the discussions which give scattered information on data structure, then googling for information and searching youtubes for relevant videos.

would appreciate if you have any more books to recommend, based on your own learning experience.

thanks in advance

[jonnin]

c++ has most of the classic data structures built into it, except for graphs (including nonbinary trees), and many of the algorithms. You will use those built in ones when coding after your studies of the container concepts.

Beyond the basics, which your book or any other with a similar name will cover just fine, it becomes a big topic on what you want to get out of it. What are you looking for next?

one thing that few books teach is how to build one data structure from another, like using a vector to build a tree or list for the best of both designs. Just knowing you can do that is enough though, it opens a ton of doors.

wikipedia has most every common algorithm explained in great detail.

[seeplus]

It depends somewhat upon why you are learning data structures - to know what are the common ones and how to use them (list, stack, tree etc) in a C++ program, to know how to write your own (nice exercise for understanding but not really needed with C++'s in-built ones except perhaps trees), an academic mathematical analysis (in which case have a look at Knuth - not C++) etc. Knowing how to write a data structure (such as a list) is more important for languages such as C which doesn't have them in-built. Many books an Data Structures and Algorithms approach from an academic background and describe how to code these structures. Where are you coming from on this?

[memepapa]

thanks seeplus, for your elaborate thoughts.


I'm trying to improve on my data structures knowledge to prepare for upcoming job interviews starting 2-3 months from now.

Specifically aiming for job interviews with fintech companies and financial institutes such as high-frequency trading firms, hence i'm specifically looking at solving coding challenges using C++

as I have researched, topics on data structures encountered in coding interviews are commonly
1) Linked lists (tend to be academic, seldom used in real-life work situations?)
2) Trees, tries & Graphs
3) Stacks & Queues
4) Heaps
5) Vectors/ ArrayLists
6) Hash tables.

my current way of studying C++ is as follows
a) i spend half my time reading books which include
- C++ Primer
- Beginning C++20 (From Novice to Professional)
as recommended by a contributor in this forum
- C++ A Beginners Guide by Herbert
- Teach Yourself C++ in One Hour a Day
- C++ Data Structures and Algorithms > by Wisnu Anggoro (published by Packt>

the list of books to read keeps getting longer, not complaining. but to break the monotony, i watch youtube video tutorials too (mostly by TheCherno, Bucky(Boston) etc)

b) and i spend the other half of my time trying to solve leetcode questions, specifically on data structures.
https://leetcode.com/study-plan/data-structure/

[jonnin]

each has pros and cons. if list were just an egghead school toy, c++ would not provide <list>.

1) lists ... good at inserting and deleting even in the middle, esp when using alternative implementations that limit sequential access problems for large data (skiplists, or combined with something else). Lists are bad at searching. They make excellent stacks and queues, because adding to head (or a tail pointer variation) is very simple. Classic (school version) code tends to have memory fragmentation problems (same as tree, graph, anything single item pointer chain based) but you can fix that with a better design.

2) trees and graphs ... advanced algorithms in graphs can be interesting, and trees are useful in some places but more often than not trees are redundant with vectors. I don't use either one much, but some types of problems are well stated with these. I have used both in professional code, but neither one *directly* more than once every 5+ years. If one is hidden in some library or utility, ok, if that counts. I think one of the maps or sets uses a tree.

3) stacks and Qs are, to me, more algorithm and concept than structure. They are both just some extra rules placed on a list or similar container's implementation really. <vector> is a great example here... it can do everything a stack or queue can do, and more. To make it a stack or queue, you just need to take away some of its capability. Both are useful, and often used together.

4) I have not ever used a heap. A dim memory from school days.

5) vectors is your go-to 'what should I stuff the data in' container. Its good at most everything, except inserting in the middle.

6) hash tables -- I use these too much, probably. They are fast and do what they do better than anything else. When appropriate, this is a great tool. But even something with O(1) access has drawbacks... touching every item or producing a sorted list of the data is a total trainwreck, and they waste memory by design.

[memepapa]

thanks, Jonnin, now the question is how and where do I find out more when I'm stuck?

I usually try google first, followed by searching youtubes, and reading the chapters in books that might have relevant topics.

for example, Hash Tables (which you mentioned using them too much)

i was having difficulty understanding unordered_map, the typical books on C++ doesn't seem to go in-depth, watching youtubes gave me more info, but when it comes to a problem that unordered_map is a effective way of solving, then I start running out of resources to read up on.

and seems like asking a question in this forum (or others like stackoverflow) might be the way to go

was wondering if there's an in-depth book on data structures that i could read up more instead.

[jonnin]

I don't know any books. The last books I bought were when the STL came out; since then I have relied on the internet.

a hash table is really simple. All data in a computer consists of bytes. Any group of bytes can be converted directly or indirectly into an integer in a range. If you can find some bytes that uniquely identify the data and mash them together into an integer, you can store the data at table[integer] and get it back.

its good for problems where you need to find one record out of billions quickly. Like the guy on the phone that just called and wants his billing address updated... you want to search 10 billion customer records, even log N search time, doing slow string matches, or just grab his record? Databases work off a form of hash tables almost exclusively; they use something called 'indexing' that is a form of hashing, though for various reasons they have many indices not just one like a standard hash table, its the same concept.


it sounds like it may be good for you to find or create a list of pros and cons for each data structure, follow the overly simple ideas here on how to pick a DS. https://opendsa-server.cs.vt.edu/ODSA/Books/Everything/html/IntroDSA.html
with that extended to cover the pros and cons you can make a flowchart that tells you which one to use for what kind of problem.

[memepapa]

a question related to hash table (specifically, the unordered_map)

if i don't know every single key in the hash table, is there a way to display all the key value pairs?

[againtry]

A book: https://au.cengage.com/c/isbn/9781133608424/
An unordered_map: https://en.cppreference.com/w/cpp/container/unordered_map

[JLBorges]

> is there a way to display all the key value pairs?

Iterate over all the key value pairs. Note that in a hash table, the keys are not ordered.

#include <iostream>
#include <unordered_map>
#include <string>

int main()
{
    const std::unordered_map< std::string, int > hash_table
    {
        { "abcd", 98 }, { "efgh", 22 }, { "ijkl", 45 }, { "mnop", 12 }, { "qrst", 62 }
    };
    
    // print out each key, mapped_value pair in the hash table 
    for( const auto& [key,value] : hash_table ) std::cout << key << " => " << value << '\n' ;
}

http://coliru.stacked-crooked.com/a/5a0668725a21d604

[seeplus]

Another possible book is Fundamentals Of Data Structures in C++
https://www.amazon.co.uk/Fundamentals-Data-Structures-SAHNI-HOROWITZ/dp/8173716064/ref=sr_1_12

- which is a bit cheaper than the other above recommendation!