[Coding] [Algorithm] Number-of-disc-intersections

For Interview purpose, right now I doing some online coding test: using codility

Here is the quesiton:

Given an array A of N integers, we draw N discs in a 2D plane such that the I-th disc is centered on (0,I) and has a radius of A[I]. We say that the J-th disc and K-th disc intersect if J ≠ K and J-th and K-th discs have at least one common point.

Write a function:

int solution(NSMutableArray *A);

that, given an array A describing N discs as explained above, returns the number of pairs of intersecting discs. For example, given N=6 and:

A[0] = 1  A[1] = 5  A[2] = 2 
A[3] = 1  A[4] = 4  A[5] = 0  

intersecting discs appear in eleven pairs of elements:

• 0 and 1,
• 0 and 2,
• 0 and 4,
• 1 and 2,
• 1 and 3,
• 1 and 4,
• 1 and 5,
• 2 and 3,
• 2 and 4,
• 3 and 4,
• 4 and 5.

so the function should return 11.

The function should return −1 if the number of intersecting pairs exceeds 10,000,000.

Assume that:

• N is an integer within the range [0..100,000];
• each element of array A is an integer within the range [0..2147483647].

Complexity:

• expected worst-case time complexity is O(N*log(N));
• expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).

Elements of input arrays can be modified.

Copyright 2009–2013 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

Here is my solution write in Objective-C which only got 62 points in Codility(due to timeout error in some question.)

The time complexity is O(n^2)

Space complexity is O(1)

#import <Foundation/Foundation.h>

int solution(NSMutableArray *A) {

    // write your code in Objective-C 2.0

      if(!A || [A count] <1) return 0;

          long resultCount = 0;

          for(int i = 0; i < [A count] ; i++){

              for(int j = i+1 ; j < [A count] ; j++){

                    

                  if(([(NSNumber *)A[j] longLongValue]+[(NSNumber *)A[i] longLongValue]) >= j-i){

                      resultCount ++;

                        //NSLog(@"print i = %d, j = %d",i,j);

                  }

                  if(resultCount > 10000000)

                  {

                        return -1;

                  }

              }

          }

          return resultCount;

       

}

//Improvement, I think I can make some performance improve using sorting.

First, produce a sorting array I-A[I]( the left bound of each disk) and add I +A[I] also in the structure.

struct element{

      int leftBound; (leftBound as sorting index)

      int rightBound;

}

So, start traverse the left bound from X,

Pseudo code may be

for X = 1~ X

      for(Y = X+1 && element[Y].rightBound<=Y)

        counter ++

The series of discussion can be found in here :   Number of Disc intersection Discuss in Statck overflow

Here is another smart guy claims that he has  O(N+M) time complexity with O(N) space complexity.

###Updated:

When I`m trying  to implement the algo that I mention above, by using a self-defined  @interface in Codility (WT.....! they didn`t support....).

So I use struct instead, how ever, objective-C`s NSArray only support NSObject, Here is the solution: Wrap a struct in Objective-C. 

Another challenge is coming, When I sorting by NSArry using this function sortedArrayUsingComparator:NSComparisonResult............ Actually, it`s too slow....

So I drop the method, by using the default struct, and using native ..... qsort

Perfect!!! I got 93 score in Codility

#import <Foundation/Foundation.h>
struct _DiskBound{
    long long leftBound;
    long long rightBound;
};
typedef struct _DiskBound DiskBound;
    
int compare (const void * first, const void * second){
    long long f = ((DiskBound *)first)->leftBound;
    long long s = ((DiskBound *)second)->leftBound;
    //NSLog(@"Current Sorting %lld, %lld",f,s);
    if(f > s )return 1;
    if(f < s) return -1;
    return 0;
    
}

int solution(NSMutableArray *A) {
    // write your code in Objective-C 2.0
if(!A && [A count] < 1) return 0;

    int resultCount = 0;
    
    DiskBound diskBound[[A count]];
    for(int i = 0; i < [A count] ; i++)
    {
        diskBound[i].leftBound =i-((NSNumber *)A[i]).integerValue;
        diskBound[i].rightBound =i+((NSNumber *)A[i]).integerValue;
    }
    qsort(diskBound, sizeof(diskBound)/sizeof(diskBound[0]), sizeof(DiskBound), compare);
    
    for (int i = 0; i < [A count]; i++){
        long long currentBound = diskBound[i].rightBound;
        for (int jj = i+1; jj < [A count] && diskBound[jj].leftBound <= currentBound; jj ++)
        {
            resultCount ++;
        }
        
        if(resultCount > 10000000)
            return -1;
    }
    return resultCount;
}

Summary:

The performance with Objective-C in Codility is relatively slower than other language. Their measurement of time complexity is the running time not from the code, I guess. So facing these kinds of mathematical problem. Using native C language can help you to do more faster and get higher grades.