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.

[WingedPanther]

I'm guessing height = weight. There is also some sort of unique identifier: name, for each actor.

I would have a class containing array/vector of name, age, height, and a member function that loops through the array once, using local variables name/age updating name/age only if the current height is in the range and the age is less than the currently found age.

What language was this for?

[janemayers]

I'm sorry, I missed the most important part...
The query should run in O(1) time worst-case.
And, yes... height = weight (:

[WingedPanther]

O(1) makes that a much nastier problem. I think I see how to get it in O(ln(x)). This may have been a problem where the problem is not possible, but the goal was to see how you approach it.

[John]

When you say the data structure has only one function, does that mean it can only have one function - to just search? Or the structures only purpose is to return the youngest actor + age?

If you can have a sorting function, you can sort the actors in a way such that their ages are ascending [the actor at the 0-th position is the youngest and the actor at the nth position is the oldest] In which case when you do a search(i, j) - if i < j the actor at the i-th position in the array will always be the youngest, if j < i the actor in the j-th position is the youngest. [No searching needed as you use the constant time reference of the array O(1)]. However, if you can't sort them prior to searching, I don't believe the problem is possible.

[WingedPanther]

The function could be called recursively. I'm thinking of a tree, with a select function that traces down the nodes recursively.