Counting disk intersections with TreeSet

Question

I am trying a Codility demo problem before taking a real test as part of a job application. One of the demos they have is the problem of counting the number of disk intersections for an array of disks.

Task description

Given an array A of N integers, we draw N disks in the 2D plane so that the I-th disk is centered on (0, I) and has a radius A [I]. We say that the Jth disk and the Kth disk intersect if J ≠ K and the Jth and Kth disks have at least one common point. Write a function: class Solution {public int number_of_disc_intersections (int [] A);

You can watch the test here .

There are some obvious O (n ^ 2) solutions with time complexity, but the goal is O (n * log (n)).

I came up with this that works on any examples I have provided and on a simple test case given by codility ([1, 5, 2, 1, 4, 0]), but Codility tells me that most are different, but I can’t understand why.

This, of course, should be O (n log n), since adding each of n disks to a TreeSet is log n, and then we iterate over all disks using only the O (1) operation TreeSet.headSet ().

 import java.util.*; class Circle implements Comparable<Circle> { long edge; int index; Circle (long e, int i){ edge = e; index = i; } long getRightAssumingEdgeIsLeft(){ return (long)(2*index - edge + 1); } @Override public int compareTo(Circle other){ return Long.valueOf(edge).compareTo(other.edge); } } class Solution { public int number_of_disc_intersections ( int[] A ) { int N = A.length; if (N<2) return 0; int result = 0; SortedSet<Circle> leftEdges = new TreeSet<Circle>(); for (int i=0; i<N; i++) { leftEdges.add( new Circle( (long)(iA[i]), i ) ); } int counter = 0; for (Circle c : leftEdges) { long rightEdge = c.getRightAssumingEdgeIsLeft(); Circle dummyCircle = new Circle (rightEdge, -1); SortedSet<Circle> head = leftEdges.headSet(dummyCircle); result += head.size() - counter; if (result > 10000000) return -1; counter++; } return result; } } 

Answer 1

Another algorithm ( O(N log N) ):

This bad script drawing:

Can be translated into a list of ranges: (not exactly the same scenario)

fig. 2

O (N log N): First, we sort the markers, making sure that the green markers appear before the red ones, if we want to consider tangent disks as overlaps.

O (N): we scan from left to right, first total = 0 and overlaps = 0 . Each time we press the green marker, total += 1 and on each red marker, total -= 1 . In addition, on each green market, if total > 0, then overlaps += total .

Black numbers in figure 2 total at each step; orange overlaps .

Then overlaps should be the answer.

See a rough implementation here: http://ideone.com/ggiRPA

Answer 2

There is an easier way ...

• Create 2 arrays of N elements (leftEdge, rightEdge).
• For each element, calculate the left and right edges (index - / + value) and set it to arrays.
• Array sorting.
• For each element in the rightEdge array, loop through the leftEdge array to find the first greater or equal element. Save the number of remaining items and the current index. For the next cycle of starting an element from a stored index ...

Thus, we really look at each sorted array only once, so the complexity of the algorithm is O (N log N).

Answer 3

This method does not require special classes such as circles or complex containers such as PriorityQueue or TreeSet. Simple integer arrays are all that is needed. This is O (N * logN). Language is Java.

 public int numberOfDiscIntersections(int [] A) { // 0 <= A.length <= 100,000 // 0 <= A[i] <= 2147483647 int [] leftEdge = new int[A.length]; int [] rightEdge = new int[A.length]; int maxLength = 100000; // maxLength is used to prevent integers > 2147483647 // and integers < -2147483647 for (int i = 0; i < A.length; i++) { leftEdge[i] = i - A[i]; rightEdge[i] = i - maxLength + A[i]; } Arrays.sort(leftEdge); Arrays.sort(rightEdge); int sum = mergeAndCountOverlaps(leftEdge,rightEdge, maxLength); return sum; } 

A merge procedure is a modified merge from a merge sort. It combines two sorted arrays, keeping the sort order intact and adding overlap counting functionality. In this case, we do not need to return the combined array, only the number of matches.

 private int mergeAndCountOverlaps(int[] leftEdge, int [] rightEdge, int maxLength) { int leftIndex = 0; int rightIndex = 0; int sum = 0; int total = 0; while ((leftIndex < leftEdge.length) || (rightIndex < rightEdge.length)) { if ((leftIndex < leftEdge.length) && (rightIndex < rightEdge.length)) { boolean compareLeftEdgeandRightEdge; if (leftEdge[leftIndex] < -2147483647 + maxLength) { compareLeftEdgeandRightEdge = leftEdge[leftIndex] <= rightEdge[rightIndex] + maxLength; } else { compareLeftEdgeandRightEdge = leftEdge[leftIndex] - maxLength <= rightEdge[rightIndex]; } if (compareLeftEdgeandRightEdge) { // a new left edge sum += total; if (sum > 10000000) { return -1; } total++; leftIndex++; } else { // a new right edge total--; rightIndex++; } } else if (leftIndex < leftEdge.length) { // a new left edge sum += total; if (sum > 10000000) { return -1; } total++; leftIndex++; } else if (rightIndex < rightEdge.length) { // a new right edge total--; rightIndex++; } } return sum; } 

Answer 4

First: you defined compareTo (), but not equals (). TreeSet JavaDoc says: "the order maintained by the set (regardless of whether an explicit comparator is provided) must be consistent with equals"

Another oddity: I do not understand what the edge field is, and why you set it to i - A[i] .

Answer 5

I did the same demonstration in preparation for programming. I didn’t get a solution developed on time and got a terrible result (something in my teens). However, intrigued by the question, I went ahead and completed it myself. Here is my solution:

  ============================================================================ Name : cFundementalsTest.c Copyright : Your copyright notice Description : Hello World in C, Ansi-style ============================================================================ */ #include <stdio.h> #include <stdlib.h> #include <string.h> #include <math.h> int main(void) { int N = 5; int A[6] = {1, 5, 2, 1, 4, 0 }; int pos_1, pos_2; int total; for(pos_1=0;pos_1<=N;pos_1++) { for(pos_2=pos_1+1;pos_2<=N;pos_2++) { if(A[pos_1] + A[pos_2] >= abs(pos_1 - pos_2)) { // they share a common point total++; printf("%d and %d\n",pos_1, pos_2); if(total > 10000000) return(-1); } } } printf ("\n\n the total is %d",total); } 

and here are the results that look correct:

 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 the total is 11 

Answer 6

At Codility, you need to solve this with sorting, right? The following is a JavaScript solution that has passed 100% testing .

We use two arrays of ranges along the x axis. The values ​​in both arrays are the same, but are first sorted by the from parameter and second, to (as ascending). Then we scan both arrays at the same time and track the overlap to count distinctive pairs.

You can play with this code in jsbin .

 function solution(arr) { const r1 = arr.map((n, i) => ({from: i - n, to: n + i})).sort((a, b) => a.from - b.from) const r2 = r1.slice().sort((a, b) => a.to - b.to) let i = 0, j = 0 let overlaps = 0 let pairs = 0 while (i < r1.length || j < r2.length) { if (i < r1.length && r1[i].from <= r2[j].to) { pairs += overlaps if (pairs > 10000000) { return -1 } overlaps++ i++ } else { overlaps-- j++ } } return pairs } 

Answer 7

Suppose that j is always greater than i, in order to satisfy the interaction of two circles, the inequality must always be satisfied:

 |R(i) - R(j)| <= j - i <= R(i) + R(j) 

This is another way of saying:

 abs(A[i] - A[j]) <= j - i <= A[i] + A[j] 

I have not tested, but I think it works. Hope this helps.

 #include <stdlib.h> public int number_of_disc_intersections(int[] A){ int len = A.length; int intersections = 0; for(int i = 0; i < len - 1; i++){ if(A[i] <= 0){ continue; } for(int j = i + 1; j < len; j++){ if(A[j] <= 0){ continue; } if(abs((A[i] - A[j]) <= j - i) && (j - i <= A[i] + A[j])){ intersections ++; } } } return intersections; }