Just to demonstrate I have not an original thought in my head, I am plagiarising the topic of this article / code puzzle from a question on Stack Overflow. It's also inspired by Duncan's "Project Euler" series of blog posts.
But just to get your brains stretching (albeit: only slightly), perhaps you might want to answer the question on my terms (which opens it to a broader audience), rather than those specific to the question.
The question is a PHP-specific one, but I don't care about that: it's a good algorithmic question for any language, and isn't too hard.
This is the original question: "PHP array read out succession", however for the purposes of this exercise, I'm going to revise it slightly.
Problem
One has an array of numbers, eg:[100, 300, 100, 50, 50, 50, 50, 50, 500, 200, 100]
One also has a threshold number, for example
500.For a given array and a given threshold, return the subarray which contains the longest run of consecutive numbers which - in total - are equal-to or less than the threshold.
For example:
series = [100, 300, 100, 50, 50, 50, 50, 50, 500, 200, 100]
threshold = 500
subseries = getSubseries(series,threshold) // [100, 50, 50, 50, 50, 50]
In this example,
100,300,100 are less than or equal to 500, and has a length of three. 300,100,50,50 has a length of four, but 100,50,50,50,50,50 has a length of six, which is the longest sequence, so is the answer.Update:
People have asked how multiple same-length subseries should be handled. This was not a consideration in the original question, and it did not occur to me to ask. I think it makes sense that in the case of two equal-length series, then the one with the highest sum should be returned. That said, I'd not "penalise" any existing entries which did not consider this (my own code - as yet unpublished - certainly doesn't!).Rules:
- answer in any or as many languages as you like. If the language isn't one I'm au fait with (so one of CFML, PHP, JS or Ruby, really), you might need to explain it to me ;-)
- Answer via a gist (etc) or code on GitHub.
- No code submitted in comments to this article will be accepted, and I will actively pillory you for not following instructions if you do so.
- The code must work for any non-negative numeric array, with any numeric threshold. Demonstrate it for the example above.
- It's up to me who wins. I can't offer much by way of prize, although I'll name you, write an article about your answer, and buy you a drink next time I see you.
Things that will improve your chances of "winning":
- Use Clean Code principles.
- Use TDD (so submit your tests too).
- Answers that I find more technically interesting are more likely to win than answers that are pedestrian or obvious. Scalpels rather than sledgehammers.
Note: I will be participating as well. I have not started yet, nor really even thought about my approach. I will write up my answer though once I've done it.
Please do circulate this to your colleagues: the more answers we get, the more interesting it'll be.
Moderation queue
Just a note: if you've not commented on this blog before, or have commented and not posted a link in your comment before: you'll go into the Disqus moderation queue. Sorry 'bout that, but I get a bit of spam on this blog. I get an email when you post a comment, and I attempt to approve legit comments immediately but this w/end I'm abroad in Ireland so don't have internet access when I'm out and about. So it might take a few hours for me to get to it.Cheers!
--
Adam
