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.
Daily Archives: June 11, 2014
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”}.
Element repeated more than n/2 times – Fast majority vote algorithm
Find the element which repeated more than n/2 times in an given array of integers.
For example, A=[2, 2, 3, 2, 3, 3, 1, 3, 1]. We can clearly see that 3 is the majority.