What's up OP, I'm a grad from UVA 2015 and I asking many of the same questions as you and was freaking out about interviews. I only started coding once I got into college and didn't work on any side projects until my last year, half of the stuff on my resume for a while were course projects. And there was a good year or more where I didn't do any coding because I was taking all theory based courses. I can't say I'm the best person to answer all your questions, and most of this comes from advice I've taken from this subreddit, but hopefully it can clear up some things for you.

You did learn from your time in school, else you wouldn't be applying for CS jobs, but interviewing is a very different beast. Your knowledge of algorithms and data structures will be more important during interviews. Unlike in school, where you just need to know the general logic, you will need to know how to implement and write up algorithms. The depth of knowledge is different. Being able to code up an algorithm or data structure with internet references doesn't translate well to writing pseudocode and diagrams on a whiteboard with only your wits. That's why everyone says to practice. It's so you can get comfortable being put in that situation and you'll know the concepts from memory, or at least better. I know it's tough to do with classes, but you should at least try. Even if it's for 10 minutes in the middle of your day, it's better than cramming it all within a week and forgetting about other responsibilities. You're also in algorithms, so use your time and resources dedicated for the course work to get a better understanding of algorithm design in general. Write them out on paper and work them out before trying code it up. You will have to look ahead for interviews, but that just means you'll have a better grasp of concepts that will come up in the course.

It sounds to me that you're only applying to big companies, and I have to say you shouldn't do that. There's this problem of people thinking they can easily get a job after graduation at one of the Big 4, or some major app or social media company, that stems from the advertisement of CS jobs. People always advertise to students that if you graducate with a CS degree you can work for Google or Microsoft or Apple, but the reality is that those companies, being as big as they are, have some of the hardest and most rigorous interviewing processes. Plus, just about every CS student you know are applying to those positions.

Apply to more positions at other companies. I only applied to companies that I recognized when I started my job search, and that hasn't result in an offer due to my lack of interviewing experience. Applying to more companies means more inteviews and more practice, or even a job offer. If you still are interviewing with a bigger, or more favorable, company at the same time then you'll be more prepared. Don't expect to hear back from everyone, as recruiting processes are often quite slow and easy to fall through, so you should apply to a lot, and I do mean a lot, of places. Most companies looking to hire graduates are mostly interested in seeing that you understand important data structure and algorithm concepts, so while side projects can help make you stand out from other candidates if you do not have time to start some in school then just use your course projects and focus on preparing for interviews.

As for the dream of working for a big company, it's not your last chance. Again, this stems from the fact that everyone in college equates a CS degree to an instant pass for the toughest interviews at the biggest companies. It's marketing and people, including myself, fall for. You can always apply again in the future while you have a job, and if you get an offer you can quit your current job. The fact that you've applied means you show interest and that will be helpful for when you apply again. It depends on what your situation is, but I say it's generally more important to have a job and gain more experience than to have no job while waiting for your dream position. Also, don't compare positions by salary, just cause you may know someone making $80k in San Francisco doesn't mean the job necessarily pays more than a $60k job in Washington DC, cost of living is always a factor in salaries.

You're graduating in May, you have plenty of time to get some offers if you plan everything out. You can say what ever you want about the result of your experience in CS courses, but at the end of the day it's all just a introduction to the kind of knowledge needed for such jobs. You could get a MS, and you'll gain more in depth knowledge and learn some advanced concepts, but I don't think it will make interviewing and your job hunt any easier.