Great programming riddle!

16 posts (showing 1-16)
ozdy

Market Level 6Community Level 13
1482 posts

There are N numbers, unsorted (potentially floating point). Find the biggest difference between two adjacent numbers if they are sorted. Your algorithm should run in linear time.

(Obviously, sorting them won't work as it's N*log(N) ) 

First person to solve it gets 5 first impressions from me :)

posted 2015-03-12T14:47:59-07:00 | edited 2015-03-12T14:48:43-07:00
LongAnimals

Market Level 9Community Level 14
983 posts

piss off.

posted 2015-03-12T14:50:56-07:00
bluebox

Market Level 6Community Level 3
334 posts

why you need algorithm for that? Gap will never be bigger than N/2 or N/2-1 - too lazy to think atm ;)

BTW. if you need to predict gaps - to make jump prediction - simply use bell curve.

posted 2015-03-12T14:53:30-07:00 | edited 2015-03-12T14:55:23-07:00
ozdy

Market Level 6Community Level 13
1482 posts

bluebox said:

why you need algorithm for that? Gap will never be bigger than N/2 or N/2-1 - too lazy to think atm ;)

BTW. if you need to predict gaps - to make jump prediction - simply use bell curve.

If you have 1,5,1000, gap is definitely bigger than 3/2 .

posted 2015-03-12T14:58:36-07:00 | edited 2015-03-12T15:00:25-07:00
bluebox

Market Level 6Community Level 3
334 posts

Yea I've assumed you have same gap after sorting.

Nsum=1006 where min=1 and max = 1000, for N numbers probabilistic answer is 997 (6/2). Now you have to run one loop to find biggest gap or confirm 997 is true. I have plenty of job. Just run a contradiction loop wich will find you biggest gap.

posted 2015-03-12T15:12:58-07:00 | edited 2015-03-12T15:15:24-07:00
ozdy

Market Level 6Community Level 13
1482 posts

bluebox said:

Yea I've assumed you have same gap after sorting.

Nsum=1006 where min=1 and max = 1000, for N numbers probabilistic answer is 997 (6/2). Now you have to run one loop to find biggest gap or confirm 997 is true. I have plenty of job. Just run a contradiction loop wich will find you biggest gap.

No way you can confirm a given gap in linear time, other than solving the problem and finding the real one :)

The solution algorithm has no probability.

posted 2015-03-12T15:31:40-07:00 | edited 2015-03-12T15:32:46-07:00
bluebox

Market Level 6Community Level 3
334 posts

Every algoritm have some probable result if you are using statistics methods.
If you run infinte number of examples for three numbers where biggest possible gap is 997, most probable biggest gap is around 747.

Method I've mentioned above will find real gap for you, because will solve the problem. But I'm really curious about someones else solution.

posted 2015-03-12T15:57:37-07:00 | edited 2015-03-12T15:59:37-07:00
ozdy

Market Level 6Community Level 13
1482 posts

bluebox said:

Every algoritm have some probable result if you are using statistics methods.
If you run infinte number of examples for three numbers where biggest possible gap is 997, most probable biggest gap is around 747.

Method I've mentioned above will find real gap for you, because will solve the problem. But I'm really curious about someones else solution.

Your method does not work in linear time. In fact sorting the numbers would be faster than your algorithm.

posted 2015-03-12T16:03:43-07:00
bluebox

Market Level 6Community Level 3
334 posts

One loop cannot be slower than sorting. Beside sorting wont give you the answer, you still need to find the gap with a loop.

posted 2015-03-12T16:15:17-07:00
ozdy

Market Level 6Community Level 13
1482 posts

bluebox said:

One loop cannot be slower than sorting. Beside sorting wont give you the answer, you still need to find the gap with a loop.

So how can you check a given gap with just one loop in an unsorted array of numbers in linear time? I don't think that's possible.

You need to check for each number if a number + gap exists and there is no number inbetween and you can't do that in constant time.

Also, sorting + 1 loop is still O(n*log(n)), you can do a fixed amount of loops as long as they are not dependent on N and it will still be linear time.

posted 2015-03-12T16:44:23-07:00 | edited 2015-03-12T17:14:11-07:00
bluebox

Market Level 6Community Level 3
334 posts

yea I assumed that you know min, max numbers and length of the array. My assumption - maybe I'm wrong - was that I'm able to figure out if given number can be edge of the biggest gap.

For instance, if you have numbers 1,4,67,245,700,1000 your biggest possible gap is in range from 199-994

let say you have array like this 1,67,4,700,245,1000

lets make short loop:
- A(1) valid, B(67)valid; this two numbers doesnt make min biggest gap, which means A=67 and you need to find digit greater than 266
-A(67) valid, 4 - invalid
-A(67) valid, B(700) valid
-A(67) valid, B(700) valid; at this point 245 is invalidating A(67), but still B is valid, so 245 is now new A
-A(245)valid, B(700) valid; 1000 does not invelidate any of this number. Invalidate itself.

gap found: A(245), B(700);

For that simple array you dont need to sort, or more than one loop. There is for sure bilion exceptions which makes algorithm more comples, but I'm really busy, so I hope this might help you at least a bit.

posted 2015-03-12T17:19:41-07:00 | edited 2015-03-12T17:21:18-07:00
bluebox

Market Level 6Community Level 3
334 posts

forgot to add - if gap between A>B is bigger than B and Nmax, you can pass all numbers >than B. In this point you are just looking for a number x>A && x<B. as lowest biggest gap can be 199, you are lookng for numbers that are greater than A+199 or lower than B-199. I allows you to skip tons of numbers in large computations.

