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

- Harshit Shrivastava July 13, 2012 | Flag Reply
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.

- sushilk.1991 July 13, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 votes

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

- Anonymous July 13, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Constructing a heap of K elements is O(K)

- iamsubhra84 July 13, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Aashish July 14, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- sushilk.1991 July 14, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- eugene.yarovoi July 14, 2012 | Flag
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

- Anonymous July 13, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous July 13, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- nik July 15, 2012 | Flag
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)

- Himanshu July 13, 2012 | Flag Reply
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]

- Aks July 13, 2012 | Flag Reply
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;
        }

- Anonymous July 13, 2012 | Flag Reply
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 .

- Anonymous July 13, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous July 13, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use the quick-select algorithm.

- Anonymous July 13, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use the quick-select algorithm.

- Anonymous July 13, 2012 | Flag Reply
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]);
}

- ethioer July 14, 2012 | Flag Reply
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() */

}

- Sandeep Singh July 14, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

it fails on p_array[i] = constant

- caot July 29, 2014 | Flag
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]);
}

- Anonymous July 23, 2013 | Flag Reply
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;
}

- L August 13, 2013 | Flag Reply
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){
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;
}
}

- xx August 21, 2013 | Flag Reply
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){
            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;
    }
}

- xx August 21, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

it fails on element in list is constant

- caot July 29, 2014 | Flag
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;
}

- Anonymous July 14, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Sandeep Singh July 14, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous July 14, 2012 | Flag
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 votes

ah...

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

- nsdxnsk July 13, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can you explain how the program outpus kth smallest element.

- SantiagoYemmiganur July 13, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- nsdxnsk July 13, 2012 | Flag


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More