Tips for testing code in Competitive programming

Testing Coding problems can sometimes become hectic. Here are some tips to use while testing Algorithmic Programming Problems.

There are generally four major categories of defects in program:

1. Syntactical Errors
2. Semantic Errors
3. Run-time Errors / Exception
4. Logical Errors

Syntactical Errors

Syntactical errors are generally grammatical errors in a program.

To Check the program for Syntactical errors you should follow below steps:

• Compiling the Code in compiler
• Some Common Syntactical errors are:
  • Misplacing Braces, parentheses etc.
  • Misplaced end of comments
  • Typographical errors
  • Misplaced Keywords

Semantic Errors 

Semantic errors may obey grammar, but violate other rules of language.
Some Common Semantic Errors are:

• Perform incorrect operations on primitive data types.
• Invoking instance method which is not defined.
• Not declaring a variable before using it.

Runtime Errors / Exceptions

Runtime errors generally occur at the time of the program execution.
Examples of the runtime errors / exceptions are:

• Division by zero
• Array index out of bounds
• Number of format errors
• Null Pointer Exception

Logical Errors

Logic errors are a mistake in the design of the class or in the implementation of an algorithm.
Logical errors can be avoided by:

• Strive for clarity and simplicity
• Consider corner or extreme cases
• Thinking of the pre / post conditions
• Organizing the code

Testing Logical Errors in Code with Example

Testing Logical Errors / Bugs in code are difficult to find. Here is a walk-through of the testing logical errors in code with the help of an example.

Maximum Pairwise Product Problem – Given an array or a sequence of N numbers and goal is to find a number which can be obtained by multiplying some two numbers from this sequence.

Solutions

Naive Solution – O(N²)

Iterate through every possible pair in the sequence using a nested for loop.

Efficient Approach:

The best solution for this problem would be to find the two largest and two smallest numbers from sequence and return a maximum of products between (largest, second largest) and (smallest, second smallest). And that would be in O(n) time.

Below is the implementation of the above approach:

 
Testing

You can do a variety of testing on your code, but most common testing can be this three :

1. Before submitting the code for evaluation one should test the code with example tests from the problem statement, which are the easiest to type in and verify.
2. Small corner cases, which can be typed in by hand and for which you know the answers. We have tackled some corner cases in our implementation also: (long long) for tackling integer range issues, (if statements) and (abs) checks.
3. Big random tests, which are generated by simple scripts to test time complexity. This type of testing is called as Stress testing.

Stress Test your Code:

This is actually a pretty standard situation when solving algorithmic programming problems. So what is stress testing? In general, it is a script that creates random tests in an infinite loop, and for each test, it calls your solution on this test and an alternative correct solution on the same test and compares the outputs. If you find a test on which your solutions output differs, you can check which one of them returns the wrong answer, debug it and then rerun the stress testing script.

Below is the example of stress testing of code of above example problem:

 
This simple script is your stress test algorithm. Running this you can find that the previous implementations differ on some cases when duplicate elements appear in the array.

Now this is because of an overlooked mistake in the algorithm, i.e We check that number at position j is different from the maximum we’ve already found. But that’s exactly the problem. What we need is instead, that j must be different from large1 because we don’t want to find the same index, but we can find number which is equal to the first found maximum. So, instead of this comparison, what we actually need is to compare j with large1.

Final Solution without Errors: