Reverse digits of a signed integer - Leet Code Solution
Problem Statement Given a signed integer, reverse digits of an integer. Return…
July 10, 2019
Min Priority Queue is a data structure which manage a list of keys(values). And, gives priority to element with minimum value.
It supports following operations:
(Heap data structure)[/coding-interview/what-is-heap-data-structure/] can be used for its implementation.
Lets see each one of them:
public class MinPriorityQueue {
private int[] heap;
private int maxSize;
private int heapSize;
public MinPriorityQueue(int maxSize) {
this.maxSize = maxSize;
this.heap = new int[maxSize];
this.heapSize = 0;
}
@Override
public String toString() {
return ArrayUtils.toString(this.heap, this.heapSize);
}
private int getLeftChild(int index) { return 2*index + 1;}
private int getRightChild(int index) { return 2*index + 2;}
private int getParent(int index) {
if (index == 0) {
return -1;
}
return (index-1)/2;
}
private void minHeapify(int index) {
int smallest = index;
int l = this.getLeftChild(index);
int r = this.getRightChild(index);
if (l < this.heapSize && this.heap[l] < this.heap[index]) {
smallest = l;
}
if (r < this.heapSize && this.heap[r] < this.heap[smallest]) {
smallest = r;
}
if (smallest != index) {
ArrayUtils.swap(this.heap, smallest, index);
this.minHeapify(smallest);
}
}
/**
* Get the min element, do not delete
*/
public int getMin() throws Exception {
if (this.heapSize == 0) {
throw new Exception("Heap underflow");
}
return this.heap[0];
}
/**
* Get the min, and delete from heap
* Runs in O(log n)
*/
public int extractMin() throws Exception {
if (this.heapSize == 0) {
throw new Exception("Heap underflow");
}
int ret = this.heap[0];
this.heap[0] = this.heap[this.heapSize-1];
this.heapSize --;
this.minHeapify(0);
return ret;
}
/**
* Set the value at index specified to new value specified
*/
public void decrement(int index, int newValue) throws Exception {
if (index > this.heapSize-1) {
throw new Exception("Overflow");
}
this.heap[index] = newValue;
while (index > 0 && this.heap[index] < this.heap[this.getParent(index)]) {
ArrayUtils.swap(this.heap, index, this.getParent(index));
index = this.getParent(index);
}
}
public void insert(int val) throws Exception {
if (this.heapSize >= this.maxSize) {
throw new Exception("Overflow");
}
this.heapSize ++;
this.heap[this.heapSize-1] = Integer.MAX_VALUE;
this.decrement(this.heapSize-1, val);
}
public static void main(String[] args) throws Exception {
MinPriorityQueue q = new MinPriorityQueue(10);
//fresh state
System.out.println(q);
//lets insert 5 elements
q.insert(10); q.insert(5); q.insert(4); q.insert(6); q.insert(20);
System.out.println(q);
System.out.println("Min: " + q.getMin());
System.out.println("Extracting min: " + q.extractMin());
System.out.println("State: " + q);
System.out.println("Decrementing index-2 to 4");
q.decrement(2, 4);
System.out.println("State: " + q);
System.out.println("Extracting min: " + q.extractMin());
System.out.println("State: " + q);
System.out.println("Extracting min: " + q.extractMin());
System.out.println("State: " + q);
}
}
To know about basic Heap data structure, and its heapify operation. See: (Heap data structure)[/coding-interview/what-is-heap-data-structure/] Its an important data structure for interview purpose.
Runtime complexity is O(1) Since we are maintaining min heap. The minimum value is always at 0th index. Just return it.
Runtime complexity is O(log n)
Runtime complexity is O(log n)
Runtime complexity is O(log n)
Problem Statement Given a signed integer, reverse digits of an integer. Return…
Problem Statement Maximum Length of Subarray With Positive Product. Given an…
Its a kind of incremental insertion technique, where the algorithm build up…
Problem Statement Say you have an array prices for which the ith element is the…
Problem Statement Given two arrays, write a function to compute their…
Its every software engineer’s dream to work with the big FAANG companies…
Introduction In this post we will see following: How to schedule a job on cron…
Introduction There are some cases, where I need another git repository while…
Introduction In this post, we will see how to fetch multiple credentials and…
Introduction I have an automation script, that I want to run on different…
Introduction I had to write a CICD system for one of our project. I had to…
Introduction Java log4j has many ways to initialize and append the desired…