Wow moment 2 !
Here is the thought process --
Use an Auxilary array Aux[size], of same type and size. As and when a Set(index, value ) operation happens, enter the value into A[index]=value; Put the index into Aux[] array, and have a counter for howmany such entries are entered, unsigned valid_count. Now whenever, we see a get count like get(index), we check/search if this index has value or not. This search happens in Aux[] array with the hope we find a value from the current index range 0<= index < valid_count. If we find the index there, we know a valid value will be found and returned. BUT THE PROBLEM IS get(index) is no longer O(1).
This is where we need to introduce another Auxalary array, say Aux2[], the first one is now renamed to Aux1[], A is our original array.
// main.cpp
// ArrayValue
//
// Created by Prokash Sinha on 5/6/21.
//
#include <iostream>
class MyArray{
public:
MyArray(size_t size) : myarra_(nullptr), aux1_arr_(nullptr),
aux2_arr_(nullptr), valid_count_(0), arr_size_(size)
{
if ( arr_size_ > 0 ) {
myarra_ = new int[arr_size_];
aux1_arr_ = new size_t[arr_size_];
aux2_arr_ = new size_t[arr_size_];
}
}
private:
int* myarra_;
size_t* aux1_arr_;
size_t* aux2_arr_;
int valid_count_;
size_t arr_size_;
public:
int get(size_t index){
int value = -1; // some value outside the domain of valid values
if ( index >= 0 && index < arr_size_ && aux2_arr_[index] >=0
&& aux2_arr_[index] < valid_count_){
value = myarra_[ aux1_arr_[aux2_arr_[index]] ];
}
return value;
};
void set(size_t index, int value){
if (index >= 0 && index < arr_size_){
myarra_[index] = value;
aux1_arr_[valid_count_] = index; // keep the current index
of myarray
aux2_arr_[index] = valid_count_; // keep the index of aux_arr_
++valid_count_;
}
}
};
int main(int argc, const char * argv[]) {
// insert code here...
int val;
MyArray myarr(10);
myarr.set(9, 99);
val = myarr.get(9);
myarr.set( 2, 22);
val = myarr.get(2);
myarr.set( 3, 45);
val = myarr.get(3);
// -- error cases
val = myarr.get(5); // shoule be -1
val = myarr.get(-1);
val = myarr.get(10);
std::cout << "Hello, World!\n";
return 0;
}
Prokash Sinha
Post a Comment
Reader Comments