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 out the largest and second largest number in an array

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

Question: Write an efficient C program to find smallest and second smallest element in an array. Solution Method 1 - Compare each element with current max and second max Algorithm 1) Initialize both first and second smallest as a00 first = second = a00 2) Loop through all the elements. a) If the current element is greater than firstMax, then update firstMax and secondMax. b) Else if the current element is greater than second then update secondMax pseudocode [Read More]
max  kodeknight  largest  minmax  unsorted-array  min  second-largest 

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