Given a 2D array with rows sorted in ascending order. Find the median of the whole 2D array.

For example,

Median (or kth Smallest) of a sorted 2D array. Read the full post (478 words, estimated 1:55 mins reading time)

Given a 2D array with rows sorted in ascending order. Find the median of the whole 2D array.

For example,

This is a preview of

Median (or kth Smallest) of a sorted 2D array. Read the full post (478 words, estimated 1:55 mins reading time)

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].

This is a preview of

Kth Smallest Element and median of Two Sorted Arrays. Read the full post (791 words, estimated 3:10 mins reading time)

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.

This is a preview of

Kth smallest/largest element in an array. Read the full post (1099 words, estimated 4:24 mins reading time)

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”}.

This is a preview of

Top K or K-most frequent words in a document. Read the full post (748 words, estimated 3:0 mins reading time)

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.

This is a preview of

Kth smallest/minimum element in a BST – Rank of a BST node. Read the full post (437 words, estimated 1:45 mins reading time)

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.

This is a preview of

K closest points. Read the full post (719 words, estimated 2:53 mins reading time)