Amdocs Interview Question
Software Engineer / DevelopersCountry: India
We can find kth smallest or maximum no using max or min heap concept as follows:
Step 1: From first K numbers build a max heap so that the top element is the largest among first K nos. Say that element is X
Step 2: Now as numbers are coming for processing, say coming number be A
If A>X then A cant be Kth Smallest.
If A=X then no change is needed.
If A<X then X cant be Kth smallest element so replace X with A and call Heapify.
For Kth largest build min heap.
When you use heap you are actually using sorting itself as constructing heap is O(nlogn)
What are doing with the duplicates?
If the array contains 3,3,3. What is the 2nd largest here.
Construction of max heap needs a little change here.
Ya we have to change the construction of max heap such that similar elements are neglected and only one instance of it is considered.
@Anonymous, @iamsubhra84: you're both wrong. If there are K elements in the heap, doing a heap remove / insert is O(logK), and you'll have to do that for up to N elements as you're
traversing the array, so the algorithm has O(NlogK) complexity.
@iamsubhra84: Perhaps you were referring to the fact that there exists a O(K) algorithm for making a heap out of K already determined elements. That's true but irrelevant in the analysis of this algorithm.
There are 2 approaches with which u can find kth smallest elemnt
a.) n th order stastics : concept of quick sort.... complexity is O(n)
b.) Augmenting Red Black Tree...... complexity O(logn)
u can refer introduction to algorithm by coreman....this algo are clearly explaind in this book
Yes, it can be solved using n th order statistics, using partitioning algorithm of quick sort you can take a look at this video, it explains the concept well
youtube.com/watch?v=kcVk30zzAmU
Using Quicksort..........
def quick_sort(list):
"""Quicksort"""
if list == []:
return []
else:
pivot = list[0]
lesser = quick_sort([x for x in list[1:] if x < pivot])
greater = quick_sort([x for x in list[1:] if x >= pivot])
return lesser + [pivot] + greater
def min_element(list):
sort_list = quick_sort(list)
return sort_list[0]
private static int GetKthSmallestItem(int[] array, int k)
{
//Current rank of smallest value
int currentRank = 1;
//Store first value as smallest value for rank 1
int KthSmallValue = array[0];
//Loop through array starting from 2nd element
for (int i = 1; i < array.Length; i++)
{
//If next array element is greater then one
//and current rank is not yet equal to k then
//replace kthSmallValue and increement currentRank
if (KthSmallValue < array[i])
{
if (currentRank < k)
{
KthSmallValue = array[i];
currentRank++;
}
}
//If next array element is smaller then kthSmallValue
//then adjust kthSmallValue with last max value
else
{
int MaxValue = array[i];
for (int j = 0; j < i; j++)
{
if (MaxValue < array[j] && (currentRank<k || KthSmallValue > array[j]))
{
MaxValue = array[j];
}
}
if (MaxValue >= KthSmallValue)
currentRank++;
KthSmallValue = MaxValue;
}
}
return KthSmallValue;
}
best way that i know of is to make use of min heap , and delete the first k elements to get the desired element as mentioned in this question .
after deleting the k elements , make sure the head is properly heapified again to maintain the min heap properties .
Since sorting of any kind is not allowed, the best could be O(n*k)
#include <stdio.h>
/*
* Find Kth smallest element
*/
void main()
{
int nums[] = {8, 12, 1, 90, 4, 6, 2};
int k = 3, i = 0;
//just initial setup for comparison purpose onlyi
int temp_arr[k];
while(i < sizeof(nums)/sizeof(int))
{
int j;
int curr_num = nums[i];
for (j=0 ; j < k ; j++)
{
if (curr_num < temp_arr[j])
{
int temp = temp_arr[j];
temp_arr[j] = curr_num;
curr_num = temp;
}
}
i++;
}
printf("%i", temp_arr[k-1]);
}
/*
* Given : An Unsorted Array
* Required : Find the kth Smallest Number in this Array.
*
* Example :
Array: {1,3,5,4,2};
kth_count=1 => 1st Smallest No. = 1
kth_count=2 => 2nd Smallest No. = 2
kth_count=3 => 3rd Smallest No. = 3
kth_count=4 => 4th Smallest No. = 4
kth_count=5 => 5th Smallest No. = 5
*
*/
#include <stdio.h>
#define INVALID_VAL -1
#define MAX_SIZE 5
#define SUCCESS 0
void Find_kth_Smallest_Numb (int *p_array, int kth_count);
int main()
{
int array[MAX_SIZE] = {1,3,5,4,2};
int kth_count = INVALID_VAL;
printf ("\nEnter kth_count: "); /* If you want 3rd smallest no., kth_count = 3 */
scanf ("%d", &kth_count);
/* If k = 3 & MAX_SIZE = 2 => Required No. must be greater than 2 numbers (as it is the 3rd smallest number)
and it should be lesser than 2 numbers */
Find_kth_Smallest_Numb (array, kth_count);
return 0;
}
void Find_kth_Smallest_Numb (int *p_array, int kth_count)
{
int index = INVALID_VAL;
int count_smaller_numbs = INVALID_VAL;
int count_greater_numbs = INVALID_VAL;
int counter = INVALID_VAL;
for (index=0; index<MAX_SIZE; index++)
{
for (counter=0, count_smaller_numbs = 0, count_greater_numbs = 0;
(counter<MAX_SIZE && count_smaller_numbs <= (kth_count - 1) && count_greater_numbs <= (MAX_SIZE - kth_count));
counter++)
{
if (index==counter) /* No Need to compare the Number with Itself */
{
continue;
}
if (p_array[index]<p_array[counter])
{
count_greater_numbs++;
}
else if (p_array[index]>p_array[counter])
{
count_smaller_numbs++;
}
if ((count_smaller_numbs == kth_count - 1) &&
(count_greater_numbs == MAX_SIZE - kth_count))
{
printf ("\n\n%dth Smallest Number = %d\n\n", kth_count, p_array[index]);
return;
}
} /* Inner For loop() */
} /* Outer For loop() */
}
/** Find the kth smallest element of an unsorted vector */
#include <iostream>
#include <algorithm>
#include <vector>
#include <cassert>
using namespace std;
template<typename T>
size_t partition(vector<T> &vec, size_t first, size_t last) {
if (first == last || first == last - 1)
return first;
size_t part = first;
// TODO median3(first, middle, last)
for (size_t curr = first; curr < last; ++curr)
if (vec[curr] < vec[first])
swap(vec[curr], vec[++part]);
swap(vec[part], vec[first]);
return part;
}
template<typename T>
T topk(vector<T> vec, size_t k) {
assert(k > 0 && "The K must be a positive number!");
assert(k <= vec.size() && "The K must be less than vector.size!");
size_t first = 0, last = vec.size();
while (first < last) {
size_t part = partition(vec, first, last);
if (part - first == k - 1) // found the number
return vec[part];
else if (part - first > k - 1)
last = part;
else {
k -= part - first + 1;
first = part + 1;
}
}
assert("Unreachable");
}
int main() {
vector<int> a = {10, 20, 30, 40, 50};
for (int i = 1; i <= 5; i++)
assert(topk(a, i) == 10 * i);
vector<int> b = {40, 50, 60, 20, 10, 30, 70};
for (int i = 1; i <= 7; i++)
assert(topk(b, i) == 10 * i);
return 0;
}
public int quickSelect(ArrayList<Integer>list, int nthSmallest){
//Choose random number in range of 0 to array length
Random random = new Random();
//This will give random number which is not greater than length - 1
int pivotIndex = random.nextInt(list.size() - 1);
int pivot = list.get(pivotIndex);
ArrayList<Integer> smallerNumberList = new ArrayList<Integer>();
ArrayList<Integer> greaterNumberList = new ArrayList<Integer>();
//Split list into two.
//Value smaller than pivot should go to smallerNumberList
//Value greater than pivot should go to greaterNumberList
//Do nothing for value which is equal to pivot
for(int i=0; i<list.size(); i++){
if(list.get(i)<pivot){
smallerNumberList.add(list.get(i));
}
else if(list.get(i)>pivot){
greaterNumberList.add(list.get(i));
}
else{
//Do nothing
}
}
//If smallerNumberList size is greater than nthSmallest value, nthSmallest number must be in this list
if(nthSmallest < smallerNumberList.size()){
return quickSelect(smallerNumberList, nthSmallest);
}
//If nthSmallest is greater than [ list.size() - greaterNumberList.size() ], nthSmallest number must be in this list
//The step is bit tricky. If confusing, please see the above loop once again for clarification.
else if(nthSmallest > (list.size() - greaterNumberList.size())){
//nthSmallest will have to be changed here. [ list.size() - greaterNumberList.size() ] elements are already in
//smallerNumberList
nthSmallest = nthSmallest - (list.size() - greaterNumberList.size());
return quickSelect(greaterNumberList,nthSmallest);
}
else{
return pivot;
}
}
public int quickSelect(ArrayList<Integer>list, int nthSmallest){
//Choose random number in range of 0 to array length
Random random = new Random();
//This will give random number which is not greater than length - 1
int pivotIndex = random.nextInt(list.size() - 1);
int pivot = list.get(pivotIndex);
ArrayList<Integer> smallerNumberList = new ArrayList<Integer>();
ArrayList<Integer> greaterNumberList = new ArrayList<Integer>();
//Split list into two.
//Value smaller than pivot should go to smallerNumberList
//Value greater than pivot should go to greaterNumberList
//Do nothing for value which is equal to pivot
for(int i=0; i<list.size(); i++){
if(list.get(i)<pivot){
smallerNumberList.add(list.get(i));
}
else if(list.get(i)>pivot){
greaterNumberList.add(list.get(i));
}
else{
//Do nothing
}
}
//If smallerNumberList size is greater than nthSmallest value, nthSmallest number must be in this list
if(nthSmallest < smallerNumberList.size()){
return quickSelect(smallerNumberList, nthSmallest);
}
//If nthSmallest is greater than [ list.size() - greaterNumberList.size() ], nthSmallest number must be in this list
//The step is bit tricky. If confusing, please see the above loop once again for clarification.
else if(nthSmallest > (list.size() - greaterNumberList.size())){
//nthSmallest will have to be changed here. [ list.size() - greaterNumberList.size() ] elements are already in
//smallerNumberList
nthSmallest = nthSmallest - (list.size() - greaterNumberList.size());
return quickSelect(greaterNumberList,nthSmallest);
}
else{
return pivot;
}
}
#include<stdio.h>
#include<stdlib.h>
int main()
{
int a[10], i, j, n, index = 0;
printf("\nEnter the number of elements\n");
scanf("%d", &n);
printf("\nEnter the elements\n");
for(i = 0; i < n; i++)
scanf("%d", &a[i]);
i = 0;
j = n-1;
while(i != j)
{
if(a[i] < a[j])
{
j--;
index = i;
}
else
{
i++;
index = j;
}
}
printf("\nThe smalles element is %d\n", a[index]);
system("pause");
return 0;
}
Making use of quick sort algorithm, achieve a partition for the position of kth element. All the elements before kth position are smaller than the kth element
- Harshit Shrivastava July 13, 2012