Create a customized data structure which evaluates functions in O(1)

Create a customized data structure such that it has functions :-
GetLastElement();
RemoveLastElement();
AddElement()
GetMin()

All the functions should be of O(1)

Question Source : amazon interview questions

Approach :
1) create a custom stack of type structure with two elements, (element, min_till_now)
2) implement the functions on this custom data type

// program to demonstrate customized data structure // which supports functions in O(1) #include <iostream> #include <vector> using namespace std; const int MAXX = 1000;   // class stack class stack {     int minn;     int size;   public:     stack()     {         minn = 99999;         size = -1;     }     vector<pair<int, int> > arr;     int GetLastElement();     int RemoveLastElement();     int AddElement(int element);     int GetMin(); };   // utility function for adding a new element int stack::AddElement(int element) {     if (size > MAXX) {         cout << "stack overflow, max size reached!\n";         return 0;     }     if (element < minn)         minn = element;     arr.push_back(make_pair(element, minn));     size++;     return 1; }   // utility function for returning last element of stack int stack::GetLastElement() {     if (size == -1) {         cout << "No elements in stack\n";         return 0;     }     return arr[size].first; }   // utility function for removing last element successfully; int stack::RemoveLastElement() {     if (size == -1) {         cout << "stack empty!!!\n";         return 0;     }       // updating minimum element     if (size > 0 && arr[size - 1].second > arr[size].second) {         minn = arr[size - 1].second;     }     arr.pop_back();     size -= 1;     return 1; }   // utility function for returning min element till now; int stack::GetMin() {     if (size == -1) {         cout << "stack empty!!\n";         return 0;     }     return arr[size].second; }   // Driver code int main() {     stack s;     int success = s.AddElement(5);     if (success == 1)         cout << "5 inserted successfully\n";       success = s.AddElement(7);     if (success == 1)         cout << "7 inserted successfully\n";       success = s.AddElement(3);     if (success == 1)         cout << "3 inserted successfully\n";     int min1 = s.GetMin();     cout << "min element  :: " << min1 << endl;       success = s.RemoveLastElement();     if (success == 1)         cout << "removed successfully\n";       success = s.AddElement(2);     if (success == 1)         cout << "2 inserted successfully\n";       success = s.AddElement(9);     if (success == 1)         cout << "9 inserted successfully\n";     int last = s.GetLastElement();     cout << "Last element :: " << last << endl;       success = s.AddElement(0);     if (success == 1)         cout << "0 inserted successfully\n";     min1 = s.GetMin();     cout << "min element  :: " << min1 << endl;       success = s.RemoveLastElement();     if (success == 1)         cout << "removed successfully\n";       success = s.AddElement(11);     if (success == 1)         cout << "11 inserted successfully\n";     min1 = s.GetMin();     cout << "min element  :: " << min1 << endl;       return 0; }

Output:

5 inserted successfully
7 inserted successfully
3 inserted successfully
min element  :: 3
removed successfully
2 inserted successfully
9 inserted successfully
Last element :: 9
0 inserted successfully
min element  :: 0
removed successfully
11 inserted successfully
min element  :: 2

Time complexity : Each function runs in O(1)