A job interview riddle I couldn't answer

[janemayers]

I guess it won't help me now, but I'll appreciate your thoughts anyway.

You are given an array with n actors, each has a weight and an age.

You should build a data structure that has only one function: for any two real numbers i,j you should be able to return the youngest actor in this range of heights (if exists).

You can take as much time as you want (finite...) to build the data structure and you may assume that no changes will be made after initialization.

Any ideas?

Thanks.

[ProgramThis]

That's a little confusing:

You should build a data structure that has only one function

huh? Did they mean "build a function to operate over the data structure that does the following:?"

Other than the wierd way the question is worded, you can simple search through the array (if it's sorted it's easier), and either create a new data structure to hold all of the actors between i and j heights, or just a temp variable to hold the youngest thus far of the actors between those heights:

actor temp = arr[0];
for( x = 1 ; x < arr.length ; x++)
if(arr[x].getHeight() <= j && arr[x].getHeight() >= i)
if(arr[x].getAge() < temp.getAge())
temp = arr[x];

I would assume that code there would find the youngest actor within a given height range.

[janemayers]

Sorry for the bad phrasing (it's just my English), but you got it wrong.
Obviously I forgot to write the most important part:
The query should take O(1) time worst-case.

[saiduluakshay]

Build the priority queue (heap ) data structure for between i, j ages.
then your algorithm will find the youngest actor in O(1) .

[kumaresh_ana]

Bucket sort