CareerCup

i doubt this is a real FB interview question because the problem statement is exactly the same as appears in a textbook:
http: // web.engr.illinois.edu/~jeffe/teaching/algorithms/notes/05-dynprog.pdf
see page 22 problem 10. an exercise of DP. probably some student who tries to figure out the solution posted it here :(

I think this problem can be solved using Dynamic Programming with O(N^2) time and O(N^1) space. (BUT I CAN BE WRONG...)

Assume it takes constant time to determine whether 2 lines intersect or not.

Consider case where there are N lines and the maximum subset of N lines among which no lines intersect is S(N).

Now let's add the (N+1)th line. The maximum subset of (N+1) lines among which no lines intersect, i.e. S(N+1), can only fall into following 2 case:
1) The (N+1)th line is not in S(N+1).
In this case, S(N+1)_case1 = S(N)

2) The (N+1)th line is in S(N+1).
In this case, in N iterations, we find out the lines which will intersect with the (N+1)th line, denoted by I(N+1). Then we exclude above lines from S(N), which gives S(N+1)_case2 = S(N) + (N+1)th line - I(N+1).

Then, the final S(N+1) must be max(S(N+1)_case1, S(N+1)_case2).

In sum, for each line we need N iterations to find out I(N) and we need a length-N array to store S(N), hence O(N^2) run time complexity and O(N^1) space.

EDIT: this is actually wrong, see anantpushkar009's comments for discussion

A key insight is that this problem is the same as unweighted interval scheduling, just around a circle. Consider two line segments l1 and l2 represented by the following points:

l1: (p1, p2)
l2: (p3, p4)

The only way that these line segments intersect is if p2 is "further along" on the unit circle than p3 or p4 is "further along" on the unit circle than p1. An nice way to represent distance on the unit circle is radians, which we can get by taking the inverse tangent of each point! One subtlety is that we need to normalize the tangent to a certain range: I'll use 0 to 2pi. In python:

import math

def arctan(x, y):
	atan = math.arctan2(x, y)
	while atan < 0:
 		atan += 2 * math.PI
	while atan > 2 * math.PI:
		atan -= 2 * math.PI
	return atan

def transform(L):
	transformed = list()
	for line in L:
		new_point = list()
		for x, y in line:
			new_point.append(arctan(x, y))
		transformed.append(new_point)
	return transformed

Now that we have a "transformed" set of line segments, each with a start and finish angle, the problem is identical to the greedy algorithm for maximum interval scheduling. Sort all the line segments by order of finish angle, add each line segment one at a time and remove all conflicting line segments with each iteration. (see an algorithms textbook for a proof):

def no_intersection(L):
	T = transform(L)
	T = sorted(T, key=lambda segment: segment[1]) # sort by finish angle
	result = list()

	i = 0
	while i < len(T):
		result.append(T[i])

		# find the next nonconflicting interval
		j = i
		while j < len(T) and T[j][0] < T[i][1]: 
			j += 1
		i = j
	
	return result

If you wanted the original line segments, you could also store the mappings in a hash table in the transforming step.

Time complexity is O(nlogn) for the sorting step in the greedy algorithm

