Return k’th largest element in a stream
Given an infinite stream of integers, return the element representing the k’th largest element in the stream.
Tag: Priority Queue
Connect `n` ropes with minimal cost
Given n ropes of different lengths, connect them into a single rope with minimum cost. Assume that the cost to connect two ropes is the same as the sum of their lengths.
Replace each array element by its corresponding rank
Given an array of distinct integers, replace each array element by its corresponding rank in the array. The minimum array element has the rank 1; the second minimum element has a rank of 2, and so on…
Efficiently merge `k` sorted linked lists
In the previous post, we have discussed how to merge two sorted linked lists into one list. This post will merge k sorted linked lists into a single list efficiently.
Merge `M` sorted lists of variable length
Given M sorted lists of variable length, print them efficiently in sorted order.
Introsort Algorithm – Overview and C++ Implementation
Introsort is an efficient in-place sorting algorithm, which usually beats all other sorting algorithms in terms of performance. Due to its high performance, it is used in several standard library sort functions.
Huffman Coding Compression Algorithm
Huffman coding (also known as Huffman Encoding) is an algorithm for doing data compression, and it forms the basic idea behind file compression. This post talks about the fixed-length and variable-length encoding, uniquely decodable codes, prefix rules, and Huffman Tree construction.
Find first `k` maximum occurring words in a given set of strings
Given a huge set of words with duplicates present and a positive integer k, find the first k–maximum occurring words in it.
Find first `k` non-repeating characters in a string in a single traversal
Given a string, find first k non-repeating characters in it by doing only a single traversal of it.
Min Heap and Max Heap Implementation in Java
In previous post, we have introduced the heap data structure and covered heapify-up, push, heapify-down and pop operations. This article covers Java implementation of Priority Queue Data Structure (Max Heap and Min heap).
External Merge Sort Algorithm
The external merge sort algorithm is used to efficiently sort massive amounts of data when the data being sorted cannot be fit into the main memory (usually RAM) and resides in the slower external memory (usually a HDD).
Travelling Salesman Problem using Branch and Bound
Given a set of cities and the distance between every pair of cities, the problem is to find the shortest possible route that visits every city exactly once and returns to the starting point.