Programming Practice

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.

For the spring of 2021 we will meet Mondays at 9pm on Zoom to go through some of the problems. See your email for the Zoom link.

We have a group on MS Teams to communicate and store files. The link to request to join is here.

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).

• Hackerrank
• Open Kattis

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 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 input 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.

1. 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.

1. Brute force

1. Dynamic programming

1. Graph problems

1. Greedy

1. Sorting

1. Math tricks