Difference between revisions of "Programming Practice"
(→Sites with Problems) |
|||
| (5 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
This page is meant to get you started working on programming problems that are similar to ones you will see in programming contests and job interviews. | This page is meant to get you started working on programming problems that are similar to ones you will see in programming contests and job interviews. | ||
| − | |||
| − | |||
| − | |||
| − | |||
= Sites with Problems = | = Sites with Problems = | ||
| Line 10: | Line 6: | ||
* '''[https://hackerrank.com Hackerrank]''' | * '''[https://hackerrank.com Hackerrank]''' | ||
* '''[https://open.Kattis.com Open Kattis]''' | * '''[https://open.Kattis.com Open Kattis]''' | ||
| + | * '''[https://leetcode.com/ LeetCode]''' | ||
| + | |||
| + | = Contests = | ||
| + | Each of the sites above may hold contests periodically. The following are additional ones that Indiana State students have participated in. | ||
| + | * '''[https://codevita.tcsapps.com/#sampleQuestions TCS CodeVita]''' | ||
| + | * '''[https://icpc.global/worldfinals/past-problems ICPC]''' | ||
= Getting Started = | = Getting Started = | ||
| Line 16: | Line 18: | ||
* Figure out an algorithm that will solve the problem. You should try possible algorithms on paper using the sample input and sample output given. If you cannot solve the sample input and sample output then there is no point writing a program that won't be correct. | * Figure out an algorithm that will solve the problem. You should try possible algorithms on paper using the sample input and sample output given. If you cannot solve the sample input and sample output then there is no point writing a program that won't be correct. | ||
* When you think you have an algorithm that will work, write the code. Test the code on the sample input and sample output given. Make sure it gives the right answer. | * When you think you have an algorithm that will work, write the code. Test the code on the sample input and sample output given. Make sure it gives the right answer. | ||
| − | * After you have code giving the right answer on the sample input/output, submit it on the site. If it is marked as incorrect, carefully read the problem again, carefully look your code again - there must be some case you are not handling properly. | + | * After you have code giving the right answer on the sample input/output, submit it on the site. If it is marked as incorrect, carefully read the problem again, carefully look over your code again - there must be some case you are not handling properly. |
Some problems to solve to get started. These are fairly easy and should get you familiar with submitting problems. | Some problems to solve to get started. These are fairly easy and should get you familiar with submitting problems. | ||
| Line 24: | Line 26: | ||
== Automatically Checked == | == Automatically Checked == | ||
| − | Programming contests are normally checked by scripts that run your program and check whether your | + | Programming contests are normally checked by scripts that run your program and check whether your output is ''exactly the same'' as the model solution. If the correct output is "Hello World!", your program would be incorrect if it output "Hello World." or "hello world!". If the problem asks for an integer then make sure to output an integer (not a floating point number). So you need to pay careful attention to what the problem asks for in terms of output. |
== Run time == | == Run time == | ||
| Line 32: | Line 34: | ||
The following are some of the most common algorithms/techniques that you will see with these problems. | The following are some of the most common algorithms/techniques that you will see with these problems. | ||
| − | # '''Simulation''' - the problem gives rules to be used to run a simulation, and you need to run the simulation until a certain point and output the result. | + | # '''Simulation''' - the problem gives rules to be used to run a simulation, and you need to run the simulation until a certain point and output the result. Here are a few non-trivial ones (but not toooo hard) to try out - [https://www.hackerrank.com/challenges/an-interesting-game-1/problem Gaming Array], [https://www.hackerrank.com/challenges/new-year-chaos/problem New Year Chaos]. Note - sometimes there are additional tricks needed to make the program faster, but the first step is to just follow the rules to keep track of things and see what happens in the end. |
# '''Brute force''' | # '''Brute force''' | ||
Latest revision as of 16:13, 1 November 2024
This page is meant to get you started working on programming problems that are similar to ones you will see in programming contests and job interviews.
Contents
Sites with Problems
Each of these sites requires you to create an account to submit your potential solutions, and each is free to use. You will often want to debug your code on your own computer and just submit your solutions on the site when you think your code is correct (at least gives the correct answer on some test input).
Contests
Each of the sites above may hold contests periodically. The following are additional ones that Indiana State students have participated in.
Getting Started
- Create an account on whatever site you are taking a problem from.
- Read the problem carefully. Make sure you understand the sample input and sample output given for the problem.
- Figure out an algorithm that will solve the problem. You should try possible algorithms on paper using the sample input and sample output given. If you cannot solve the sample input and sample output then there is no point writing a program that won't be correct.
- When you think you have an algorithm that will work, write the code. Test the code on the sample input and sample output given. Make sure it gives the right answer.
- After you have code giving the right answer on the sample input/output, submit it on the site. If it is marked as incorrect, carefully read the problem again, carefully look over your code again - there must be some case you are not handling properly.
Some problems to solve to get started. These are fairly easy and should get you familiar with submitting problems.
- Hackerrank: hello world, loops, arrays, recursion, sorting
Why Your Program is Wrong
Automatically Checked
Programming contests are normally checked by scripts that run your program and check whether your output is exactly the same as the model solution. If the correct output is "Hello World!", your program would be incorrect if it output "Hello World." or "hello world!". If the problem asks for an integer then make sure to output an integer (not a floating point number). So you need to pay careful attention to what the problem asks for in terms of output.
Run time
Some contest problems are fairly easy to solve with an inefficient program, but the real work is figuring out how to make your program faster. Oftentimes, your program needs to finish in around 1-5 seconds to be fast enough. For a C program, a single loop that goes through around 100 million iterations might be okay. For a Python program, a single loop that goes through 1 million iterations might be okay. If you have nested looped, you should count how many times the innermost part runs - two nested loops that each go 1 to 1000 will end up running the innermost code 1 million times.
Algorithm Techniques
The following are some of the most common algorithms/techniques that you will see with these problems.
- Simulation - the problem gives rules to be used to run a simulation, and you need to run the simulation until a certain point and output the result. Here are a few non-trivial ones (but not toooo hard) to try out - Gaming Array, New Year Chaos. Note - sometimes there are additional tricks needed to make the program faster, but the first step is to just follow the rules to keep track of things and see what happens in the end.
- Brute force
- Dynamic programming
- Graph problems
- Greedy
- Sorting
- Math tricks
