Deterministic Selection - Select the i th smallest element

 Posted on May 1, 2014  (Last modified on August 7, 2020)  |  3 minutes  |  Kinshuk Chandra

We have already seen RSelect or Random Selection here. Now lets focus on DSelect. Though RSelect is good, and works in linear time, but it deterministically runs in O(n) time, even in worst case. But the downside is that it doesn’t runs as fast as RSelect, but its worst case is still better. Like in quicksort, we had it better than merge sort, but worst case of quicksort was worse than mergesort. [Read More]
Algorithms  kodeknight  randomized algorithm  largest  sorting  Data Structure  selection  kth-largest  smallest 

Find kth largest element from a 2-d sorted array

 Posted on May 1, 2014  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

Problem Given the 2D matrix or array - sorted row-wise and column-wise, find the kth largest element. Example Input Consider the array below and k=4 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 Output Output should be 22 Solution Method 1 - Use MaxHeaps We know if k=1, we should return A[n-1][n-1] i. [Read More]
kodeknight  snapdeal  largest  kth-largest 

Find kth largest in an Array

 Posted on February 14, 2014  (Last modified on August 7, 2020)  |  4 minutes  |  Kinshuk Chandra

**Problem : **  You have an array of numbers; you need to find the k-th largest in the arra Solution ** Method 1 - Tournament principle** We have to find the element which has competed with largest element, and is just (k-1)th level.We have discussed this principle here. Method 2 - Using max heap Consider the array of length n. Here is the algo :  Build a max heap in O(n) ;  Now remove k elements from the heap; wherein each removal costs log(n) time to maintain the heap property. [Read More]
max  kodeknight  largest  minmax  unsorted-array  kth-largest  min  smallest 

Find Nth largest element in the rotated sorted array

 Posted on August 24, 2013  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

Please give review to this post http://rawjava.blo…

Unknown - Apr 1, 2015

Please give review to this post
http://rawjava.blogspot.com/2015/04/java-program-to-find-maximum-number.html

Good question and equally good answer..Enjoyed your post :)

search  ArraySearch  kodeknight  recursion  array  binary search  rotated array  kth-largest  min  sorted-array 

Find Nth largest element in the rotated sorted array

 Posted on August 24, 2013  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

**Question : **Find Nth largest element in the rotated sorted array So for example we have sorted array as - 2,3,6,12, 15, 18. Now suppose the array is rotated k times ( we don’t know k), such that array becomes 15, 18,2,3,6,12 Solution So, to find the Nth largest element in normal sorted array is a[N]. But in this case it is rotated k, which we don’t know. [Read More]
search  ArraySearch  kodeknight  recursion  array  binary search  rotated array  kth-largest  min  sorted-array 

Randomized Selection : Selecting the i'th smallest element

 Posted on August 4, 2013  (Last modified on August 7, 2020)  |  3 minutes  |  Kinshuk Chandra

Input - array A with n distinct numbers and a number i ∈ {1,2,…,n} Output : ith order statistic i.e. ith smallest element of the input array O(n log n) algorithm Apply mergesort/quicksort Return the ith element of sorted array So, we used reduction via taking the help of sorting algorithm. So this was the naive way as we would be to say, “Hey let’s sort it and then we can just pick out the ith one! [Read More]
Algorithms  kodeknight  randomized algorithm  largest  sorting  Data Structure  selection  kth-largest  smallest 

Find nth largest value in a BST

 Posted on September 11, 2011  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

Hi there I was just going through your this post a… bakwasscoder - Jun 5, 2012Hi there I was just going through your this post and had a small doubt. Shouldn’t we do a stack based iterative traversal to get the correct value in this code ? This recursive may give wrong result as it will start counting after the rightmost element has been found. This element won’t be the nth largest in BST. [Read More]
tree  kodeknight  interview  largest  binary-search-tree  BST  kth-largest 

Find nth largest value in a BST

 Posted on September 11, 2011  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

Simplest solution is to do a reverse in order search and maintain a global counter.
ReverseInOrder(Tree T, n)
1. if (T->right != null ) ReverseInOrder(T->right)
2. if (count==n) return T. Else count++
3. if (T->left != null ) ReverseInOrder(T->left)

tree  kodeknight  interview  largest  binary-search-tree  BST  kth-largest