DSA - 4

Why are my perf-test cases failing in finding K closest points to the origin?

Do you understand the error?

Perf-test cases fail if the required performance is not  met, in some cases if you unlock and run these you might also get the right output. 

Where is the error occurring?

If Only performance test cases are failing either the time complexity of your code is not meeting the requirements or you’re not using the right data types to store the value. Can you look at the code and check what is the time complexity of it?

Why do you think you are seeing this error? What might be causing it?

You need to check mainly two things here to figure out the exact error:

1. What is the time complexity of your code overall? Can it be improved?

2. When we multiply 2 int values, the result might exceed the int limit, are we type casting them?

How to Debug this? To debug this issue, I would recommend the following steps:

In case 1, we can solve this problem in O(N*log(K)) using a max heap, check your approach and try to make changes to achieve this.

In case 2,  you need to note that the values in perf test cases are of size long and you need to make changes so you’re comparing longs and not int.

If you’re trying to use a comparator in java that causes an issue as well since the values are long and int compare won't be able to compare them, to solve this you have to write a class that holds a long value and index which can be used to make your priority queue.

You can create a java class which can hold the distance and index, then the priority queue can be made of this type and a comparator can be used on it:

    static class CustObj{

        long dist=0;

        int idx=0;

        CustObj(long d,int i){

            dist=d;

            idx=i;

        }

    }

Why do we get overflow or depth exceeded when doing recursion?

Do you understand the error?

As the error says we have an overflow or depth exceeded, which means that our recursion stack is filling up more than it can hold.

Where is the error occurring?

The error will be in the recursive function, can we check what we are doing there? How many times is the function being called?

Why do you think you are seeing this error? What might be causing it?

There are two possible cases for this:

1. We don't have a base case on which out recursion stops

2. The number of recursive calls exceeds the recursion limit set by the language.

How to Debug this? To debug this issue, I would recommend the following steps:

For case 1, it is suggested to check the condition where your recursion is breaking, if this is not met you will have never-ending recursion calls leading to a recursion stack overflow.

This would cause an error:

fib(int n)

{

return fib(n - 1) + fib(n - 2);

}

Adding the case where recursion has to stop would fix this:

fib(int n)

{

if (n <= 1) return n; 

return fib(n -1) + fib(n - 2);

} 

For case 2, although this is a rare case and only happens in a few problems, the recursive calls might exceed the limit set by the compiler. Languages like Python only have a recursion depth limit of 1000 by default, this can be changed in some cases and we provide this in the given template when needed, but even this is not enough for a few problems and we need to find a different approach to solve the problem.