Now let's say you are needed to create a collection class of yours which has the following access:

SetValueAll(value)

SetValue(index, value)

GetValue(index), return value

where 'value' can be any arbitrary type. And the internal data representation is up to you. But you are limited to:

(Challenge 1): The constraint is that all three operations have to be strictly O(1) complexity.

(Challenge 2): After challenge 1, now you are required to also have its memory footprint no more than O(n).

 

so... let's get going!!!

 

edit: O(n) seems impossible. The least should be O(n+ε).

---

Any technology without common sense is useless.

dstl1128:

Now let's say you are needed to create a collection class of yours which has the following access:

SetValueAll(value)

SetValue(index, value)

GetValue(index), return value

where 'value' can be any arbitrary type. And the internal data representation is up to you. But you are limited to:

(Challenge 1): The constraint is that all three operations have to be strictly O(1) complexity.

(Challenge 2): After challenge 1, now you are required to also have its memory footprint no more than O(n).

 

so... let's get going!!!

 

Perhaps make it a better challenge: No Pointer 

---

- Self control is the appetence of the most strongest man -

Well, it doesn't need pointers to achieve. It is attainable in Java, C#, VBnet as well.

---

Any technology without common sense is useless.

I'll just slowly show my progress/approach... comments are welcomed.

Here's the 1st slow and normal version, and not necessarily correct in all cases:
(bounds checking has been ignored, ignore code tag - useless)

class MyArray1
{
    // ...

    public void SetValueAll(T newval)
    {
        for (int i = 0; i < _data.length; ++i)
            _data[ i ] = newv;
    }

    public void SetValue(int ndx, T newval) 
    { 
        _data[ndx] = newval; 
    }

    public T GetValue(int ndx) 
    { 
        return _data[ndx]; 
    }

    // ...

    private T[ ] _data;
};

---

Any technology without common sense is useless.

Clearly the SetValueAll() is still O(n) operation. But one thing we have improved is that if setting the value of T are expensive, i.e. SetValueAll() doesn't need to make an expensive assignment operation for each item, instead just assign array of bools. Just some simple attempt, though still far from what I need, it is getting close.

class MyArray2
{
    // ...

    public void SetValueAll(T newval)
    {
        _value = newval;
        for (int i = 0; i < _isset.length; ++i)
            _isset[ i ] = false;
    }

    public void SetValue(int ndx, T newval)
    {
        _data[ndx] = newval;
        _isset[ndx] = true;
    }

    public T GetValue(int ndx)
    {
        if (_isset[ndx])
            return _data[ndx];
        else
            return _value;
    }

    // ...

    private T[ ] _data;

    private T _value;
    private bool[ ] _isset;
};

---

Any technology without common sense is useless.

Hi Derek,

It's no fun you posting the question and you giving the answer. I actually have a version in my mind just too lazy to put it in letters. Give me sometime on Monday, I will post mine here.

---

- Self control is the appetence of the most strongest man -

No problem. That is not the final I think, since it is still O(n). Actually I'm not sure about the final answer too.

I'm still working on it. But I think I got one very close right now. Ok, I'll just stop here for now. :P

---

Any technology without common sense is useless.

Here's mine. Two assumptions:
1) Fixed length array.
2) Object must override the Equals method

    class MyFireArray<T>

    {

        private T[] _data;

        private bool _isAllSame;

 

        // Array, assuming fixed size

        public MyFireArray( int size )

        {

           _data = new T[ size ];

        }

 

        public void SetValueAll( T newval )

        {

            _data[0] = newval;

            _isAllSame = true;

           

        }

 

        // Slightly tricky...

        public void SetValue( int index, T newval )

        {

            if( _isAllSame && _data[ 0 ].Equals( newval ) )

            {

                // do nothing

            }

            else

            {

                _data[ index ] = newval;

                _isAllSame = false;

            }

        }

 

        // Assuming null is one of the acceptable value

        public T GetValue( int index )

        {

            if( _isAllSame )

            {

                return _data[ 0 ];

            }

            else

            {

                return _data[ index ];

            }

        }       

    }

 

---

- Self control is the appetence of the most strongest man -

Hmm... can you do this with the correct result:

myarr.SetValue(10, 5);
myarr.SetValueAll(7);
myarr.SetValue(1,2);

What is the value of myarr.GetValue(10); ?
For a normal container/collection, it should return 7.

---

Any technology without common sense is useless.

oh ya, now it seems like i am cheating... Haha

Let see how to progress from there again..

---

- Self control is the appetence of the most strongest man -

Early morning rituals...

 1 class MyArray3
 2 {
 3     // ...
 4 
 5     public void SetValueAll(T newval)
 6     {
 7         _laststamp = _timer;
 8         _value = newval;
 9         _timer++;
10     }
11 
12     public void SetValue(int ndx, T newval)
13     {
14         _cell[ndx].data = newval;
15         _cell[ndx].timestamp = _timer;
16     }
17 
18     public T GetValue(int ndx)
19     {
20         if (_cell[ndx].timestamp > _laststamp)
21             return _cell[ndx].data;
22         else
23             return _value;
24     }
25 
26     // ...
27 
28     struct node
29     {
30         T data;
31         int timestamp;
32         node() { timestamp = 0; }
33     };
34 
35     private node[ ] _cell;
36 
37     private int _timer = 1;
38 
39     private T _value;
40     private int _laststamp = 0;
41 };
42 

The time stamps will wrap around if the MyArray3 is used for a long time. Still not good for usage. Back to drawing board...

---

Any technology without common sense is useless.