CareerCup

rearrange them in the format of interval: [-1,1] [-4,6] ...
then the problem becomes checking overlapping intervals.
just sort them on the base of starting point and binary search each end point in the sorted list

This solution occupies O(n) extra space and works in O(logn), Does it sound correct?:

I write down the max and min points of the circles and store them in an array using a data structure to identify the index of each point. Then, I sort them in nlogn.

Next I iterate through the array keeping note of circle starts and ends using a hashmap and whenver a circle ends, all the circles which are enveloping it add to the number of intersections. Hence, I add them up.

import java.util.Arrays;
import java.util.HashMap;


public class Circle {

	class node implements Comparable<node>{
		int value;
		int index;
		node(int index, int value) {
			this.index = index;
			this.value = value;
		}
		public int compareTo(Circle.node o) {
			return this.value - o.value;
		}
	}
	int[] A;
	node[] B;
	Circle(int[] in) {
		this.A = in;
		B = new node[A.length*2];

		for( int i = 0 ;i < A.length; i++) {
			B[2*i] = new node(i, i - A[i]);
			B[2*i+1] = new node(i, i + A[i]);

		}
	}

	int process() {
		Arrays.sort(B);
		int sum = 0, envelopes = 0, i =0;
		HashMap<Integer, Boolean> m = new HashMap<Integer, Boolean>();
		while( i < B.length) {
			System.out.println("node " +B[i].index +" value "+ B[i].value);
			if(m.containsKey(B[i].index))
			{
				m.remove(B[i].index);
				envelopes--;
				sum += envelopes;

			}else{

				m.put(B[i].index, true);
				envelopes++;

			}
			i++;
		}
		return sum;
	}
	public static void main(String args[]) {

		int[] A = {1,5,2,1,4,0};
		Circle c = new Circle(A);
		System.out.println(c.process());
	}

}

1. merge start / end of all intervals in ONE array, keeping a flag that marks whether it's a start or an end.
2. sort it.
3. scan the sorted array by updating two variables, i for open intervals and c for intersection count.
- if we meet a start point, count+=i and i++
- if we meet an end point, i--.

There you go.

For the example in the question, we get a sorted array of the intervals and scan/update like this

i = 0, c = 0
-4 start, c+=0, i=1
-1 start, c+=1, i=2
0 start, c+=2, i=3
1 start c+=3, i=4
1 end i=3
2 start, c+=3, i=4
4 end, i=3
4 end, i=2
5 start, c+=2, i=3
5 end, i=2
6 end, i=1
8 end, i=0
the result is c=11.

Time complexity is O(NlgN) and space complexity is O(N).

namespace ConsoleApplication1
{
    class Program
    {

        public class Interval : IComparable<Interval>
        {
            public int start;
            public int end;
            public Interval(int start, int end)
            {
                this.start = start;
                this.end = end;
            }

            public int CompareTo(Interval interval)
            {
                return this.start.CompareTo(interval.start);
            }
        }


        public static Interval[] IntArrayToIntervalArray(int[] A)
        {
            Interval[] newArray = new Interval[A.Length];
            for (int i = 0; i < A.Length; i++)
            {
                newArray[i] = new Interval(i - A[i], i + A[i]);
            }

            Array.Sort(newArray);
            return newArray;
        }

        public static int NumberOfDiscIntersections(int[] A)
        {
            Interval[] newArray = IntArrayToIntervalArray(A);
            int count = 0;
            for (int i = 0; i < A.Length; i++)
            {
                count += BinarySearchGetNumberOfIntersectingIntervals(newArray, i + 1, A.Length - 1, newArray[i]);
            }
            return count;
        }

        public static int BinarySearchGetNumberOfIntersectingIntervals(Interval[] A, int p, int r, Interval Int)
        {
            if (p <= r)
            {
                decimal x = (p + r) / 2;
                int q = (int)Math.Floor(x);
                if (A[(int)q].start < Int.end)
                {
                    return (q - p + 1) + BinarySearchGetNumberOfIntersectingIntervals(A, q + 1, r, Int);
                }
            }

            return 0;

        }


        static void Main(string[] args)
        {
            int[] A = new int[] {1,5,2,1,4,0};

            Console.WriteLine(NumberOfDiscIntersections(A));
            Console.ReadLine();
        }
    }
}

How can the expected complexity (assuming the expectation is taken over the draw of random numbers in your algorithm and not some sort of a random draw of discs) be O(n log n), when the size of the output for some trivial cases is O(n^2)?

Program:

#include <iostream>
#include <vector>

using namespace std;

struct sortFunc{
        bool operator ()(const pair<int,int>& p1, const pair<int,int>& p2) const
        { return p1.first<p2.first; }
};

