Logic teasers, Edition 2;

Reposted from :

http://ayende.com/blog/163394/new-interview-question?Key=ba723523-5252-4377-8c54-239026db23e5

Given a finite set of unique numbers, find all the runs in the set. Runs are 1 or more consecutive numbers.

That is, given

{1,59,12,43,4,58,5,13,46,3,6}, the output should be:

{1}, {3,4,5,6}, {12,13}, {43}, {46},{58,59}.

Note that the size of the set may be very large.

 

Let’s try and break this down; here’s my first shot at a dumb algorithm, to solve.

So you’re scanning through the set. You need to know if the number you’re currently on is consecutive from a previously occurring number.

Whenever you hit a number that is a consecutive from a previous, you create a new list (?) and add these two numbers to it, removing them from the list you’re scanning.

If you encounter a number which previously formed the start of a list, that now forms the start of a new list,

When you reach the end of the set, you stop counting.

It’s late, I’ll come back to this in an hour or two.