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 :
- create a custom stack of type structure with two elements, (element, min_till_now)
- implement the functions on this custom data type
Implementation:
C++
// 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; } |
Java
// program to demonstrate customized data structure // which supports functions in O(1) import java.util.ArrayList; public class Gfg { // class Pair static class Pair{ int element; int minElement; public Pair( int element, int minElement) { this .element = element; this .minElement = minElement; } } int min; ArrayList<Pair> stack = new ArrayList<>(); public Gfg() { this .min = Integer.MAX_VALUE; } // utility function for adding a new element void addElement( int x) { if (stack.size() == 0 || x < min) { min=x; } Pair pair = new Pair(x,min); stack.add(pair); System.out.println(x + " inserted successfully" ); } // utility function for returning last element of stack int getLastElement() { if (stack.size() == 0 ) { System.out.println( "UnderFlow Error" ); return - 1 ; } else { return stack.get(stack.size() - 1 ).element; } } // utility function for removing last element successfully; void removeLastElement() { if (stack.size() == 0 ) { System.out.println( "UnderFlow Error" ); } else if (stack.size() > 1 ) { min=stack.get(stack.size() - 2 ).minElement; } else { min=Integer.MAX_VALUE; } stack.remove(stack.size() - 1 ); System.out.println( "removed successfully" ); } // utility function for returning min element till now; int getMin() { if (stack.size() == 0 ) { System.out.println( "UnderFlow Error" ); return - 1 ; } return stack.get(stack.size() - 1 ).minElement; } // Driver Code public static void main(String[] args) { Gfg newStack = new Gfg(); newStack.addElement( 5 ); newStack.addElement( 7 ); newStack.addElement( 3 ); System.out.println( "min element :: " +newStack.getMin()); newStack.removeLastElement(); newStack.addElement( 2 ); newStack.addElement( 9 ); System.out.println( "last element :: " +newStack.getLastElement()); newStack.addElement( 0 ); System.out.println( "min element :: " +newStack.getMin()); newStack.removeLastElement(); newStack.addElement( 11 ); System.out.println( "min element :: " +newStack.getMin()); } } // This code is contributed by AkashYadav4. |
Python3
# Program to demonstrate customized data structure # which supports functions in O(1) import sys stack = [] Min = sys.maxsize # Utility function for adding a new element def addElement(x): global Min , stack if ( len (stack) = = 0 or x < Min ): Min = x pair = [x, Min ] stack.append(pair) print (x, "inserted successfully" ) # Utility function for returning last # element of stack def getLastElement(): global Min , stack if ( len (stack) = = 0 ): print ( "UnderFlow Error" ) return - 1 else : return stack[ - 1 ][ 0 ] # Utility function for removing last # element successfully; def removeLastElement(): global Min , stack if ( len (stack) = = 0 ): print ( "UnderFlow Error" ) elif ( len (stack) > 1 ): Min = stack[ - 2 ][ 1 ] else : Min = sys.maxsize stack.pop() print ( "removed successfully" ) # Utility function for returning min # element till now; def getMin(): global Min , stack if ( len (stack) = = 0 ): print ( "UnderFlow Error" ) return - 1 return stack[ - 1 ][ 1 ] # Driver code addElement( 5 ) addElement( 7 ) addElement( 3 ) print ( "min element ::" , getMin()) removeLastElement() addElement( 2 ) addElement( 9 ) print ( "Last element ::" , getLastElement()) addElement( 0 ) print ( "min element ::" , getMin()) removeLastElement() addElement( 11 ) print ( "min element ::" , getMin()) # This code is contributed by mukesh07 |
C#
// program to demonstrate customized data structure // which supports functions in O(1) using System; using System.Collections.Generic; class GFG { static List<Tuple< int , int >> stack = new List<Tuple< int , int >>(); static int min = Int32.MaxValue; // utility function for adding a new element static void addElement( int x) { if (stack.Count == 0 || x < min) { min=x; } Tuple< int , int > pair = new Tuple< int , int >(x,min); stack.Add(pair); Console.WriteLine(x + " inserted successfully" ); } // utility function for returning last element of stack static int getLastElement() { if (stack.Count == 0) { Console.WriteLine( "UnderFlow Error" ); return -1; } else { return stack[stack.Count - 1].Item1; } } // utility function for removing last element successfully; static void removeLastElement() { if (stack.Count == 0) { Console.WriteLine( "UnderFlow Error" ); } else if (stack.Count > 1) { min=stack[stack.Count - 2].Item2; } else { min=Int32.MaxValue; } stack.RemoveAt(stack.Count - 1); Console.WriteLine( "removed successfully" ); } // utility function for returning min element till now; static int getMin() { if (stack.Count == 0) { Console.WriteLine( "UnderFlow Error" ); return -1; } return stack[stack.Count - 1].Item2; } static void Main() { addElement(5); addElement(7); addElement(3); Console.WriteLine( "min element :: " +getMin()); removeLastElement(); addElement(2); addElement(9); Console.WriteLine( "Last element :: " +getLastElement()); addElement(0); Console.WriteLine( "min element :: " +getMin()); removeLastElement(); addElement(11); Console.WriteLine( "min element :: " +getMin()); } } // This code is contributed by divyeshrabadiya07. |
Javascript
<script> // program to demonstrate customized data structure // which supports functions in O(1) let min; let stack = []; min = Number.MAX_VALUE // utility function for adding a new element function addElement(x) { if (stack.length == 0 || x < min) { min=x; } let pair = [x,min]; stack.push(pair); document.write(x + " inserted successfully" + "</br>" ); } // utility function for returning last element of stack function getLastElement() { if (stack.length == 0) { document.write( "UnderFlow Error" + "</br>" ); return -1; } else { return stack[stack.length - 1][0]; } } // utility function for removing last element successfully; function removeLastElement() { if (stack.length == 0) { document.write( "UnderFlow Error" + "</br>" ); } else if (stack.length > 1) { min=stack[stack.length - 2][1]; } else { min=Number.MAX_VALUE; } stack.pop(); document.write( "removed successfully" + "</br>" ); } // utility function for returning min element till now; function getMin() { if (stack.length == 0) { document.write( "UnderFlow Error" + "</br>" ); return -1; } return stack[stack.length - 1][1]; } addElement(5); addElement(7); addElement(3); document.write( "min element :: " +getMin() + "</br>" ); removeLastElement(); addElement(2); addElement(9); document.write( "Last element :: " +getLastElement() + "</br>" ); addElement(0); document.write( "min element :: " +getMin() + "</br>" ); removeLastElement(); addElement(11); document.write( "min element :: " +getMin() + "</br>" ); // This code is contributed by rameshtravel07. </script> |
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)
Auxiliary space: O(n) for stack
Contact Us