Tell me more ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.
up vote 0 down vote favorite

I was posed this question at an interview and never really came up with a great solution. Does anyone have an "optimum" solution? Where the target is efficiency and being able to deal with large input.

Material Provided:

I am given a long list of shops and their opening/closing times (say 1000).

The Problem:

For a given time of day, return how many of the shops are open

Example Data:

Sainsburys 10:00 23:00
Asda 02:00 18:00
Walmart 17:00 22:00

Example In/Out

Input | Output
12:00 | 2
22:00 | 1 (walmart shut @ 22:00)
17:30 | 3

The two parts of the problem are how to store the data and how to efficiently get the answer, I guess how you're reading the input etc doesn't really matter.

Thanks for your time and insight!

share|improve this question
Thus you look for a solution with the most efficient lookup time using given data? Efficiency of insertion/deletion into the data structure does not matter? Are opening/closing times discrete numbers? – Howard Nov 19 '12 at 15:30
@Howard I guess it's a combination of insert and efficiency of lookup. Opening and closing times are integers so yes they're discrete – Pez Cuckow Nov 19 '12 at 15:39
Have you watched these lectures? Lecture 3 has a bit about range trees which might be a good way to store and search through this kind of data? – Gareth Nov 19 '12 at 15:47
1  
Welcome to CodeGolf.SE. This site is a place for posing and playing certain programming games, not a general problem solving facility. This particular problem does not seem to meet our current requirement that there be a "objective winning criteria" for every game posted here. I've started a meta discussion about this, and would be interested in how you think things like this could fit into our site, but I am going to close it for the time being. – dmckee♦ Nov 19 '12 at 17:25
1  
Shouldn't we migrate it instead of closing it? It might be an adequate question on stackoverflow. – vsz Nov 20 '12 at 16:21

closed as not constructive by dmckee♦ Nov 19 '12 at 17:26

As it currently stands, this question is not a good fit for our Q&A format. We expect answers to be supported by facts, references, or specific expertise, but this question will likely solicit debate, arguments, polling, or extended discussion. If you feel that this question can be improved and possibly reopened, see the FAQ for guidance.

Browse other questions tagged or ask your own question.