Given a 2D array with rows sorted in ascending order. Find the median of the whole 2D array.
For example,
Tag Archives: kth smallest
Kth Smallest Element and median of Two Sorted Arrays
Given two sorted arrays find the element which would be kth in their merged and sorted combination.
For example, A=[1, 1, 2, 3, 10, 15] and B=[-1, 2, 3, 4, 6, 7] then k=8th smallest element would be 4 as it appears in 8th position of the merged sorted array=[-1, 1, 1, 2, 2, 3, 3, 4, 6, 7, 10, 15].
Kth smallest/largest element in an array
Given an array of integer. Find the kth smallest element in the array in a most efficient manner.
For example: A = [2, 1, 0, 3, -1, 3] and k=3 then the 3rd smallest element is 1. This is also (6-3) = 3rd largest element.
Top K or K-most frequent words in a document
Given a document (or stream) of words. Find the top k most frequent words in the document (or stream).
For example, if stream = “aa bb cc bb bb cc dd dd ee ff ee dd aa ee”. That is, {“dd”=3, “ee”=3, “ff”=1, “aa”=2, “bb”=3, “cc”=2}. Then top 3 most frequent words are: {“dd”, “ee”, “bb”}.
Kth smallest/minimum element in a BST – Rank of a BST node
Given a binary search tree. Find the kth smallest element in the BST.
A quick solution would be to perform a modified inorder traversal with an extra parameter k. Each time inorder traversal is popping a node out of recursion/call stack (i.e. unwinding a recursion)then we keep decreasing the k. When k=0 then the current node in the call stack is the desired kth smallest node. This is O(n) time algorithm.
K closest points
Given an array containing N points find the K closest points to the origin in the 2D plane. You can assume K is much smaller than N and N is very large.