## InMobi Interview Question

Country: India
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
0
of 0 vote

I assume all the sets are sorted.

Find 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.

Comment hidden because of low score. Click to expand.
0

Correction : Time Complexity would be :

O(sizeof(e1)+sizeof(e2)...+sizeof(en))

Correct me if wrong

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

Thanks eugene.

Do you have any optimal solution for this? Kindly let me know.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.