int main(int argc, char* argv[])
{
        vector<int> v(argc-1, -1);
        for(int i=0; i<argc-1; i++) {
                v[i] = atoi(argv[i+1]);
        }

        vector<pair<int, int> >intVec(v.size());
        for(int i=0; i<v.size(); i++) {
                intVec[i] = make_pair(i-v[i], i+v[i]);
        }

        sort(intVec.begin(), intVec.end(), sortFunc());

        // Note : This is not n^2 but the order of results
        // This loop will break the moment we find that it cannot increment Overlaps
        int Overlaps = 0;
        for (int i=0;i<intVec.size();i++) {
                for (int j=i+1;j<intVec.size();j++) {
                        if (intVec[i].second < intVec[j].first) {
                                break;
                        } else {
                                Overlaps++;
                        }
                }
        }

        cout<< "Input is :"<<endl;
        for(int i=0; i<v.size(); i++) {
                cout<< v[i] << " ";
        }
        cout << endl;
        cout << "Overlaps : "<< Overlaps<<endl;
        return 0;
}

Output:

./a.out  1 5 2 1 4 0
Input is :
1 5 2 1 4 0 
Overlaps : 11

use stl, and it is much more convenient:

bool MyCompare(pair<int,int> p1,pair<int,int> p2){return p1.first<p2.first;}
bool MyCompare2(int p1,pair<int,int> p2){return p1<p2.first;}

int NumOfIntersection(vector<int> A)
{
	int N=A.size();
	vector<pair<int,int>> P;
	for(int i=0;i<N;i++)
	{
		int start_pt=i-A[i],end_pt=i+A[i];
		P.push_back(pair<int,int>::pair(start_pt,end_pt));
	}
	sort(P.begin(),P.end(),MyCompare);
	int res=0;
	for(int i=0;i<N;i++)
	{
		vector<pair<int,int>>::iterator iter=upper_bound(P.begin()+i,P.end(),P[i].second,MyCompare2);
		iter--;
		int id=iter-P.begin();
		res+=(id-i);
	}
	return res;
}

Use Interval trees. Search the page on Interval trees on Wikipedia.

My idea:
a> Build an array containing left point and right point of each pixel. Each left point or right point consume on item in the array. Here is some extra trick, shift the original (left, right) ==> (left*2-1, right*2). The extra logic is making sure we can sort easily for the case that left value of some point is the same right value of some point (or even same point, in which its range is zero), in which case we need to be sure left value should be put before the right value(single point contact is till contact). And also we need to know if it is left /right value according to its value, easily.
b> merge sort the array. We need to use merge sort because worse case of quicksort is bigger than O(nlogn). The array's len is 2N, (left +right), so the merge sort will have O(2NLOG(2N)), still O(NLOGN)
c> Go through the sorted array, if it is left value, which means we found start of a new disk, so we can add preexisted disk number as total number of overlappled pair number and then increased of preexisted disk number. If it is right value, which means we found end of a new disk, we need to delete the preexisted disk number.
d> This logic bellow does not care the number limiting issue. (such 10,000,000). Some extra logic could be added for that.
e> Time complexity is O(NLOGN)+2N , still O(NLOGN). Space complexity, 2N for array, N for mergeSort, so still O(N).

I like zyfo2's answer but it's a little terse so I'll offer my elaboration:

1. We are given a list of discs already sorted by the location of the center of disc. Create a second list of discs that is sorted by the location of the top of the disc. If we use mergesort, this operation will take O(N log N) in the worst case and O(N) space complexity in the worst case.

2. Iterate through the entire given list of discs. For every disc i, search the second list (sorted by top of disc) for the first disc whose top is located at or below the center of disc i. This is the first intersecting disk.

3. Then search for the last disc whose top is located at or above the bottom of disc i (computed as i+A[i]). This is the last intersecting disc. Both searches take O(log N) so we haven't increased the complexity.

4. The difference between the first and last disc (plus one) is the number of discs intersecting with disc i. Add this to a running total.

When we reach the end of the list, the running total will contain the solution. Note that since we are only looking for discs below disc i, we'll never count the same intersection twice.

Here's my solution:
1. Sort the circles by their bottom point (center - radius).
2. Initialize a min-heap that will be used to hold circles with their top point (center+radius) as key.
3. For each circle in the sorted list, compare its bottom value with the min circle on the heap, and pop from the heap all circles that their top point is lower than the current circle's bottom. The rmaining circles in the heap intersect the current circle, since their bottom point is lower than the current circle's bottom point, and their point is higher than the current circles bottom. So add the size of the heap to the count of intersecting circles. Push the current circle onto the heap.
4. Repeat step 3 for all the circles.

