## techInterview Discussion |
||

A part of techInterview.org: answers to technical interview questions.
Your host: Michael Pryor |
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.
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
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
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 |

Powered by FogBugz