posted 2015-03-12T17:46:14-07:00
ozdy

Market Level 6Community Level 13
1482 posts

bluebox said:

forgot to add - if gap between A>B is bigger than B and Nmax, you can pass all numbers >than B. In this point you are just looking for a number x>A && x<B. as lowest biggest gap can be 199, you are lookng for numbers that are greater than A+199 or lower than B-199. I allows you to skip tons of numbers in large computations.

I understand your solution, but unfortunately it doesn't work in all cases, for example consider you have 1000 numbers, minimum is 1, biggest is 1000000, your first 8 numbers are:

1000K,1,500K,250K,750K, ... you can't exclude anything.

posted 2015-03-12T18:33:50-07:00
Bryce

Market Level 5Community Level 5
375 posts

LongAnimals said:

piss off.

I don't know if I can top that answer but I'll certainly try!

Below is some Unity c# code... Although I must admit that I cheated... I didn't really have the patience to do it without google -- so I don't deserve your 5 FIs :P.

Either way I had some fun thinking about the problem -- thanks for that :).

[c#]
using UnityEngine;

public class NumberGap : MonoBehaviour
{
    public float[] numbers;

    void Start()
    {
        Debug.Log(maximumGap(numbers));
    }

    //simple class to represent a gap betweeen numbers
    private class Gap
    {
        //our low and high numbers
        private float? _low, _high = null;

        //distance between gap
        public float distance
        {
            get 
            {
                if (_low.HasValue == false || _high.HasValue == false)
                {
                    return 0;
                }
                return high - low; 
            }
        }

        //lowest number in gap
        public float low
        {
            get
            {
                if (_low.HasValue == false)
                    Debug.LogError("Gap has no value assigned!");

                return _low.Value;
            }
        }

        //highest number in gap
        public float high
        {
            get
            {
                if (_high.HasValue == false)
                    Debug.LogError("Gap has no value assigned!");
                
                return _high.Value;
            }
        }

        //does the gap contain any values at all?
        public bool hasValue
        {
            get
            {
                return _low.HasValue || _high.HasValue;
            }
        }

        //inserts a number, and expands gap as necessary
        //on first insertion low = high = n
        //after that low = lowest number inserted and high = highest
        public void InsertNumber(float n)
        {
            if (_low.HasValue == false)
            {
                _low = n;
            }

            else
            {
                _low = Mathf.Min(_low.Value, n);
            }

            if (_high.HasValue == false)
            {
                _high = n;
            }
            
            else
            {
                _high = Mathf.Max(_high.Value, n);
            }
        }
    }

    //find the maximum gap between an unsorted array of floating point numbers
    //returns the biggest diference between two numbers if they were sorted
    public float maximumGap(float[] numbers)
    {
        float maximumGap = 0; //this will be the value we want

        if (numbers.Length < 2) return maximumGap; //don't need to do anything on 1 or fewer numbers...


        //find the gap between highest number and lowest number
        Gap gapMinMax = new Gap();

        foreach (float num in numbers)
        {
            gapMinMax.InsertNumber(num);
        }

        if (gapMinMax.distance == 0) return maximumGap; //don't need to do anything if theres no gap at all

        //construct an aray of empty "gap buckets" the length of our numbers minus one
        Gap[] gapBuckets = new Gap[numbers.Length-1];

        for (int i = 0; i < gapBuckets.Length; i++)
        {
            gapBuckets[i] = new Gap();
        }

        float gapBucketInterval = gapMinMax.distance / gapBuckets.Length; //used to put the numbers into their corresponding buckets

        //insert numbers into the appropriate buckets
        for (int i = 0; i < numbers.Length; i++)
        {
            int index = Mathf.FloorToInt((numbers[i]-gapMinMax.low) / gapBucketInterval);
            index = Mathf.Min(index, gapBuckets.Length-1);
            gapBuckets[index].InsertNumber(numbers[i]);
        }


        //iterate over buckets and get maximum gap
        float lastValue = 0;
        bool first = false;
        for (int i = 0; i < gapBuckets.Length; i++)
        {
            if (gapBuckets[i].hasValue)
            {
                if (first)
                {
                    maximumGap = Mathf.Max(gapBuckets[i].low - lastValue, maximumGap); //check last gap high value with current low
                }

                first = true;
                maximumGap = Mathf.Max(gapBuckets[i].distance, maximumGap); //check current gap distance
                lastValue = gapBuckets[i].high;
            }
        }

        return maximumGap;
    }
}
[/c#]

 

posted 2015-03-12T20:57:29-07:00
ozdy

Market Level 6Community Level 13
1482 posts

Nice, Bryce, that's it. I must admit I didn't solve it and neither did the guy that told me the problem or anyone else I've asked it. Thinking about such problems can be a lot of fun :)

For anyone wondering, here is the approach:

1.) Find minimum and maximum value of sequence (one N for loop)
2.) Create an array of N elements - each represents a gap of (max-min)/N from minimum element. Due to math properties, the maximum difference should cross such a boundary. So all you have to do now is iterate over all elements and fit each inside a gap (via division) and store only lowest and highest number for each gap. (one N for loop).
3.) Go through the gaps and see which boundary cross is highest (one N for loop)

posted 2015-03-12T21:12:28-07:00 | edited 2015-03-12T21:13:19-07:00
bluebox

Market Level 6Community Level 3
334 posts

thanks for the answer. I thought you need some quick answer for your script, so I came up with first thought ;)

posted 2015-03-13T00:35:26-07:00