They probably didn't answer because if you need clarification on the question, you have no hope of producing the answer. And incidentally it IS a programming challenge. (Which is why the econ prof had no clue.)

You have a collection of N intervals. And a collection of M points (which they call queries). For a given interval and point, that point can be in the interval or not. For each point you are supposed to find out how many intervals it is inside of. And you're supposed to make the code fairly efficient.

From the way you've written it, the intervals look like open intervals. So x1[i] is not in the i'th interval. That is a minor but significant detail, and I expect their test data to check it.

The naive solution is to write a function that takes an interval and a point, and says whether that point is in that interval. Then you just loop over all points and intervals. This works, but the number of times you run that comparison is N * M. Which, if N and M are large, is going to be painfully slow. In fact there is a notation to discuss how slow, and that notation would say O(N * M). They don't want any variant on this solution.

The solution they are probably looking for is O((N + M) * log(N)). One solution is to try to first find and put into sorted form all of the intervals where the answer is going to be constant across the interval, and then do a binary search for each point to find what interval it falls into (and therefore what the answer is for that point).

My guess as to their thinking is that anyone who can't figure out something like this won't have any clue when they cause scalability problems. This matters for larger sites.

If you don't understand any of what I just said, that's a hole in your background. To fix it go off and learn about little-o, big-O, and some basic algorithms. A short list of algorithms to learn could include quicksort, merge sort, hashing, binary search and how a BTree works. That combination will solve most problems pretty easily.

From the explanation you just gave I sovled it in 7 minutes but i guess thats no challenge since you did all the thinking and I just had to code it. But I see what you mean; i feel like I should have known that and will definitely go look into the things you suggested.

--Thanks

use an interval tree

I took each x axis line segment x(1) -> x(6) for example and hashed it at 1,2,3,4,5,6 and did that for everyone then it would simply be a question of iterating each M point and looking at the hash table

Probably a stupid way to do it but it worked.

I think the issue was that I did not know points == queries

Hashing is indeed the wrong way to go.

Yea, i just wanted to solve it quick so I didn't feel like such a dumb ass. I did it again using your solution and now i see what you mean about scalability because your way is much much faster and more efficient. I had to run my solution on my db server using memcache because it was taking too long and too much memory but yours ran on my laptop.