Hope you all enjoyed the video, let me know what you think of this format! Don't forget the first 1,000 people to use this link will get a 1 month free trial of Skillshare: skl.sh/thecherno07211
The specs did specifically state that the data should be a lowercase English word. Although the cases didn't actually test for it, you didn't know that before submitting the code. Good luck with that.
This assignment is a perfect learning exercise for following instructions and wishes of uneducated users or incompetent product owners, with no knowledge of how the internals work.
@@felixinfinita3777 many of us are stuck with limited choices for education because of financial and other personal reasons. So my peers and I at our school are always learning things on our own time and just going through University for that slip of paper that makes the job filtering process *slightly* easier for us :((
@@felixinfinita3777 the main takeaway here is that it doesn't matter. It's simply there to let people learn about array, loops, play with pointers and references while adhering to a tight spec. It's not supposed to be a realistic scenario
I think we should take it easy on the students here, but not on the person creating the assignment. The student is learning, so obviously they're not always going to make the best choices because they don't know what the best choices are. They're trying to learn a language and are getting precisely zero feedback on the quality of their code. The fact that it works is all we check, which is kind of worthless if they're being allowed to write terrible code and nobody is helping them improve.
I had to write my first programming assignments in C, particularly my second assignment, which was a pain in the butt. Now that it's submitted I can see so many areas of improvement that I might rewrite it this holidays.
Writing "good code" is something my CS professor has been trying to drill into us the last 2 years, and the more I learn the more I really appreciate being taught that in the beginning. She makes us comment every part of our code to explain why we are utilizing it as well as making flowcharts for every one of our assignments/ programs. I really fear the next CS professor I have b/c I know many of them suck at giving detailed feedback.
@@scootypoot3205 Flowcharts should *not* be neccessary. Good comments (meaning not on every part of the code but where it's appropriate) plus good test cases should suffice. You are writing test cases, right?
@@ImperatorZed A lot of it is more of to makesure the students actually understand and know what they are doing. It's like pseudocode, nobody writes pseudocode after that first year or so.
Holy moly this is the best thing ever. I haven’t reached the stuff that is the assignment was talking about but its nothing i can’t understand and this video actually was the best way to learn it. You, literally typing along and thinking/commentating for some reason gives me confidence in my own coding and also shows me ways to approach a problem/question which is perfect! Thank you and please do more!
Imagine university actually teaching you how to make a proper hash table. It'd be cool to see templating, hash calculation, bucketing for collisions etc.
That's what we had to do in the algorithms and data structures course at Stockholm uni, also a second year course. We got one week to do that and one or two other assignments, and that was one of the easier weeks of that course. If they had three weeks to do this they must have had multiple simultaneous/overlapping assignments.
My university doesn't formally teach C++ (only C). And the data structures and algorithms assignment was only a finite state machine and a very primitive binary tree.
Indeed. Personally, i would extract those status strings at least into constants (or similiar) in the code, so typos wouldn't be a thing to look out for. Should be done with all "magic values", in my opinion, just as Cherno did with the size of the hash table.
It hurts my soul when schools teach terrible practices like that. They're on their second year, if they don't know what enums are they should be able to figure it out for the assignment
3 Weeks, wow, that’s a long time for this. Pretty clean code, good explanation of thought process. Fun to see what other educational institutes does in diff countries.
Well its 3 weeks because this is not the only thing you have to do... Keep in mind there are lots of other projects, exams, homework etc. for other classes.
3 роки тому
@@humptyDumptyHadAGreatFall Haha, at my uni we get new programmings assignments every week. Deadline is always in 2 weeks, but you get bonus points if you submit it in the first week. Plus the difficulty of our assignments is on another level and we can only use C. :) And there is still a lot of other things for other classes to do...
@ Yes, we get new C++ assignments every week too. Our deadline is one week and no exceptions. I was just pointing out to people who are self thought programmers and comment on how long they have on the assignment, that it's in not as simple when you are at uni and have other shit 2.
I'm new to programming and learning C++ by myself. Even though many instructions mentioned there are even unclear for me, this video still provides me a tons of useful information about how I can think of my code, when next time I'm trying to solve a specific problem. Also a tons of practical functions learned along the way. Great work body! Need more video like this.
I wrote the code during your coding just to practice, and this kind of videos is very cool. It's very good to see someone is doing a university assignments that it will help us (university students) to think about this in a different way. Also real world codes will help better, and i see that you're doing that as well... Thank you a million. 🙂👍
Absolutely! More University/General coding assignments and challenges. More importantly, real life coding from start to finish, whiteboarding and all. An entire project.
As someone who already program in another language this was a great way to get the basics of C++ and some of your code styling. Can we please have more of those? Maybe some HackerRank tests if you're out of Uni assignments.
was very enjoyable to see your approach to this assignment, taught me some interesting library uses too which is always helpful in expanding my knowledge. 10/10 would watch again!
These in-depth videos are informative and helpful. I, for one, love seeing how skilled programmers implement strategies in detail. So, my vote is for more of these.
It's always fun to tinker with problems to solve :) It doesn't really matter because the test cases don't check for it, but I think you can save yourself that infinite loop and still adhere to the requirements. The requirements say "Keep trying until key is found, or we're certain it doesn't exist" ... If you've tried every slot and haven't found it, you're not going to find it on any subsequent iterations so you probably just stop there. Anyway, thanks for the video!
I think you've missed a rather important requirement for searching - it says "or we're certain doesn't exist". If you loop through the entire "hash table" you can be certain the entry does not exist. You probably shouldn't let it infinitely loop! I would expect the automated test to fail that case.
I start learning programing 5 month ago, after i learn all height value algorithms and data structures, and did a lot of problems in Leetcode this second years assignment seams to me soo easy, that mean i m in a good path, and also thanks to you for your c++ course a learn a lot from your channel.
Thank you, Yan, for this great video. 28:50 I think 'constexpr' is already available in C++11. So, you could define the array size by a constant expression.
Putting my guess in before watching, I feel this is a perfect/typical implementation of a hash table with chaining. I had a similar question in my uni, but with ints instead of strings. I just used -1 for not initialized, -2 for deleted key and neither if its a stored value (unsigned int)
This gives me memories of my first year in CS where we had to create a sort search algorithm with a red black tree in haskell. That was a fun time though I prefer assembly and other object orentead programming. That year was a nightmare since I knew very little about programming when startead and after 4 months I had to write those types of sorting algorithms and learn reccurion in a week. Though it was a fun experience with the downside of missing some understanding of some concepts that had to re-lern later(not enough time to go through it thorrow).
You could also split Entry into two separate arrays "status" and "data" and use std::copy_if with a std::ostream_iterator and have the STL take care of the loop and the correct separator-handling like so: std::copy_if(std::begin(data), std::end(data), std::ostream_iterator{ std::cout, " " }, [&](auto&& key) { auto slot = std::distance(data, &key); return status[slot] == "occupied"; }); Two birds, one stone😉
@@TheCherno Clearing the data is not enough. Then you can get double "orange" by calling: Aapple Aorange Dapple Aorange You need to keep searching if the status is "tombstone". EDIT: My bad. You are actually checking for a match or "never used" status. So clearing should work.
One edge case you missed(and the test cases didn't cover) was in the input checking. Valid keys were supposed to be lowercase English words, so any keys with upper case or other non word characters should have been ignored.
OH POG! It's like the old video where you did a code review and gave pointers on how to make it cleaner, but you're just completely re-doing the assignment the Cherno™ way!?!?! I'm hype
47:22 and that's what I love about C#, there it's literally 1 line and super descriptive: string.Join(" ", m_Entries.Where(entry => entry.Status == "occupied").Select(entry => entry.Data))
@@ABaumstumpf If you are used to functional programming then that line is perfectly easily readable and tells me in one glance exactly what it does. I wonder how you'd write that in C++. Sadly I haven't used C++ since before lambda functions were introduced there. But from a quick glance it does seem to require a lot more verbosity to use functional approaches there. So how would you actually write that in a C++ one-liner? In JavaScript it would look like this (very similar to the C# example): m_Entries.filter(entry => entry.Status === "occupied").map(entry => entry.Data).join(" ");
@@epajarjestys9981 "If you are used to functional programming then that line is perfectly easily readable and tells me in one glance exactly what it does." ... there are always people that says this even about brainfuck. for how to do it: in general i would give the object a function to print the filtered content, then outputting it would be simple. Or one can use either boosts ranges-join, or std::rangers with filter/join (just the lambdas become a bit long). "for( const auto& elem : toBePrinted | std::views::filter([](auto ele){ return ele.status == OCCUPIED; }) ) result += ((result.empty() ? "" : " ," ) + elem.data);"
You actually have a slight mistake in your Find method, it doesn't handle "tombstone" correctly. "Aapple Dapple Aapple" would result in an empty output while the expected output is "apple".
You could also adjust the Add method. If a key exists, don't just return but set the state to "occupied" beforehand. This way, no need to clear any data in find. For "Aapple Dapple Aapple": after Dapple, "apple" is still stored, just set to "tombstone". Then when wewant to add another "apple", we just set it from "tombstone" to "occupied" and it will print again. We update the data only if it becomes stale.
A hash set is a specific kind of hash table where the key is the value. Hash tables are associative arrays and are usually implemented as an array because it gives optimal O(1) best-case performance. They can be implemented as trees which have better worst-case performance at the cost of best-case performance. Other than having a terrible hash function this is just a linear probing hash table/set with a fixed size.
You comment a couple of times that the spec doesn't talk about terminating the find after a certain number of iterations. It does though - "keep trying until key is found, or we're certain it doesn't exist". If we've checked all the slots we can be certain it doesn't exist and should therefore stop, returning false in your case
a video thecherno has always promised in the c++ series and never made is 'how the heck memory works and memory allocation works'. Just pointing out to this topic to remind you.
TLDR: Everyone saying this is a useless arbitrary assignment is wrong. Everyone saying this is completely useless or an unnecessarily complex assignment doesnt see that this is intended to teach one of several methods of implementing a hash table in a class thats on Data Structures & Algorithms where you learn data structure implementations and time complexity analysis. This assignment covers open addressing with linear probing. Theres also quadratic probing and double hashing and can even be paired with chaining. They simplified the hash function for convenience because it easily creates collisions to exemplify what happens on collisions. Its important to know how hash tables could be implemented because it helps with time complexity analysis. Admittedly, it should resize and rehash once a threshold capacity is reached, and its just a hash set rn, a value should be paired with the status for a hash table. But calling it useless or arbitrary doesn't recognize what the assignment is teaching / trying to accomplish
I love this channel ♥️ I regular viewer of this channel ✨💕 And I learnt many things form this channel Thankyou thankyou very much🙏✨✨ Thankyou for this video also🔆
Do you ever check on the 10 character limit for the inputs? Because the assignment also says you need to discard invalid inputs, and any input over 10 characters would be invalid...
You don't know how these kind of assignments work. You will **never** recieve invalid inputs outside of the ones they want you to check specifically (the first letter here). You assume the user knows the rules before giving inputs to your program.
@the air accumulator you never assume the user knows the rules. My professors absolutely required that I implemented guards against the inputs they told me were invalid.
47:50 It brings me joy to see the workaround the trailing space as I've always felt that doing stuff like this myself was a bad or a wrong way to do it. I don't know why. It works as it should but just felt that there should be an easier way to do it.
There is a small bug in the code. After deleting an entry if try to find it again it will return true. So it will fail on a test case like Aapple Dapple Aapple. This can be resolved by setting the data to empty string in delete.
I just finished my first Structured Programming class so I could I actually follow along. That said, I enjoy your criticism about the "following instructions" assessment. I am just a Mechanical Engineering student but I don't see how this type of assignment is something to look forward to. Additionally, my course involved showing up to class to go over the powerpoint, working a few exercises afterwards, then self study until the next class. Self study is loosely defined, as well, since we had no official literature to follow.
well, the assignment says that you should keep trying until you are certain that the key doesn't exist, so it's not just if you encounter "never used" but also if you get back to your original point, so it doesn't have to (shouldn't) loop infinitely
I really enjoyed this video! It makes me feel as if I know how to do this because you explain it so well, but trust me, I would not be able to do this on my own lol
@22:05 The substring method is hopefully more performant than constructing a new string from a const char*. The c_str method should be used in the other case to guarantee null termination. Although, I believe all implementations of std::string null terminate the buffer by default, so it wouldn't cause an issue (hopefully).
His passive-aggressive kind of serious humour is the best thing on the planet lol for example him saying "The students were given three weeks to complete this assignment". I loved this video. 50+ mins not a single skip
48:46. I am not an expert, but why not to make for loop like this: "for (int i = 0; i < Size - 1; i++)". In loop use old code from 46:44. And after the loop ends write: "std::cout
Keep doing them, even if they feel boring. They teach you to think and cement the algorithms and programmers way of thinking into your brain. You won't use that code after college, but the principles will remain the same and THAT you will use :)
Hey Cherno, great format! I got covid and this was a nice way of chilling at home inbetween paracetamol dosis! I'd add to the code maybe the usage of range based loops if you are iterating over the whole array of Entries? It's a good best practices to teach IMO. Other than that, it can't get any better for those specs :)
Could you make a video about the keyboard shortcuts you use? Your navigation and editing is so fast and efficient. I'm sure loads of people would learn a few new things and could become faster themselves.
Looks like just a lot of ctrl+arrow keys for jumping left and right by full words, shift+arrow keys to select characters, ctrl+shift+arrow keys to select full words. Double clicking a word also selects it. Nothing more special than that other than doing it really quickly from what I can tell
32:15 But what if the data is equal, but the status is "tombstone"? Edit: 40:00 Not deleting data, I smell a bug incoming. Edit 2: Turns out it didn't appear in your tests, I'd be interested to see whether it actually is a bug that the tests just don't cover, or if I don't understand the program flow well enough. (Live commenting is fun.)
> 32:15 But what if the data is equal, but the status is "tombstone"? This is a bug in the requirements. According to the requirements, equal data means a match, no matter if the status is "tombstone". Fortunately, this inconsistency is irrelevant, since the only parts of the interface used result in correct behaviour anyway. The only consequence of this behaviour is that a "tombstone" status can be set twice.
@@MasterHigure Please don't! It's actually a nice exercise to go through all possible states for delete and insert (e.g. the only two functions/methods that are actually used) and see what happens. I'd be super happy if you manage to proof me wrong 👍
First, thanks again for providing C++ content that I can actually show my students. Way too much of the C++ content on UA-cam is substandard and out of date. A few things I would do different: 1. Use an enum for the Entry status. I don't like "stringly typed" code. 2. Have Find() return a std::tuple instead of using an out parameter. Perhaps I just have a thing against (a) out parameters, (b) default arguments, and (c) pointers, but I think it leads to cleaner code, and it sets you up to use structured bindings later on when you can use C++17. 3. Lose the std::endl; just use ' '. The first time you run an output-intensive program over a slow VPN, you'll be thankful for that. (Yes, I learned that lesson the hard way.) 4. Simplify the input loop in main to something like this: char command; std::string word; while (std::cin >> command >> word) etc. 5. Use std::array for the hash table array. I just like to avoid raw arrays whenever possible. They're just so C. FWIW, I did double-check that std::tuple and std::array were in C++11. (So was constexpr, BTW.) Also, my first suggestion is the only one I would insist on with my students.
I showed this assignment to my teacher and he found this interesting too. He agreed to let me use this assignment as practice before the real assignment drops but he added another requirement: not to use sstream but to use string or string.h instead. Idk if it's harder or not but I'll try.
Please read carefully. You have to ensure termination in the Find method. The requirements say you have to keep searching until it is found, or your are certain it does not exist. Imagine a full table with entries "a" and you search for "b". In your case the program doesn't terminate. But it should after 26 iterations.
This doesn't seem too unusual for an assignment to me. Probably a bit easy for a 2nd year course, but other than that. They ask to do very unique things with specific requirements in part so it isn't easy for people to find code to copy and in part because meeting requirements is really important.
But what do you actually learn from this? It's not hard for 2nd year so it's not a valid mental exercise and it does not teach you anything new. It's also very impractical
The flag strings all start with different letters so string comparison in this case just compares one char, not a big deal. Also, if you want to avoid typing mistakes just define them as constants.
Would love to see how to make design documents. Because I didn't do Computer Science at College or University level, never had to learn it. Would be interesting to know how it's done properly. Love the C++ videos!
No they won't. It's undefined behavior for any other function than main. I've encountered real-world bugs due to this. Also, in debug mode, some compilers will fill that uninitialized memory with zeroes, others will fill it with a specific pattern (e.g., 0xBAADF00D, 0xDEADBEEF), which I think is more helpful. All compilers at a reasonable warning level will warn about missing return statements.
Your Add function loops twice over the table, both in Find and GetInsertIndex. Instead you can add an outInsertIndex parameter to find (it can be different than outIndex because of tombstones). Also, I don't like the Size being hardcoded 26 without an explanation. Instead I'd suggest ('z' - 'a' + 1), which explains why 26 and also avoids potential mistakes. In python it's even better, len(string.ascii_lowercase). btw having automated testing doesn't mean there is no human testing, it's very common to have both to let the human focus on less trivial problems.
I would love cherno to review more things like this, even big codebases that are in C++ because they aren't that much material available for that language, I love C++ but I don't know what are the best practices, test cases, and stuff like that.
Assignment said that you should keep searching until we are sure that there is no such key in hashtable. so limit on 'Size' number of iterations actually is there
What bothers me most is probably that even if you have to use strings for those statuses I would at least have defined them as static const variables or something for the sake of readability and to prevent typos etc. Sure there are other optimizations especially regarding performance, but that just bothered me really.
When I get assignments like this at trade school, I like to make a "lawful" edition, following the instructions as closely as possible, and an "anarchy" edition where I still fulfill the core requirements of the program, while restructuring everything else to make more sense. Of course, this kind of effort wouldn't be worth it to everyone.
This assignment's requirements sound like what would happen if a mostly-nontechnical person tried to tell you how to implement something. As the programmer, it's part of your job to tell the business when their requirements make no sense from either a business standpoint or a technical standpoint. Even though the professor wants the lawful version, the anarchy version is the correct way to solve the problem, and in a real professional context it would be your responsibility to tell him that.
22:49, lol, your input parsing isn't done. You don't handle the inputs 'A' and 'D' with no word. Maybe the requirements didn't survive the summary, but it sounded like Aword and Dword needed the 'word' to be valid inputs. I don't know about the university this assignment came from, but we had brutal test cases on input parsing.
I'm currently in my DSA class and we also just learned about "Hash Tables," which had me very confused because they put it out to be an alternative to arrays or vectors...which they're not. Hash Tables are Tables, not Lists. They have Key-Value pairs and although the way they told us to program it was similar to this (where it would take a "hash" of the item and slot it in the correct slot) that's still not what a hash table is.
In order to prevent simple, common and easy to make typo's from causing problems in the code regarding the table slot status markers, and since ENUMS seems to be unusable per the instructions, couldn't you create a status struc with 3 string variables? and then call the status.var (or whatever) in place of hand typing out the status strings every time you need to use, compare and set them? something like: struc Status { const char * never = "never used" const char * occupied = "occupied" const char * tomb = "tombstone" }; And then say, in the Find function I could write: ... if (m_Entries[index].status == Status.never) return false; ...
Hope you all enjoyed the video, let me know what you think of this format! Don't forget the first 1,000 people to use this link will get a 1 month free trial of Skillshare: skl.sh/thecherno07211
The specs did specifically state that the data should be a lowercase English word. Although the cases didn't actually test for it, you didn't know that before submitting the code. Good luck with that.
Hi, will u ever do an OpenGL Compute Shader tutorial?
This was perfect! I really really loved the commentary of how you approach a problem and it gave me more confidence for some reason. Thank you!
Yes we loved it please do more :) (Even though this assignment was a bit weird xD)
Please make videos on design patterns with cpp your videos are really amazing 🤩
This assignment is a perfect learning exercise for following instructions and wishes of uneducated users or incompetent product owners, with no knowledge of how the internals work.
I was going to say it is good for using some old arcane library with wierd usage requirements
The main takeaway should be: don't follow such assignments and find better job/university/course
@@felixinfinita3777 this is what my assignments look like...
@@felixinfinita3777 many of us are stuck with limited choices for education because of financial and other personal reasons. So my peers and I at our school are always learning things on our own time and just going through University for that slip of paper that makes the job filtering process *slightly* easier for us :((
@@felixinfinita3777 the main takeaway here is that it doesn't matter. It's simply there to let people learn about array, loops, play with pointers and references while adhering to a tight spec. It's not supposed to be a realistic scenario
Here I am, procrastinating my own assignments to watch someone else doing assignments.
😂 🤣 🤣 🤣
I think we should take it easy on the students here, but not on the person creating the assignment. The student is learning, so obviously they're not always going to make the best choices because they don't know what the best choices are. They're trying to learn a language and are getting precisely zero feedback on the quality of their code. The fact that it works is all we check, which is kind of worthless if they're being allowed to write terrible code and nobody is helping them improve.
I had to write my first programming assignments in C, particularly my second assignment, which was a pain in the butt. Now that it's submitted I can see so many areas of improvement that I might rewrite it this holidays.
Writing "good code" is something my CS professor has been trying to drill into us the last 2 years, and the more I learn the more I really appreciate being taught that in the beginning. She makes us comment every part of our code to explain why we are utilizing it as well as making flowcharts for every one of our assignments/ programs. I really fear the next CS professor I have b/c I know many of them suck at giving detailed feedback.
@@scootypoot3205 Flowcharts should *not* be neccessary. Good comments (meaning not on every part of the code but where it's appropriate) plus good test cases should suffice. You are writing test cases, right?
@@ImperatorZed A lot of it is more of to makesure the students actually understand and know what they are doing. It's like pseudocode, nobody writes pseudocode after that first year or so.
yeah, i think teachers mainly focus on "as long as it runs" rather than emphasizing good coding practice, which I see is rarely taught at university.
Holy moly this is the best thing ever. I haven’t reached the stuff that is the assignment was talking about but its nothing i can’t understand and this video actually was the best way to learn it. You, literally typing along and thinking/commentating for some reason gives me confidence in my own coding and also shows me ways to approach a problem/question which is perfect!
Thank you and please do more!
Imagine university actually teaching you how to make a proper hash table. It'd be cool to see templating, hash calculation, bucketing for collisions etc.
That's what we had to do in the algorithms and data structures course at Stockholm uni, also a second year course. We got one week to do that and one or two other assignments, and that was one of the easier weeks of that course. If they had three weeks to do this they must have had multiple simultaneous/overlapping assignments.
Same in France in 2nd year during DataStructure courses
I did this in my data structures course at Oregon State, it was one of the easier assignments in that class
well a good university teaching that....
My university doesn't formally teach C++ (only C). And the data structures and algorithms assignment was only a finite state machine and a very primitive binary tree.
I don't know C++, but I did the assignment in C# and I am proud that it worked the first time, without errors.
The fact that status is not an enum physically hurts me.
Thought the same it's just really weird in my opinion. But hey school assignments are often pretty shit. Atleast speaking from personal experience...
Typical cpp dev
High five, bruh
Indeed. Personally, i would extract those status strings at least into constants (or similiar) in the code, so typos wouldn't be a thing to look out for.
Should be done with all "magic values", in my opinion, just as Cherno did with the size of the hash table.
It hurts my soul when schools teach terrible practices like that. They're on their second year, if they don't know what enums are they should be able to figure it out for the assignment
The fact that you don't have to ensure any safety spurs up the anxiety within me.
This is a great video! I would like to see more and I'm sure many others agree.
+1
Agree++
@@alexgoldstein1420 agree#
I really liked this type of format. I hope there will be more of it!
3 Weeks, wow, that’s a long time for this.
Pretty clean code, good explanation of thought process. Fun to see what other educational institutes does in diff countries.
Well its 3 weeks because this is not the only thing you have to do... Keep in mind there are lots of other projects, exams, homework etc. for other classes.
@@humptyDumptyHadAGreatFall Haha, at my uni we get new programmings assignments every week. Deadline is always in 2 weeks, but you get bonus points if you submit it in the first week. Plus the difficulty of our assignments is on another level and we can only use C. :) And there is still a lot of other things for other classes to do...
@@humptyDumptyHadAGreatFall more importantly people that never used c++ before wont finish this assignment as fast
@ Yes, we get new C++ assignments every week too. Our deadline is one week and no exceptions.
I was just pointing out to people who are self thought programmers and comment on how long they have on the assignment, that it's in not as simple when you are at uni and have other shit 2.
I'm new to programming and learning C++ by myself. Even though many instructions mentioned there are even unclear for me, this video still provides me a tons of useful information about how I can think of my code, when next time I'm trying to solve a specific problem. Also a tons of practical functions learned along the way.
Great work body! Need more video like this.
Your channel actually got me through university c++/computer graphics
I wrote the code during your coding just to practice, and this kind of videos is very cool.
It's very good to see someone is doing a university assignments that it will help us (university students) to think about this in a different way.
Also real world codes will help better, and i see that you're doing that as well...
Thank you a million. 🙂👍
Absolutely! More University/General coding assignments and challenges. More importantly, real life coding from start to finish, whiteboarding and all. An entire project.
As someone who already program in another language this was a great way to get the basics of C++ and some of your code styling. Can we please have more of those? Maybe some HackerRank tests if you're out of Uni assignments.
was very enjoyable to see your approach to this assignment, taught me some interesting library uses too which is always helpful in expanding my knowledge. 10/10 would watch again!
These in-depth videos are informative and helpful. I, for one, love seeing how skilled programmers implement strategies in detail. So, my vote is for more of these.
It's always fun to tinker with problems to solve :)
It doesn't really matter because the test cases don't check for it, but I think you can save yourself that infinite loop and still adhere to the requirements. The requirements say "Keep trying until key is found, or we're certain it doesn't exist" ... If you've tried every slot and haven't found it, you're not going to find it on any subsequent iterations so you probably just stop there.
Anyway, thanks for the video!
He probably thought some data status can be “tombstone” in the future, so it’s place can be changed
careful kids, you are seeing a master at work.
This makes me want to go back to my old college assignments and redo them... What have you done to me?
Really like these kinds of videos.
We love you The Cherno
I think you've missed a rather important requirement for searching - it says "or we're certain doesn't exist". If you loop through the entire "hash table" you can be certain the entry does not exist. You probably shouldn't let it infinitely loop! I would expect the automated test to fail that case.
This assignment is definitely written by a java professor who got stuck teaching a c++ class
sadly most professors never worked an actual job
@@nobytes2 At my uni you can see all the papers they have published, and sometimes you hear about where they used to work.
The mere idea of "java professor" is, frankly, ridiculous.
Why? Java is a great language. In a lot of ways comparable to c++. @@tolkienfan1972
Really great video! Didn't felt like 50 minutes passed! :D
What a video! Even in my case (I work with C++) it was possible to learn watching your solutions!
Please, continue this format!
A series in which you speed run university assignments sounds cool
New to your channel but I’m loving your videos man, thanks for the efforts you put in.
I start learning programing 5 month ago, after i learn all height value algorithms and data structures, and did a lot of problems in Leetcode this second years assignment seams to me soo easy, that mean i m in a good path, and also thanks to you for your c++ course a learn a lot from your channel.
Thank you, Yan, for this great video.
28:50 I think 'constexpr' is already available in C++11. So, you could define the array size by a constant expression.
Putting my guess in before watching, I feel this is a perfect/typical implementation of a hash table with chaining. I had a similar question in my uni, but with ints instead of strings. I just used -1 for not initialized, -2 for deleted key and neither if its a stored value (unsigned int)
This gives me memories of my first year in CS where we had to create a sort search algorithm with a red black tree in haskell. That was a fun time though I prefer assembly and other object orentead programming. That year was a nightmare since I knew very little about programming when startead and after 4 months I had to write those types of sorting algorithms and learn reccurion in a week. Though it was a fun experience with the downside of missing some understanding of some concepts that had to re-lern later(not enough time to go through it thorrow).
You can use range based for loop in your Print function. They were in language since C++11.
You could also split Entry into two separate arrays "status" and "data" and use std::copy_if with a std::ostream_iterator and have the STL take care of the loop and the correct separator-handling like so:
std::copy_if(std::begin(data), std::end(data), std::ostream_iterator{ std::cout, " " }, [&](auto&& key) {
auto slot = std::distance(data, &key);
return status[slot] == "occupied";
});
Two birds, one stone😉
Another thing that exists in C++11 is constexpr (both variables and functions), unlike what Cherno said at 23:46
i love your videos to the level that i watched the full ad at the beginning
Oh yes. More of this with medium/hard Leetcode questions, please!
yes! more. this exercise is exactly what we need. please
The Find function will return true for tombstone entries for a matching entry string. I think this can fail the test in some edge case.
You're right, that's what I get for not clearing the data... 🤦♂️
@@TheCherno c++ series, make template video and how memory works (heap, stack, etc)
@@nyanlauncher7350 pretty sure he already has those in the C++ series
@@TheCherno Clearing the data is not enough.
Then you can get double "orange" by calling:
Aapple Aorange Dapple Aorange
You need to keep searching if the status is "tombstone".
EDIT: My bad. You are actually checking for a match or "never used" status. So clearing should work.
@@IndrekL i think the solution you were thinking of was to rewrite this in rust ( ͡~ ͜ʖ ͡°) jk lol
One edge case you missed(and the test cases didn't cover) was in the input checking. Valid keys were supposed to be lowercase English words, so any keys with upper case or other non word characters should have been ignored.
OH POG! It's like the old video where you did a code review and gave pointers on how to make it cleaner, but you're just completely re-doing the assignment the Cherno™ way!?!?! I'm hype
I coded it myself before watching too to compare our outputs, fun!
47:22 and that's what I love about C#, there it's literally 1 line and super descriptive:
string.Join(" ", m_Entries.Where(entry => entry.Status == "occupied").Select(entry => entry.Data))
Yeah... you can write that in 1 line in C++ as well - but i would say neither is "descriptive" or even acceptable code.
@@ABaumstumpf If you are used to functional programming then that line is perfectly easily readable and tells me in one glance exactly what it does.
I wonder how you'd write that in C++. Sadly I haven't used C++ since before lambda functions were introduced there. But from a quick glance it does seem to require a lot more verbosity to use functional approaches there.
So how would you actually write that in a C++ one-liner?
In JavaScript it would look like this (very similar to the C# example):
m_Entries.filter(entry => entry.Status === "occupied").map(entry => entry.Data).join(" ");
@@epajarjestys9981 "If you are used to functional programming then that line is perfectly easily readable and tells me in one glance exactly what it does."
... there are always people that says this even about brainfuck.
for how to do it:
in general i would give the object a function to print the filtered content, then outputting it would be simple.
Or one can use either boosts ranges-join, or std::rangers with filter/join (just the lambdas become a bit long).
"for( const auto& elem : toBePrinted | std::views::filter([](auto ele){ return ele.status == OCCUPIED; }) ) result += ((result.empty() ? "" : " ," ) + elem.data);"
You actually have a slight mistake in your Find method, it doesn't handle "tombstone" correctly. "Aapple Dapple Aapple" would result in an empty output while the expected output is "apple".
You could also adjust the Add method. If a key exists, don't just return but set the state to "occupied" beforehand. This way, no need to clear any data in find. For "Aapple Dapple Aapple": after Dapple, "apple" is still stored, just set to "tombstone". Then when wewant to add another "apple", we just set it from "tombstone" to "occupied" and it will print again. We update the data only if it becomes stale.
A hash set is a specific kind of hash table where the key is the value. Hash tables are associative arrays and are usually implemented as an array because it gives optimal O(1) best-case performance. They can be implemented as trees which have better worst-case performance at the cost of best-case performance.
Other than having a terrible hash function this is just a linear probing hash table/set with a fixed size.
You comment a couple of times that the spec doesn't talk about terminating the find after a certain number of iterations. It does though - "keep trying until key is found, or we're certain it doesn't exist". If we've checked all the slots we can be certain it doesn't exist and should therefore stop, returning false in your case
a video thecherno has always promised in the c++ series and never made is 'how the heck memory works and memory allocation works'. Just pointing out to this topic to remind you.
Also templates
I second this reminder
That would be a very long video lol
@@kartikeyagarwal6087 he already has one on that. Just search for thecherno templates. And you will get the video
TLDR: Everyone saying this is a useless arbitrary assignment is wrong.
Everyone saying this is completely useless or an unnecessarily complex assignment doesnt see that this is intended to teach one of several methods of implementing a hash table in a class thats on Data Structures & Algorithms where you learn data structure implementations and time complexity analysis. This assignment covers open addressing with linear probing. Theres also quadratic probing and double hashing and can even be paired with chaining. They simplified the hash function for convenience because it easily creates collisions to exemplify what happens on collisions. Its important to know how hash tables could be implemented because it helps with time complexity analysis. Admittedly, it should resize and rehash once a threshold capacity is reached, and its just a hash set rn, a value should be paired with the status for a hash table. But calling it useless or arbitrary doesn't recognize what the assignment is teaching / trying to accomplish
I love this channel ♥️
I regular viewer of this channel ✨💕
And I learnt many things form this channel
Thankyou thankyou very much🙏✨✨
Thankyou for this video also🔆
Do you ever check on the 10 character limit for the inputs? Because the assignment also says you need to discard invalid inputs, and any input over 10 characters would be invalid...
You don't know how these kind of assignments work. You will **never** recieve invalid inputs outside of the ones they want you to check specifically (the first letter here). You assume the user knows the rules before giving inputs to your program.
@the air accumulator you never assume the user knows the rules. My professors absolutely required that I implemented guards against the inputs they told me were invalid.
47:50 It brings me joy to see the workaround the trailing space as I've always felt that doing stuff like this myself was a bad or a wrong way to do it. I don't know why. It works as it should but just felt that there should be an easier way to do it.
Perhaps you should have a look to std::accumulate, check the third example with dash_fold lambda in the documentation.
There is a small bug in the code. After deleting an entry if try to find it again it will return true. So it will fail on a test case like Aapple Dapple Aapple. This can be resolved by setting the data to empty string in delete.
It's fascinating, feel free to do more if you feel like it!
Using mod for wrapping around blew my mind!
THANK YOU
I just finished my first Structured Programming class so I could I actually follow along. That said, I enjoy your criticism about the "following instructions" assessment. I am just a Mechanical Engineering student but I don't see how this type of assignment is something to look forward to. Additionally, my course involved showing up to class to go over the powerpoint, working a few exercises afterwards, then self study until the next class. Self study is loosely defined, as well, since we had no official literature to follow.
well, the assignment says that you should keep trying until you are certain that the key doesn't exist, so it's not just if you encounter "never used" but also if you get back to your original point, so it doesn't have to (shouldn't) loop infinitely
I love this series
I really enjoyed this video! It makes me feel as if I know how to do this because you explain it so well, but trust me, I would not be able to do this on my own lol
@22:05 The substring method is hopefully more performant than constructing a new string from a const char*. The c_str method should be used in the other case to guarantee null termination. Although, I believe all implementations of std::string null terminate the buffer by default, so it wouldn't cause an issue (hopefully).
the -'a' triggers me, when there is uppercase in the input stream!🤣
His passive-aggressive kind of serious humour is the best thing on the planet lol for example
him saying "The students were given three weeks to complete this assignment". I loved this video. 50+ mins not a single skip
Learned a lot of random things I wouldn't have thought to ask. Thanks!
48:46. I am not an expert, but why not to make for loop like this: "for (int i = 0; i < Size - 1; i++)". In loop use old code from 46:44.
And after the loop ends write: "std::cout
This is how my classes are very in-depth with lots of reqs that helps us make code that we won't use after college
Keep doing them, even if they feel boring. They teach you to think and cement the algorithms and programmers way of thinking into your brain. You won't use that code after college, but the principles will remain the same and THAT you will use :)
This is kinda like watching a speedrun
Hey Cherno, great format! I got covid and this was a nice way of chilling at home inbetween paracetamol dosis!
I'd add to the code maybe the usage of range based loops if you are iterating over the whole array of Entries? It's a good best practices to teach IMO. Other than that, it can't get any better for those specs :)
Could you make a video about the keyboard shortcuts you use?
Your navigation and editing is so fast and efficient.
I'm sure loads of people would learn a few new things and could become faster themselves.
Looks like just a lot of ctrl+arrow keys for jumping left and right by full words, shift+arrow keys to select characters, ctrl+shift+arrow keys to select full words. Double clicking a word also selects it. Nothing more special than that other than doing it really quickly from what I can tell
@@robbertzzzzz how about moving to the start/end of the line, selecting the entire line, deleting the entire line and moving the line up/down?
@@gamersfunnl2067 end/home, shift+end/home, and I think hitting ctrl+x with nothing selected cuts the entire line.
Same
@@gamersfunnl2067 move lines up/down alt+up,alt+down
copy lines up/down shift+alt+up,shift+alt+down
no need to select
Fantastic video, really helpful to head your thought process "live" as you went!
I mean replacing while(true) with for(int i=0; i
with the space at the end, you could also always pop the last character of the string since you know it will be a space
This isn't a string, it's printed to stdout
@@AssemblyWizard ohh 😪
o my god
Cherno's the type of guy who explains what a code review is
32:15 But what if the data is equal, but the status is "tombstone"?
Edit: 40:00 Not deleting data, I smell a bug incoming.
Edit 2: Turns out it didn't appear in your tests, I'd be interested to see whether it actually is a bug that the tests just don't cover, or if I don't understand the program flow well enough. (Live commenting is fun.)
> 32:15 But what if the data is equal, but the status is "tombstone"?
This is a bug in the requirements. According to the requirements, equal data means a match, no matter if the status is "tombstone".
Fortunately, this inconsistency is irrelevant, since the only parts of the interface used result in correct behaviour anyway.
The only consequence of this behaviour is that a "tombstone" status can be set twice.
@@totalermist Sounds reasonable. I'll take your word for it.
@@MasterHigure Please don't! It's actually a nice exercise to go through all possible states for delete and insert (e.g. the only two functions/methods that are actually used) and see what happens.
I'd be super happy if you manage to proof me wrong 👍
@@totalermist We'll see. I'm somewhat indisposed at the moment, what with summer and all. I might check up on it later.
I feel honored that my comment made it to this video, Thank you Cherno
First, thanks again for providing C++ content that I can actually show my students. Way too much of the C++ content on UA-cam is substandard and out of date.
A few things I would do different:
1. Use an enum for the Entry status. I don't like "stringly typed" code.
2. Have Find() return a std::tuple instead of using an out parameter. Perhaps I just have a thing against (a) out parameters, (b) default arguments, and (c) pointers, but I think it leads to cleaner code, and it sets you up to use structured bindings later on when you can use C++17.
3. Lose the std::endl; just use '
'. The first time you run an output-intensive program over a slow VPN, you'll be thankful for that. (Yes, I learned that lesson the hard way.)
4. Simplify the input loop in main to something like this:
char command;
std::string word;
while (std::cin >> command >> word)
etc.
5. Use std::array for the hash table array. I just like to avoid raw arrays whenever possible. They're just so C.
FWIW, I did double-check that std::tuple and std::array were in C++11. (So was constexpr, BTW.) Also, my first suggestion is the only one I would insist on with my students.
Professor Wells, please share your code. thank you
Attaching the code and assignment would be very helpful for us to follow along!
@TheCherno There is an infinite loop in Find function, when the table is full and you try to add other element
BLOODY HELL at 27:48 I needed a light mode warning, my retinas got burned! other than that, awesome video, thanks!
The Cherno, an idea for your C++ channel... making some videos about Design Patterns. Cheers and keep these coming!
Please make a video on standard getline function of C++
I showed this assignment to my teacher and he found this interesting too. He agreed to let me use this assignment as practice before the real assignment drops but he added another requirement: not to use sstream but to use string or string.h instead. Idk if it's harder or not but I'll try.
The stringstream can be avoided fairly easily to just use cin directly. For example, while(cin.peek() != '
') ...
Please read carefully. You have to ensure termination in the Find method. The requirements say you have to keep searching until it is found, or your are certain it does not exist. Imagine a full table with entries "a" and you search for "b". In your case the program doesn't terminate. But it should after 26 iterations.
This doesn't seem too unusual for an assignment to me. Probably a bit easy for a 2nd year course, but other than that. They ask to do very unique things with specific requirements in part so it isn't easy for people to find code to copy and in part because meeting requirements is really important.
But what do you actually learn from this?
It's not hard for 2nd year so it's not a valid mental exercise and it does not teach you anything new. It's also very impractical
The flag strings all start with different letters so string comparison in this case just compares one char, not a big deal. Also, if you want to avoid typing mistakes just define them as constants.
Would love to see how to make design documents. Because I didn't do Computer Science at College or University level, never had to learn it. Would be interesting to know how it's done properly. Love the C++ videos!
holy hell you made that way more convoluted then it had to be.
great! I can't wait to watch the full video :)
To my knowledge every function, not just main, will return the value 0 appropriately cast to the return value if the return statement is omitted.
No they won't. It's undefined behavior for any other function than main. I've encountered real-world bugs due to this. Also, in debug mode, some compilers will fill that uninitialized memory with zeroes, others will fill it with a specific pattern (e.g., 0xBAADF00D, 0xDEADBEEF), which I think is more helpful. All compilers at a reasonable warning level will warn about missing return statements.
Your Add function loops twice over the table, both in Find and GetInsertIndex. Instead you can add an outInsertIndex parameter to find (it can be different than outIndex because of tombstones).
Also, I don't like the Size being hardcoded 26 without an explanation. Instead I'd suggest ('z' - 'a' + 1), which explains why 26 and also avoids potential mistakes. In python it's even better, len(string.ascii_lowercase).
btw having automated testing doesn't mean there is no human testing, it's very common to have both to let the human focus on less trivial problems.
As a high school programming reacher, I suddenly feel a lot better about the assignments I give my students…
I would love cherno to review more things like this, even big codebases that are in C++ because they aren't that much material available for that language, I love C++ but I don't know what are the best practices, test cases, and stuff like that.
Assignment said that you should keep searching until we are sure that there is no such key in hashtable.
so limit on 'Size' number of iterations actually is there
I don't code in Cpp, but I watched this full video, it's very enjoyable. It was oddly relaxing.
What bothers me most is probably that even if you have to use strings for those statuses I would at least have defined them as static const variables or something for the sake of readability and to prevent typos etc. Sure there are other optimizations especially regarding performance, but that just bothered me really.
When I get assignments like this at trade school, I like to make a "lawful" edition, following the instructions as closely as possible, and an "anarchy" edition where I still fulfill the core requirements of the program, while restructuring everything else to make more sense.
Of course, this kind of effort wouldn't be worth it to everyone.
This assignment's requirements sound like what would happen if a mostly-nontechnical person tried to tell you how to implement something. As the programmer, it's part of your job to tell the business when their requirements make no sense from either a business standpoint or a technical standpoint. Even though the professor wants the lawful version, the anarchy version is the correct way to solve the problem, and in a real professional context it would be your responsibility to tell him that.
Thank You Very Much You Really Deserve The Best Man ! ❤️
With the print issue at the end, I would personally just build a string first and cut off the trailing space before printing the complete string.
Finally done with the c++ serius .. time for the game engine serius :)
The Cherno going outside on a snowy day : hmm there a lot of particles going on
22:49, lol, your input parsing isn't done. You don't handle the inputs 'A' and 'D' with no word. Maybe the requirements didn't survive the summary, but it sounded like Aword and Dword needed the 'word' to be valid inputs. I don't know about the university this assignment came from, but we had brutal test cases on input parsing.
This assignment gets B-
I just learned to write hello world and here I am watching university assignments being solved lol
hey, great video! where can I find the code, the tests and the assignment description?
I'm currently in my DSA class and we also just learned about "Hash Tables," which had me very confused because they put it out to be an alternative to arrays or vectors...which they're not. Hash Tables are Tables, not Lists. They have Key-Value pairs and although the way they told us to program it was similar to this (where it would take a "hash" of the item and slot it in the correct slot) that's still not what a hash table is.
In order to prevent simple, common and easy to make typo's from causing problems in the code regarding the table slot status markers, and since ENUMS seems to be unusable per the instructions, couldn't you create a status struc with 3 string variables? and then call the status.var (or whatever) in place of hand typing out the status strings every time you need to use, compare and set them? something like:
struc Status
{
const char * never = "never used"
const char * occupied = "occupied"
const char * tomb = "tombstone"
};
And then say, in the Find function I could write:
...
if (m_Entries[index].status == Status.never)
return false;
...