Difference between revisions of "Programming Practice"
(→Sites with Problems) |
|||
| (9 intermediate revisions by the same user not shown) | |||
| Line 2: | Line 2: | ||
= Sites with Problems = | = 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). | |
| − | '''[https://open.Kattis.com Open Kattis''' | + | * '''[https://hackerrank.com Hackerrank]''' |
| + | * '''[https://open.Kattis.com Open Kattis]''' | ||
| + | * '''[https://leetcode.com/ LeetCode]''' | ||
| + | |||
| + | = 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: [https://www.hackerrank.com/challenges/30-hello-world/problem hello world], [https://www.hackerrank.com/challenges/30-loops/problem loops], [https://www.hackerrank.com/challenges/30-arrays/problem arrays], [https://www.hackerrank.com/challenges/30-recursion/problem recursion], [https://www.hackerrank.com/challenges/30-sorting/problem sorting] | ||
= Why Your Program is Wrong = | = Why Your Program is Wrong = | ||
== 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 17: | Line 29: | ||
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''' | ||
Revision as of 00:01, 12 May 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).
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
