Design a Data Structure that performs add in O(n) and getMinimum & deleteMinimum in O(1)
Design a data structure which can do following operations
- add() in O(n)
- getMinimum() in O(1)
- deleteMinimum() in O(1)
Source : MakeMyTrip Interview.
- Maintain a linkedlist with elements in increasing order.
- Move head to next position in case of delete Min operation.
- Return First element in case of get Min Operation.
Implementation:
#include <iostream>
// Node class
class Node
{
public:
int data;
Node* next;
Node(int d)
{
data = d;
next = nullptr;
}
};
// Main class
class MinDS
{
Node* start;
public:
MinDS()
{
start = nullptr;
}
// Function to add an element
void addElement(int d)
{
Node* tmp = new Node(d);
// If the linked list is empty
if (start == nullptr)
{
start = tmp;
return;
}
// If the new element is smaller than the head
if (d < start->data)
{
tmp->next = start;
start = tmp;
return;
}
// If the new element needs to be inserted in the middle
Node* prev = start;
Node* ptr = start->next;
while (ptr != nullptr)
{
if (d < ptr->data)
{
tmp->next = ptr;
prev->next = tmp;
return;
}
else
{
prev = ptr;
ptr = ptr->next;
}
}
prev->next = tmp;
}
// Function to get the minimum element
int getMin()
{
return start->data;
}
// Function to delete the minimum element
int delMin()
{
int min = start->data;
start = start->next;
return min;
}
// Function to print elements
void print()
{
Node* ptr = start;
std::cout << "Elements: ";
while (ptr != nullptr)
{
std::cout << ptr->data << ", ";
ptr = ptr->next;
}
std::cout << "\n";
}
};
int main()
{
MinDS x;
x.addElement(10);
x.addElement(20);
x.addElement(5);
x.addElement(15);
x.print();
std::cout << "Get Min: " << x.getMin() << std::endl;
std::cout << "Del Min: " << x.delMin() << std::endl;
x.print();
std::cout << "Min: " << x.getMin() << std::endl;
return 0;
}
// Java code for linked list to
// perform required operations
import java.util.*;
// Node class
class Node
{
int data;
Node next;
Node(int d)
{
data = d;
next = null;
}
}
// main class
class MinDS
{
Node start;
public MinDS()
{
start = null;
}
// Function to add element
void addElement(int d)
{
Node tmp = new Node(d);
// If linked list is empty
if (start == null)
{
start = tmp;
return;
}
// If head itself is greater
if (d < start.data)
{
tmp.next = start;
start = tmp;
return;
}
// If need to insert somewhere in middle
Node prev = start;
Node ptr = start.next;
while (ptr != null)
{
if (d < ptr.data)
{
tmp.next = ptr;
prev.next = tmp;
return;
}
else
{
prev = ptr;
ptr = ptr.next;
}
}
prev.next = tmp;
}
// Function to get minimum
int getMin()
{
return start.data;
}
// Function to delete minimum
int delMin()
{
int min = start.data;
start = start.next;
return min;
}
// Function to print elements
void print()
{
Node ptr = start;
System.out.print("Elements: ");
while (ptr != null)
{
System.out.print(ptr.data + ", ");
ptr = ptr.next;
}
System.out.println("\n");
}
// Driver code
public static void main(String[] args)
{
MinDS x = new MinDS();
x.addElement(10);
x.addElement(20);
x.addElement(5);
x.addElement(15);
x.print();
System.out.println("Get Min: " + x.getMin());
System.out.println("Del Min: " + x.delMin());
x.print();
System.out.println("Min: " + x.getMin());
}
}
# Python code for linked list to perform required operations
# Node class
class Node:
def __init__(self, d):
self.data = d
self.next = None
# Main class
class MinDS:
def __init__(self):
self.start = None
# Function to add element
def addElement(self, d):
tmp = Node(d)
# If linked list is empty
if self.start is None:
self.start = tmp
return
# If head itself is greater
if d < self.start.data:
tmp.next = self.start
self.start = tmp
return
# If need to insert somewhere in the middle
prev = self.start
ptr = self.start.next
while ptr is not None:
if d < ptr.data:
tmp.next = ptr
prev.next = tmp
return
else:
prev = ptr
ptr = ptr.next
prev.next = tmp
# Function to get minimum
def getMin(self):
return self.start.data
# Function to delete minimum
def delMin(self):
min_val = self.start.data
self.start = self.start.next
return min_val
# Function to print elements
def printList(self):
ptr = self.start
print("Elements: ", end="")
while ptr is not None:
print(ptr.data, end=", ")
ptr = ptr.next
print("\n")
# Driver code
if __name__ == "__main__":
x = MinDS()
x.addElement(10)
x.addElement(20)
x.addElement(5)
x.addElement(15)
x.printList()
print("Get Min:", x.getMin())
print("Del Min:", x.delMin())
x.printList()
print("Min:", x.getMin())
using System;
// Node class
public class Node
{
public int data;
public Node next;
// Constructor
public Node(int d)
{
data = d;
next = null;
}
}
// Main class
public class MinDS
{
private Node start;
// Constructor
public MinDS()
{
start = null;
}
// Function to add an element
public void AddElement(int d)
{
Node tmp = new Node(d);
// If the linked list is empty
if (start == null)
{
start = tmp;
return;
}
// If the new element is smaller than the head
if (d < start.data)
{
tmp.next = start;
start = tmp;
return;
}
// If the new element needs to be inserted in the middle
Node prev = start;
Node ptr = start.next;
while (ptr != null)
{
if (d < ptr.data)
{
tmp.next = ptr;
prev.next = tmp;
return;
}
else
{
prev = ptr;
ptr = ptr.next;
}
}
prev.next = tmp;
}
// Function to get the minimum element
public int GetMin()
{
if (start == null)
{
throw new InvalidOperationException("List is empty");
}
return start.data;
}
// Function to delete the minimum element
public int DelMin()
{
if (start == null)
{
throw new InvalidOperationException("List is empty");
}
int min = start.data;
start = start.next;
return min;
}
// Function to print elements
public void Print()
{
Node ptr = start;
Console.Write("Elements: ");
while (ptr != null)
{
Console.Write(ptr.data + ", ");
ptr = ptr.next;
}
Console.WriteLine();
}
}
class Program
{
static void Main(string[] args)
{
MinDS x = new MinDS();
x.AddElement(10);
x.AddElement(20);
x.AddElement(5);
x.AddElement(15);
x.Print();
Console.WriteLine("Get Min: " + x.GetMin());
Console.WriteLine("Del Min: " + x.DelMin());
x.Print();
Console.WriteLine("Min: " + x.GetMin());
}
}
// Node class
class Node {
constructor(d) {
this.data = d;
this.next = null;
}
}
// Main class
class MinDS {
constructor() {
this.start = null;
}
// Function to add element
addElement(d) {
let tmp = new Node(d);
// If linked list is empty
if (this.start === null) {
this.start = tmp;
return;
}
// If head itself is greater
if (d < this.start.data) {
tmp.next = this.start;
this.start = tmp;
return;
}
// If need to insert somewhere in middle
let prev = this.start;
let ptr = this.start.next;
while (ptr !== null) {
if (d < ptr.data) {
tmp.next = ptr;
prev.next = tmp;
return;
} else {
prev = ptr;
ptr = ptr.next;
}
}
prev.next = tmp;
}
// Function to get minimum
getMin() {
return this.start.data;
}
// Function to delete minimum
delMin() {
let min = this.start.data;
this.start = this.start.next;
return min;
}
// Function to print elements
print() {
let ptr = this.start;
let result = "Elements: ";
while (ptr !== null) {
result += ptr.data + ", ";
ptr = ptr.next;
}
console.log(result + "\n");
}
// Driver code
static main() {
let x = new MinDS();
x.addElement(10);
x.addElement(20);
x.addElement(5);
x.addElement(15);
x.print();
console.log("Get Min: " + x.getMin());
console.log("Del Min: " + x.delMin());
x.print();
console.log("Min: " + x.getMin());
}
}
// Call the main function
MinDS.main();
Output
Elements: 5, 10, 15, 20, Get Min: 5 Del Min: 5 Elements: 10, 15, 20, Min: 10
Contact Us