I did a C++ University Assignment
Вставка
- Опубліковано 18 тра 2024
- The first 1,000 people to use this link will get a 1 month free trial of Skillshare: skl.sh/thecherno07211
Patreon ► / thecherno
Instagram ► / thecherno
Twitter ► / thecherno
Discord ► thecherno.com/discord
0:00 - Intro
3:30 - Assignment requirements
12:56 - Doing the assignment
49:10 - Outro
Code ► Coming soon...
Send an email to chernoreview@gmail.com with your source code, a brief explanation, and what you need help with/want me to review and you could be in the next episode of my Code Review series! Also let me know if you would like to remain anonymous.
This video is sponsored by Skillshare.
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
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.
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.
Here I am, procrastinating my own assignments to watch someone else doing assignments.
😂 🤣 🤣 🤣
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.
@@DFYX When I graded assignments as a TA, I would only read the code AFTER the sample passes validation tests.
Welcome to higher education.
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.
I don't know C++, but I did the assignment in C# and I am proud that it worked the first time, without errors.
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.
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!
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
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.
when he said "I'm not going to go into the design document"
I literally put my breakfast down I was so sad.
Your channel actually got me through university c++/computer graphics
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.
Fantastic video, really helpful to head your thought process "live" as you went!
New to your channel but I’m loving your videos man, thanks for the efforts you put in.
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.
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!
What a video! Even in my case (I work with C++) it was possible to learn watching your solutions!
Please, continue this format!
I love this series
great! I can't wait to watch the full video :)
Absolutely! More University/General coding assignments and challenges. More importantly, real life coding from start to finish, whiteboarding and all. An entire project.
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.
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).
I would love watching a series where you just solve Code Wars puzzles!
We love you The Cherno
It's fascinating, feel free to do more if you feel like it!
Really great video! Didn't felt like 50 minutes passed! :D
Learned a lot of random things I wouldn't have thought to ask. Thanks!
i love your videos to the level that i watched the full ad at the beginning
More of this please!
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.
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.
Using mod for wrapping around blew my mind!
THANK YOU
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.
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 :)
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 series in which you speed run university assignments sounds cool
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.
Oh yes. More of this with medium/hard Leetcode questions, please!
yes! more. this exercise is exactly what we need. please
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
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.
This is kinda like watching a speedrun
This is a hashtable, it's called hasing with linear search. There are other implementation of hashtables, for example a hastable with lists.
Excellent video!
Interesting video! Would like to see more like it.
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.
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.
Thank You Very Much You Really Deserve The Best Man ! ❤️
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.
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 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🔆
@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).
Thanks for sharing, very interesting.
the -'a' triggers me, when there is uppercase in the input stream!🤣
Yeah great! More of this!
Very cool video !
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
More videos like this please!!!!
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
holy hell you made that way more convoluted then it had to be.
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.
More videos like this plz.
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.
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.
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.
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.
I don't code in Cpp, but I watched this full video, it's very enjoyable. It was oddly relaxing.
Attaching the code and assignment would be very helpful for us to follow along!
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 😪
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.
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.
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
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.
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
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
Cherno's the type of guy who explains what a code review is
@TheCherno There is an infinite loop in Find function, when the table is full and you try to add other element
Please make a video on standard getline function of C++
thank you gentleman
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 :)
Finally done with the c++ serius .. time for the game engine serius :)
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.
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);"
The Cherno, an idea for your C++ channel... making some videos about Design Patterns. Cheers and keep these coming!
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.
Your Print function's for loop could be simplified with a ranged for, since it's iterating over a member array it will know the size. Like this:
for ( auto &entry: m_Entries)
{
}
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.
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
it really helping us learn c++
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.
Your videos are rekindling my interest to get back into programming. Thank you
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.
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!
Can you please do the review of your workplace? :) Which hardware do you use, keyboard, mouse, trackpad, etc.
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() != '
') ...
If you miss the return 0. It is automatically if needed will be included by the compiler.
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 got really happy to see how easy univ assignments will be and then I read comments below 😥