## Amdocs Interview Question for Software Engineer / Developers

Country: India

Comment hidden because of low score. Click to expand.
1
of 1 vote

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

Comment hidden because of low score. Click to expand.
1
of 3 vote

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.

Comment hidden because of low score. Click to expand.
2

When you use heap you are actually using sorting itself as constructing heap is O(nlogn)

Comment hidden because of low score. Click to expand.
0

Constructing a heap of K elements is O(K)

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

Ya we have to change the construction of max heap such that similar elements are neglected and only one instance of it is considered.

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

Augmented RB tree will have nlgn complexity, u missed to consider complexity in construction of an augmented RB tree.

Comment hidden because of low score. Click to expand.
0
of 0 vote

it doesnot do any good . If k = n/2 you have O(n*n)

Comment hidden because of low score. Click to expand.
0
of 2 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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 .

Comment hidden because of low score. Click to expand.
0

Again this is kind of sorting, heap sort, you are asked not to use sorting

Comment hidden because of low score. Click to expand.
0
of 0 vote

Use the quick-select algorithm.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Use the quick-select algorithm.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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]);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

/*
* 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() */

}

Comment hidden because of low score. Click to expand.
0

it fails on p_array[i] = constant

Comment hidden because of low score. Click to expand.
0
of 0 vote

main()
{
int i,j,m,temp,k;
int a[]={1,3,6,8,-5,-2,3,8};
for(i=0;i<4;i++)
{
for(j=4,m=0;j<8;j=j++,m++)
{
if(a[i]>=a[j])
{
temp=a[j];
for(k=j;k>i;k--)
{
a[k]=a[k-1];
}
a[k]=temp;
}
}}
for(i=0;i<8;i++)
printf(" %d ",a[i]);
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

/** 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;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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){
}
else if(list.get(i)>pivot){
}
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;
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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){
}
else if(list.get(i)>pivot){
}
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;
}
}``````

Comment hidden because of low score. Click to expand.
0

it fails on element in list is constant

Comment hidden because of low score. Click to expand.
-1
of 1 vote

``````#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;
}``````

Comment hidden because of low score. Click to expand.
0

Your Code provides the smallest Number, not the kth smallest number in the Array

Comment hidden because of low score. Click to expand.
0

@Sandeep: Oops... U r rite... I did not read the question correctly... Need to think again...

Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0

ah...

Time complexity is O(k * n)... not n!

Comment hidden because of low score. Click to expand.
0

Can you explain how the program outpus kth smallest element.

Comment hidden because of low score. Click to expand.
0

Simply return smallest after k loop but as others imply, this is not good solution at all since it's like brute force.
Maybe modification of quick sort helps

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.