This idea builds up from the solution given by yoavzimmerman (by reducing the given problem to unweighted interval scheduling problem by using angles instead of points). The problem with that was, it failed because of cyclic nature of intervals. We can get through that in the following way:
1. If there exists an angle at which no line exists, ie, if there exists theta such that a ray from origin at theta wrt x-axis passes through no line, we rotate x-axis by angle theta. Now we no more have any cyclic nature in the intervals.
2. If the above does not exist, we choose a pair of lines that intersect, say l1 and l2. Both of these can not be together in a solution. So, we apply interval scheduling on L-l1 and L-l2 (both of these set will satisfy the condition#1) and return the max of these two.

To check existence of theta, run a line sweep algorithm[O(n)]. The rest can be done in nlogn time. So, total complexity nlogn.

EDIT : As in the worst case, every ray from origin might intersect O(n) number of lines, the worst case complexity will be O(n^2 * logn)

Now that I think about it, isn't this the same as finding the "maximum independent set", which is NP-hard?

To see this, first represent the line segments as a graph instead. Let each line segment be a vertex, and let there be an edge between 2 vertices if the corresponding line segments intersect. Isn't the original problem of finding the maximum subset of L equivalent to finding the maximum subset of vertices such that they cover the whole graph, without any 2 vertices being adjacent?

I was wrong.

Let the lines be L1, L2,L3, ..., Ln. One idea is to define the sub problem as D(i, j, k) = max # of non intersecting line segments between Li & Lj using { L1, L2, ..., Lk }, then

D(i, j, k) = 0 if Li and Lj intersects (can be O(1))
max(D(i, j, k-1), D(i, k, k-1)+D(j, k, k-1))

Let F(i, j) =- D(i, j, n)

then for each Li, we find max F(i, j) among all Lj's that are on one side of Li
+max F(i, j) among all Lj's that are on the other side of Li

Do this for each Li, and record the max

O(N^3)

After digesting the comments by guruqu & gen-y-s, here's how I understood the dynamic programming solution.

(1) First convert each point to some angle such that they can be sorted, while keeping track of which segments they correspond to - O(n)
(2) Sort the angles - O(nlogn)
(3) You should now end up with an array (eg. [5 2 3 4 2 1 4 3 5 1]). The numbers correspond to the line segments.
(4) Note that in the example above, {534} is the solution. Also notice how the "longest non-contiguous palindrome" in the array is 5x34xx435. It should be easy to see that the numbers constituting the "longest non-contiguous palindrome" are actually the same line segments as the solution.
(5) Finally, due to the cyclic nature, the array could have been shifted like [2 3 4 2 1 4 3 5 1 5] instead. To accommodate this, you actually need to find the 2 "longest non-contiguous palindromes" in the array. In this case they are 34xx43 and 5x5. So the solution is simply the line segments from the 2 "longest non-contiguous palindromes".
(6) The optimal substructure should now be obvious. Basically DP[i][j] contains the optimal solution from point i to point j (inclusive). You then build the DP matrix starting from length 1 to 2n. At each step, set DP[i][j] = (arr[i] == arr[j] ? 1 : 0) + (max(DP[i][k] + DP[k+1][j]) for k=i to j-1). Populating this matrix requires O(n^3) time.

The algorithm takes O(n^3) time and O(n^2) space. Hope I haven't missed anything.

Recursive procedure:
For each segment s do:
[segment s had broken circle into two sectors, s1 and s2]
run recursive procedure on segment set that fully fit in s1 and similarly with s2, sum them up and plus one for selected one.
Select max sum from for loop and return

Note. in the second recursion and on, selected segment will be breaking current sector into 3 sectors, so sum up from 3 recurcsive procedures.

Time analizes:

T(n) = n * 3T(n/3)
T(1) = 1

n^log n. Which is better than exponentional needed for straight forward solution to coloring problem.

Now, we can enhaunce solution to each sector with caching. There should be O(n^2) of such sectors, so the time complexity should be O(n^2) because all the time solving this we are filling each cache entry and once done, the rest will complete.

As discussed earlier, convert to angles. Now, _if there is a point_ on the circle which does not belong to any segment, rotate the set so that it become 0. Now we've got a "movie scheduling problem" from Skiena's book, which is solved by selecting the interval with the leftmost right border, eliminating intersections and then repeting until all the intervals are considered. Should be n*log(n).

The next is a wild guess, haven't had time to think over yet:
If there is _no such a point_, maybe something like this will work: rotate so that the smallest sector starts at 0, apply the algorithm, above; then revert angels (i.e. go clockwise), so that we start from another side of the smallest sector and go opposite direction; repeate the algorimth and choose the best of two results.
If there are multiple minimums, we may repeat it for each, so it's n^2. (However, not sure still if this is accurate for border conditions)

This problem is O(n^2) solvable
take a point on the circle (0,1) say.. now for each line get the two angles formed from the two end points w.r.t x axis, say (alpha, beta) such that alpha<beta so for each line you will get these angles (a0,b0), (a1,b1), (a2,b2)....
sort them on their first index(O(nlogn) and then find the largest non-decreasing sequence on the second index..O (n^2)

This is actually a conceptually simple problem to solve.

Since the lines are all on the unit circle, each line bisects the circle into two halves. For example, a horizontal (-1,0 to 1,0) line bisects the circle into 0->180 and 181 -> 359 degrees.

All lines that will intersect with this one must have one vertex in the first half and one vertex in the second. In the previous example, suppose we have a line where one vertex is at angle 90. If the line intersects then the second vertex must be between 181 and 359, Otherwise, the line is conceptually on the top of the unit circle and will not intersect.

Once this comparison is found, we can build a simple n^2 algo to search for lines that don't intersect anything. We have to leave the intersected lines in because there may be another line further in the list that only intersects with this one.

Observation : 2 lines(x1,y1), (x2,y2) intersect iff on the circle x2 comes between x1 and y1 or wise verse. Assume all the lines are maked as (x1,y1), (x2,y2).....(xn,yn)

1. start from any point on the circle and move along the circle(circumfrance) to come back to same point, along the path keep the sequence of xi's as they come in the path.
2. Now again do the same process in the opposite direction but this time keep track of sequence of yi's along the path.
now you name 2 sequances one of xi's and other yi's

now find the maximum matching sequence for (xi's ,yi's ) which will give you subset of maximum lines without overlap.

Also easily draw all the lines in a matrix marking each point with the line object and if there are more than one passing in the same matrix put in a structure where for each intersection is represented.

Another way is to convert each point as either a degrees or radian point in the circle. In this way we can say a line intersect if in between a line starts in A and ends in B there are another point that starts in between A & B but end outside A & B.

For example if Line (A, B) and Line (C,D) if in degrees do not intersect if you find them in the following orders ABCD, ACDB or CABD in that orders in radians or degrees otherwise the they intersect when they are like ACBD, CADB

Using recursion to find the largest subset

We can sort all endpoints by angle (y = sin(a), x = cos(a)).
Then we can build a graph where vertices are lines,edges are intersections. It is possible to do in O(n). So now we need to find the largest independent set. It is NP hard.
One of possible heuristics is to find the most low-degree vertex, add it to the set, delete it and its neighbours from the graph. Repeat until it is possible.

Dynamic Programming. Should be O(n^3) time and O(n^2) space.
State would be two dimensional DP(i,j) standing for maximum segments that can fit into [i,j].
State transition would be base on first segment of optimal solution in range [i,j].
DP(i,j) = argmax_k (1+DP(k_start+1,k_end-1)+DP(k_end+1,j)), seg k that fits in [i,j].
Mind some boundary cases, and hopefully this is clear enough for you guys.

public static class Point {
  public double x, y;

  public Point(double x, double y) {
    this.x = x;
    this.y = y;
  }
}

public static int MaxSetDP(int[] segs) {
  int n = segs.length;
  if (n == 0)
    return 0;

  int[][] dp = new int[n][n];
  for (int i = 0; i < n; i++) {
    for (int j = i; j >= 0; j--) {
      int max = 0;

// For segment [i,j] search through all segments that fits in [i,j]
// assuming it's the first segment for opitmum solution
// Find the segments with largest fit

      for (int k = j; k < i; k++) {
        if (segs[k] >= 0 && segs[k] <= i) {
          int cmax = 1;
          if (segs[k] - k > 2) {
            cmax += dp[k + 1][segs[k] - 1];
          }
          if (segs[k] < i) {
            cmax += dp[segs[k] + 1][i];
          }
          max = Math.max(max, cmax);
        }
      }
      dp[j][i] = max;
    }
  }
  return dp[0][n - 1];
}


public static class AngleCompare implements Comparator<Point> {

  @Override
  public int compare(Point o1, Point o2) {
    if (o1.x >= 0 && o2.x >= 0) {
      return o1.y < o2.y ? -1 : 1;
    } else if (o1.x < 0 && o2.x < 0) {
      return o2.y < o1.y ? -1 : 1;
    } else {
      return o1.x < o2.x ? 1 : -1;
    }
  }

}

public static int MaxSetPoints(Point[][] segments){

  Point[] array = new Point[segments.length * 2];
  for (int i = 0; i < segments.length; i++) {
    array[i * 2] = segments[i][0];
    array[i * 2 + 1] = segments[i][1];
  }
  HashMap<Point, Integer> order = new HashMap<>();

// Sort points by clock-wise order
// Comparison function not using any sin,cos function which is slow

  Arrays.sort(array, new AngleCompare());
  for (int i = 0; i < array.length; i++) {
    order.put(array[i], i);
  }

// Flatten into integer array, 
// Non zero elements indicates start point, value is the end point
// Negative value is an end point

  int[] segs = new int[segments.length * 2];
  for (Point[] si : segments) {
    segs[order.get(si[0])] = order.get(si[1]);
    segs[order.get(si[1])] = -1;
  }
  return MaxSetDP(segs);
}

Not sure if this works (especially since it's quite simple), so let me know if you can find a counter-example.
(1) For each segment, count how many times it intersects with the other segments - O(n^2)
(2) Sort the segments by their number of intersections - O(nlogn)
(3) Iterate through the segments and include each segment as long as it doesn't intersect any of the current ones - O(n)

So O(n^2) total.