techInterview Discussion

A part of techInterview.org: answers to technical interview questions.

Your host: Michael Pryor

amazon question

If you have a file with each line having 3 values and it represents a range and corresponding value belonging to that range. ie, minimum, maximum, value. Like the following:
20,30,A
41,50,D
31,40,B
51,60,C

Write an algo so that if 43 is given as a key, it must return D as the value. There might be many searches, not just one.



int getValue(int key);

there is obvious O(N) method we are looking logn or O(1)method.
ray3044 Send private email
Sunday, July 20, 2008
 
 
What if the ranges overlap?
What are the maximum values of the array?

O(log n) per search is fairly easy with a O(n log n) initial setup. Use sorting and binary search.

A O(1) look-up is possible with a O(n) initial effort.  Use a big-ass look-up table.

O(k), k is the number of bits in the representation of one array bound, look-up is possible with a O(k log k) initial setup.  Use a modified trie.

*Shrug*  More realistic for an interview than the Microsoft one below?

Sunday, July 20, 2008
 
 
O(log n) per search is fairly easy with a O(n log n) initial setup. Use sorting and binary search.
?

please elaborate, say, one file sorted by first index, and another one sorted by second index, then?

how to identify the intersect of two set after two binary (each get one set which satisfied the 1st/2nd index requirement) search efficiently?

thanks
ray3044 Send private email
Wednesday, July 23, 2008
 
 
I assumed that the intervals were distinct.  Sort the list by initial index.  Do a binary search for your search value or its predecessor in the list.  This interval is the only one it could fall in.

Obviously, this solution doesn't work if the intervals are not distinct.  Which isn't an insurmountable problem.

Thursday, July 24, 2008
 
 
how about there is intersect of the intervals? thanks
ray3044 Send private email
Thursday, July 24, 2008
 
 
If there are intersections, we can keep O(log n) lookup by paying a higher setup cost.

We agian sort the list by the initial interval value.  O(n log n)

For simplicity when I say pred, I mean the element being operated on or its predecessor.

For each item in the list, we get the pred of that item's end interval value in the sorted intial list.  This gives us all the values for the interval (potential all n values may be in this list).

From this we may construct a non-overlapping interval sorted by the inital postion that returns an array of values in O(log n) time.  The construction takes O(n ^ 2 * log n).

Friday, July 25, 2008
 
 
Isn't this direct application of interval trees??
K. Ashwin Kumar
Monday, July 28, 2008
 
 
It's just a basic sort + binary search problem.

Thursday, July 31, 2008
 
 

This topic is archived. No further replies will be accepted.

Other recent topics Other recent topics
 
Powered by FogBugz