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.
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 strange thing about this assignment is that it dictates how the internals are to be implemented (hash function, number of buckets, states etc) yet its graded purely on the externally visible behaviour. The grading would never know if you just used an std::unordered_set
Well, not quite. It relies on the output being in the right order. But apart from that, yes. I paused the video after the instructions and implemented it for myself. Some tweaks seemed just more logical to me than what the instructions say: - an enum for the slot states - Add doesn't need to check if the key exists before finding a place to insert. It can just do both at the same time.
Yeah, that struck me as odd. As long as you wrote a program that accurately simulated the behaviour they were looking for, you'd get 10/10, regardless of the implementation.
from my experience, university assignments are *never* graded purely on externally visible behavior. Automatically evaluating whether the program works is a convenience, usually it would have to be run manually to check the output. If the program does work, checking its implementation is of course a given too. A lot of people seem to be confused as to why the assignment requires a specific kind of implementation when it is not the best or simplest way to perform the task. Remember that university assignments are for one purpose only, learning. If it asks you to implement a hash table search, it is to train the student to understand and use real hash tables, through a simpler example. If your first programming assignment asks you to write a for loop to count to 1000, its purpose is not to teach the student the number 1000, it is to make the student understand and use for loops.
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.
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!
@@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.
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.
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.
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.
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!
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.
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.
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.
2 года назад
@@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.
Absolutely! More University/General coding assignments and challenges. More importantly, real life coding from start to finish, whiteboarding and all. An entire project.
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!
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.
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.
Check handmade hero for memory allocation. It's much more in-depth, better, and goes beyond most of these "just use the std::vector / STL bro" type of videos.
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.
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😉
I kind of like getting down to the command line compilation. Nice change lol. I really wish C++ had a Rust style build system though... would be super nice.
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.
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
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
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).
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.
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.
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.
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.
First, thanks again for providing C++ content that I can actually show my students. Way too much of the C++ content on RU-vid 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.
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
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
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.
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.
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 👍
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.
@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).
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.
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.
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.
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
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; ...
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
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 :)
Love this format really but feel like it was a missed opportunity to create a small Makefile since we're in Linux land. That could also be used not only to do the compilation/linking, but also to run all the functional tests as well with a test virtual target. Makefile are a saving grace when working in the cli and translate very well into ci/cd systems in the real world.
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
This is interesting, I just finished my second year in a community college and transferring to a 4yr school. All I have done so far is C++ when it comes to coding, this assignment seems quite convoluted for a second-year student. Not to mention it might test your knowledge, but it has little to no real functionality. I am pretty sure I can complete it, but I think its more demanding than my average assignment thus far.
I just finished my second year in a CC and my final project for data structures class was building a database using maps and multi maps I implemented while using B+ Trees as the underlying data structure to store indices of a binary file. The user would input SQL-like commands like “insert into [table_name] values [value_list]”. Then I parsed through the data by tokenizing the input through a state machine then running the tokens through another state machine to determine if I had a proper command. After that I built a tree that formatted a command into a spec I can understand later. Then, I used the shutting yard algorithm and dealt with evaluating conditional expressions with logical and relational operators to determine the indices I was looking for. As a second year community college student, this assignment seems way too simple for a 3 week period.
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.
The requirements in the assignment are poorly written, but they do imply a halt. The last requirement for the find function states "keep trying until the key is found, or we're certain it doesn't exist". I would argue that looping through the entire array and coming back to where you started is certainty that it doesn't exist which means to satisfy the requirements you do need to check that, and if I were a teacher constructing the test batch for this assignment I would throw in a test case where the table is full and I search for something that isn't there to see how many submissions end up in an infinite loop which I would take off points for.
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.
This assignment is so much more confusing than I was expecting. When I first read the assignment, I thought it wanted 26slots, each with a linked list of keys matching with the hash. But no, it only allows for 26 values *ever*
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
Looking at the assignment I assume one major requirement for the design of this assignment: it must not turn up in a google search. With online assignments, usually all the internet is available and frankly speaking, for computer science it should be. In short, the assignment should not teach the student how to implement a hash table. The hash table was probably done in detail during the lectures and during some trainings. This looks like some time-limited exercise that should not turn up in a google search. It should show whether the student understood the basic principles of programming and the basics of hash-tables by giving a vastly simplified problem. Taking that assignment out of context will probably do the teacher wrong.
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.
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🔆
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
Someone else mentioned the need to skip bad inputs. Something like ABad that isn’t all lowercase would be illegal, so the input validation should make sure to skip it. Same if the key is longer than 10 characters. I would expect at least one test case to make sure many kinds of invalid inputs are actually being ignored.
Hi! For the last space problem, how about we just add all the output in a string and check if it contains a space at the last character and just remove it? It seems a bit more simple to me like that. Anyways, great content.👍
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.
Depends on what your prospects are for your future in software. While you may not have to implement a hash table yourself, event, it gives you an introduction to how data structures and algorithms work on a basic level. Often assignments feel more difficult due to the pressure on getting it "right" to get high grades. This is of course not a true reflection of real-life.
