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.

Time Complexity : O(e1+e2+...+en). I am not sure about this time complexity calculation, please correct if I am wrong.

- Ranj February 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Correction : Time Complexity would be :

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

Correct me if wrong

- Ranj February 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- eugene.yarovoi February 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Thanks eugene.

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

- Ranj February 20, 2012 | Flag
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

- hoper April 18, 2014 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More