Here's my solution:
1. Sort the circles by their bottom point (center - radius).
2. Initialize a min-heap that will be used to hold circles with their top point (center+radius) as key.
3. For each circle in the sorted list, compare its bottom value with the min circle on the heap, and pop from the heap all circles that their top point is lower than the current circle's bottom. The rmaining circles in the heap intersect the current circle, since their bottom point is lower than the current circle's bottom point, and their point is higher than the current circles bottom. So add the size of the heap to the count of intersecting circles. Push the current circle onto the heap.
4. Repeat step 3 for all the circles.

import heapq

def disc_intersect(l):
  range_l=[(center-radius, center+radius) for (center,radius) in enumerate(l)]
  range_l.sort()
  h=[]
  tot_cnt=0
  for (start, end) in range_l:
    while len(h)>0 and start>h[0]:
      heapq.heappop(h)
    tot_cnt+=len(h)
    heapq.heappush(h, end)
  return tot_cnt

def main():
  l=[1,5,2,1,4,0]
  print disc_intersect(l)

I got a similar question on my Google interview... and blew it. I wish I had spent more time solving this problem. Ironically, I figured out the optimal solution the next day while walking my dog. It uses DP and goes like this:

1. Sort the discs by top
2. Keep a "meta-disc" in memory and initialize it to the first disc in the sorted list. The meta-disc represents the preceding series of discs that overlap.
3. Iterate through the sorted list, from disc 2 to disc n.
4. If the top of disc i is below the bottom of the meta disc (i.e. we found a gap) re-initialize the meta-disc to disc i and proceed to the next disc.
5. However if the top of disc i is within the meta-disc, it must overlap with one of the preceding discs and we increment the overlap count.
6. Also, if the bottom of disc i is below the bottom of the meta-disc, enlarge the meta-disc by setting it's bottom to the bottom of disc i.

The meta-disc is our DP subproblem-holder. It saves us from checking every disc or searching for particular discs.

The complexity is O(n log n) due to the sort. The iterations take O(n) and don't require a binary search so each iteration takes O(1).

how about this? Create another array of size N. Now for each point from 0 to N, find out how many discs reach that point. (So we init the array to 0 and for all discs d, we increment values from arr[d] to arr[d-radius(d)] and arr[d] to arr[d+radius(d)]. Now the number of overlaps at any point p = arr[p]C2 (arr[p] Choose 2).

Can some one explain how A[0] and A[1] intersect??
A[0] spans from (-1,1), and A[1] goes from (-4,6). How can these two intersect when A[0] is completely inside A[1]

Two Arrays, one with starting, one with ending points.
Sort both O N * log N
Iterate on both count the number of intersections O N.


Uses exactly O(N) extra memory and O (n * log n ) computationally.

package com.arrays;

import java.util.Arrays;
/**
 
 * @author suketu
 *
 */
public class DiscIntersections {

    
    public static void main(String[] args) {
        
        
        int[] A = {1,5,2,1,4,0};
        
        int n = getNumberOfIntersections(A);
        System.out.println(n);
        
    }

    private static int getNumberOfIntersections(int[] a) {
        
        int[] endingPoints = new int[a.length],startingPoints = a;
        for (int i = 0; i < a.length; i++) {
            if(a[i] < 0) return -1;// this is a negative radius, I don't know what to do in that case.
            endingPoints[i] = i + a[i];
            startingPoints[i] = i - a[i];
        }
        Arrays.sort(startingPoints);
        Arrays.sort(endingPoints);
        int intersections = 0;
        int currentDiscs = 0;
        for(int i = 0, j = 0; i < startingPoints.length || j < endingPoints.length; ) {
            
            if( i < startingPoints.length && startingPoints[i] <= endingPoints[j]) {
                currentDiscs++;
                i++;
            } else {
                currentDiscs--;
                intersections += currentDiscs;
                j++;
            }
        }
        return intersections;
    }
}

Sounds like a programming contest question. Is it really google onsite question?

This solution has some drawbacks as mentioned by others. So, I remove it no to confuse anyone.

# include <stdio.h>
# include <conio.h>

int max(int a , int b){
    if (a>=b) return a;
    else return b;
}


int main(){
    int inp[7] = {2,4,0,1,6,5,3};
    int i,j, ctr=0;
    for(i = 0; i<=6; i++)
       for(j = i+1; j<=6; j++)
          if( max(inp[i], inp[j]) >= (j-i)) 
                ctr++;

              
    printf("%d", ctr); 
    getch();
 }

The o/p for above program is 17.

When i change the inp[7] to a sorted array, the o/p is 21. This 21 is basically the sum of all elements of the inp[] array.

2,4,1,0,6,5,3
6,5,4,0,3,2,1
* * * *

The asterisks show the positions where sorted array element is higher than original element.
Number of asterisks is 4.

Subtracting the number of astersiks from 21(sum of the array) gives 17.

I have tested it for few examples and seems to be fine.

So, sorting time complexity is nlogn, storing the sorted array has space complexity of n.