A road named NoNameUno

How do we use array types, in C / C++ algorithms? 

We either allocate on stack ( when using local array to a function ) or using heap memory to use until we free the array objects. We use one of many ways to allocate such array objects, initialize before using it, they either implicitly or explicitly destroy it...

Now there is a situation where you can allocate a really large array object, but you want to avoid initializing it , because it is slow for certain applications. The only methods we need is to have Get, and Set methods to set or get information form a particular index, just like A[i], where i is the index. NOW RANDOM ACCESS PATTERN WILL BE THROWN AT THE IMPLEMENTATION, Our job is to make sure the implementation we design work without any fault.  How do we do that ??

You can use extra or auxilary memory as you want, but in this case performance of CPU is more important.

Try to think about, and come up with a solution... You will certainly miss the WOW moment, if you jump into the code, I will present here.  I was half way, or perhaps 2/3rd of the way. No paper pencil , just talk and think thru, including hold the thinking process -- what if I do this, or that etc. Extra time usually given when two players are hoping to win, an even game if you will. So I was given couple hours to take a shot at it, encouraged to take the path I was thinking.... Do please don't miss the WOW moment.

Probelem statement:

Elements in an array can be retrieved/set in constant time O(1). For

the sake of this problem, assume when you new an array, the allocated

memory will just have garbage — data from their previous life. So

typically you need to traverse the array, and initialize the elements

to some well-known invalid value. Say if we know the valid data is

positive int, then you’d initialize the elements to something like -1

to indicate it’s an invalid value. This way when you get a -1, you

know it’s a garbage value.

For this problem, write a class called MyArray that has three functions:

constructor — MyArray(size_t size)

getter — int get(size_t index)

setter — void set(size_t index, int value)

The requirements are

* No initialization of the array before using it, assume it is very very expensive operation

• The implementation can only use native data types like int and

native array (i.e., cannot use things like HashTable, Set, LinkedList,

etc).

• The getter function returns -1 when the value is a garbage (i.e., an

index that has never been set by client). It has to be 100% correct in

the sense that there is no circumstance where the getter would return

a value X, where X is actually garbage.

• All three functions have to be strictly O(1) — not amortized O(1)