InMobi Interview Question
Country: India
Interview Type: In-Person
Correction : Time Complexity would be :
O(sizeof(e1)+sizeof(e2)...+sizeof(en))
Correct me if wrong
Two problems: 1) This algorithm isn't optimal; 2) This algorithm could have very high complexity if time is not discretized into a small number of chunks. I think it's better to make no such assumptions.
There's a linear-time (NlogN if you have to sort) time algorithm for solving this problem with just real-number timestamps.
can we think in terms of graphs.
s1{a,b,c} -- s2{c,d} -- s3{d,e,f} -- s4{x,z}
i.e. 4 nodes. each node has 'n links/pointers' where n = number of elelments in it.
s1 has 1 link to s2 via c (the other 2 links are set to null )
s2 has 1 link to s3 via d ( => s2 has 2 links where are non null but s3 has 1 link set and other two are null)
s4 has no outgoing links.( (all 2 links are set to null ))
steps:
1)create the graph.. here a graph with 4 nodes 1 for each set.
2)remove the node with highest links i.e. here s2
3)check if you have nodes with 0 links
4) if step3 has nodes with >0 links, repeat step 2,3 u get nodes with 0 links
I assume all the sets are sorted.
- Ranj February 19, 2012Find the maximum value out of all the sets i.e., compare the last value in each set & find the maximum value.
Create a bitset with a size that of this maximum value.
Walk thru the first set & for each value set the corresponding bit. i.e, if s1 = 6, then the 6th bit is set.
Pick the next set. Walk thru it. If you find any bit is already set, for any value of this set, then that set needs to be removed.
Follow the same for all the remaining sets.
Time Complexity : O(e1+e2+...+en). I am not sure about this time complexity calculation, please correct if I am wrong.