Hi all! This is a problem asked on facebook interview....
There are many intervals each defined by pair containing a starting point and a ending point (si, ei). Two intervals i1 and i2 are called nested if i2 lies completely inside of i1. Example:- (2,6) and (3,4) are nested, since (3,4) is a part of (2,6). Similarly k intervals i1, i2, i3....ik are called nested if, i2 lies inside i1, i3 lies inside i2, ...and so on. Determine size of largest set of intervals from the given intervals, such that all the intervals in that set could produce a nesting.
I thought it in following way:- Let us take an e.g.- (0,7) (0,5) (1,21) (1,9) (2,8) (2,4) (3,20) (4,16) (5,15) (6,21) Sort it in the way such that a[i-1]<=a[i] && b[i-1]>=b[i] Than starting from first interval we start a linked list.. if the next interval comes inside a interval we move down the node and traverse the graph created down the node(other than main list)..we store the pointer of the maximum level node in this graph at which the new interval can fit.. and traverse further in linked list to see under whom the current interval comes.. at last we have a pointer to a node with whom we have to attach the current interval.. and compare the level of this node with the maximum level we already have..... The final value of maximum level is size of maximal nested intervals set..
complexity of above solution is likely to be:- O(n(k+l) + nlogn)
I guess it is difficult to get it this way, but I have no other option... if anyone got other algorithm.. please explain it...thanks!!
has anyone got any idea.... my algorithm takes much time to implement(many data structures needed!!!)... I want to implement it in lesser time..please post if any one got the problem....
It's evil to post problems from interviews, because then they cannot use it anymore. BTW: This problem has pretty straightforward solution in O(N^2) and a bit more tricky in O(N log N).
This question is well-known, so it isn't really bad in this case. I'm surprised that Facebook asks on their interviews things having almost nothing common with real stuff they do.
I know, that many interview questions aren't related to real work, but this one is much more theoretical and impractical then usual questions.
As far as I know, you're interning at Google now. Do you want to say that Google asks more practical questions on the interviews?
I want to say nothing about Google interview questions, because it is confidential information =)
But according to public information including other spoiled tasks from different companies interviews I can say that this task looks unusual.
You can build a directed graph G = <V, E>, where V = {1, 2, ... n}, and you will put an edge from vertex u to vertex v if interval number u lies inside interval number v. Note that G is a DAG, so you can make a topological sort and the problem is reduced to find the largest path in G. This can be done easily using dynamic programming. The complexity is O(n ^ 2).
NOTE: If there are repeated intervals, you should assign the same node to equals intervals and in the dynamic programming this node shall sum to the answer the amount of nodes that it represent.
it looks correct!!..most of the time (O(n^2)) is spent in insertion of a new interval with all of its edges to its parent sets in which it is nested...using Kahn's algo(or DFS), we can do topological sort in O(|V|+|E|) and same time for finding longest path...
do a sweep line, you can do this algorithm in O(n log n) to find which interval lies inside of another
I think it can be solved for O(NLog(N)). sort all intervals (a[i] < a[j] || a[i] == a[j] && b[i] > b[j]). Add into set S interval (-inf, inf) and set it's Depth to zero. Now iterate over all intervals in sorted order. First we should find in the set S interval j with maximum Depth such that b[j] >= b[i]. It can be done using Interval Tree data structure for O(log(N)). Update Depth of Interval i and put into S interval (a[i], b[i]). it can written in pseudo code, assuming c is an interval tree:
c[b[i]] = max(c[b[i]], Depth[i]);can u explain it a bit more... what is this c actually and how are you inserting in the tree inside the set S...what are you conveying through c[b[i]]??
Ok if you don't understand forget about S. Interval tree — it can be Segment tree, or Cartesian Tree. Let c is an array and one of this data structures constructed over it. So you can change c[i] and update the tree in O(Log(N)) time (lets call this query Change(i, newValue)). Also you can answer "what is the maximum value among c[i], where i >= x" in O(Log(N)) time (lets call this query FindMax(x)).
"First we should find in the set S interval j with maximum Depth such that b[j] >= b[i]. ... Update Depth of Interval i"
equal to
Depth[i] = FindMax(b[i]) + 1
" put into S interval (a[i], b[i])"
equal to
Change(b[i], Depth[i]);
Sort pairs ai < aj || ai == aj && bi > bj. Remove ai. Now find Longest Non Increasing Subsequence in O(nlogn) using binary search instead of Interval tree.
Similar algo: Longest Increasing Subsequence
ok.. i got it .. i thought it other way early(previous comment..sorry for that!!)... actually it need not be continuous..got it...but is there any proof of correctness of this algorithm anywhere??? If yes, please notify.. otherwise its ok..thanks ValenKof!!
Note: my algorithm after sorting do not use a[i]. Actually my algorithm finds Longest Non Increasing Subsequence of all b[i].