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”, […]
Tag Archives: kth smallest
Given a 2D array with rows sorted in ascending order. Find the median of the whole 2D array. For example, A= 2, 4, 5, 6 1, 2, 2 ,4 3, 4, 4, 5 1, 2 , 3, 3 Then the merged array would be [1, 1, 2, 2 ,2, 2, 3, 3, 3, 4, 4, […]
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 […]
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. A trivial solution is to sort the array. But question […]
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, […]
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. Notice the key requirement here: “K is much smaller than N. N is very large”. Definitely the brute-force solution by finding distance of […]