Amdocs Interview Question Testing / Quality Assurances

  • amdocs-interview-questions
    0
    of 0 votes
    19
    Answers

    Given an integer array of which both first half and second half are sorted. Write a function to merge the two parts to create one single sorted array in place [do not use any extra space].
    e.g. If input array is [1,3,6,8,-5,-2,3,8] It should be converted to: [-5,-2,1,3,3,6,8,8]

    - DInesh on April 07, 2011 Report Duplicate | Flag
    Amdocs Testing / Quality Assurance Algorithm Arrays



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

I have solved this problem in c#. Compare the first and mid element on the array, like that we compare the all the array elements. When we find smaller number in the second set of array, need to swap the array elements.

void mergetwoSortedRangeArray(int[] arr)
{
int i=0;
int j=(int)arr.Length/2;
while(i<j && j< arr.Length -1)
{

if (arr[i] > arr[j])
{
rotateArray(arr, i, j);
j++;
}
i++;
}
}

void rotateArray(int[] arr, int startInd, int endInd)
{
int newInd = startInd, temp = 0;
int? prevValue = null;

if ((endInd - startInd) > 1)
{
for (int i = startInd; i <= endInd; i++)
{
if (newInd == endInd)
newInd = startInd;
else
newInd++;

temp = arr[newInd];
if (prevValue == null)
arr[newInd] = arr[i];
else
arr[newInd] = (int)prevValue;
prevValue = temp;
}
}
}


Let me know if anyone find better solution

- N on April 07, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

For input array: {1, 3, 6, 8, -5, -2, 3, 8 }
Your code return:
{1, 1, 1, 1, 1, 1, 3, 8}

- m@}{ on April 07, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I have tested this algorithm with different inputs. It works without any issue. Can you check it out what is wrong on this algorithm?

- N on April 07, 2011 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Your rotateArray doesn't "rotate" a range with just two elements. In that case endInd = startEnd + 1. So, endInd - startInd is 1, and rotateArray does nothing. Change the test to
if ((endInd - startInd) >= 1)
The other mistake you have is that mergeSortedRangeArray skips the very last element.
Change the while condition to
while (i < j && j < arr.length)
Try you current implementation on {1, 4, 2, 3}.
Unfortunately your solution is O(n^2). It is just an insert sort. It is possible to do the merge in O(n) time.

- Anonymous on April 09, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

1) We could use in-place sort algorithm (quicksort for example). space: O(1) time: O(n*lgn).
2) Use in-place merge algorithm.

- m@}{ on April 07, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

bitonic sort

- camSun on April 17, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

// java code


public class MergeShort {

/**
* @param args
*/
/**
* @param args
*/
public static void main(String[] args) {
int[] a={4,7,9,20,1,3,10,15};
int i=0, length=8, j, k, temp;
// for(i=0;i<length;i++){
// System.out.println(i+":"+a[i]);
// }
for(j=length/2; j<length; j++){
for(; i<j; i++){
if(a[i] >= a[j]){
temp=a[j];
for(k=j; k>i; k--){
a[k]=a[k-1];
}
a[i]=temp;
i++;
break;
}
}
}
System.out.println("#######################");
for(i=0;i<length;i++){
System.out.println(i+":"+a[i]);
}

}

}

- Arun Kumar on August 18, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I've wrote just logic using some hard coded values like array length.

- Arun Kumar on August 18, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Are not we using extra space 'temp'?? [do not use any extra space] It is clearly specified in given question.

- jaip42 on February 10, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

We can do it inplace using heapssort method

- Ashupriya on July 01, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I am downvoting this answer, because there are lots of ways to in-place sort a list, but this brief answer doesn't explain why heapsort would be superior to, say, quicksort, given the partial ordering.

Of the most common divide-and-conquer sorts, mergesort is the one that breaks down the problem by recursively creating two sorted lists, so it would seem like the most appropriate sort to adopt for this problem. Unfortunately, it's really hard to do a mergesort efficiently on array-based lists when you don't have contiguous storage at your disposal for the merged result. If the original list were a linked list instead of an array, then you could do it pretty trivial with no extra storage, but the problem explicitly says this an array.

- showell30@yahoo.com on March 16, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>
void mergetwoSortedRangeArray(int *, int );
void swap(int *, int *);

int main(void){

	int a[8]={1,3,6,8,-5,-2,3,8};
	int len = sizeof(a)/sizeof(int);
	mergetwoSortedRangeArray(a,len);
	for(int i=0; i<len; i++){
		printf("%d 	",a[i]);
	}

		 return 0;
}

void mergetwoSortedRangeArray(int a[], int len){
	int i=0, j=len/2;
	while(i<j && j<=len){
		if(a[j]<a[i]){
			for(int k=i; k<j; k++){
				swap(&a[k], &a[j]);
			}
			i++;
			j++;
		}
		else{
			i++ ;
		}
	}
			printf("\n");
}

void swap(int *x, int *y){
	*x ^= *y;
	*y ^= *x;
	*x ^= *y;
}

- Jai Prakash on July 01, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

$arr = array(1,3,6,8,-5,-2,3,8);

$arr_len = count($arr);

$mid = $arr_len/2;
$i=0;

while ($mid < $arr_len) {
if ($arr[$i] < $arr[$mid]) {
$i++;
} else {
$temp = $arr[$i];
$arr[$i] = $arr[$mid];
$arr[$mid] = $temp;
$mid++;
}
}

- nhc002 on October 10, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>
#include<conio.h>

int _tmain(int argc, _TCHAR* argv[])
{
int a[8],len,*p,temp=0,i,j;
a[8]=(1,3,6,8,-5,-2,3,8);
p=a;

len=sizeof(a)/sizeof(a[0]);

printf("length of the array is : %d",len);
printf("\n");
for( i=0;i<len/2;i++)
{
for( j=len/2;j<len;j++)
{
if(*(p+i) > *(p+j) || *(p+i)==*(p+j))
{
int k=0;
k=k+i;
temp=*(p+j);
printf("%d ",*(p+j));
while(k<=j)
{
*(p+k+1)=*(p+k);

k++;

}
*(p+i)=temp;


}

}
}
for(i=0;i<len;i++)
{
printf("%d ",*(p+i));
}

getch();






return 0;
}
--------------------------------------------------------------------------------------------------
check and plz let me knw tat what is the problem in this code?

- sahil on November 08, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

and plz dont consider line-> printf("%d ",*(p+j));

- Anonymous on November 08, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

C# code 
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Sort2HalfSortedArrays
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] array = { 1, 3, 6, 8, -5, -2, 3, 8 };
            int[] sortedArray = Sort(array); ;
            Console.WriteLine("Sorted Array");
            for (int i = 0; i < sortedArray.Length; i++)
            {
                Console.Write("{0} ", sortedArray[i]);
            }
            Console.Read();

        }
        public static int[] Sort(int[] array)
        {
            int i = 0;
            while (array[i] < array[i + 1])
            {
                if (i + 1 == array.Length - 1)
                {
                    return array;
                }
                else
                {
                    i++;
                }
            }

            int j = array.Length - 1;
            while ((i >= 0) && i < j)
            {
                if (array[i] >= array[j])
                {
                    int k = i;
                    while (k < j)
                    {
                        int temp = array[k];
                        array[k] = array[k + 1];
                        array[k + 1] = temp;
                        k++;
                    }
                    i--;
                    j -= 2;
                }
                else
                {
                    j--;
                }
            }
            return array;
        }

        
    }
}


output:
Sorted Array 
-5,-2,1,3,3,6,8,8

Comment if any issues in this.

- pdvijetha on January 15, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Basically what we are doing is comparing the first element of both sorted portion

Scenario 1) in case second portion elemnt is smaller , we are bringing it to front and shifting the elements to right making room for it

Scenario 2) in case first portion elemnt is smaller, just goto second element in first portion, remain at first element in second portion

1,3,6,8,-5,-2,3,8
-5,1,3,6,8,-2,3,8
-5,-2,1,3,6,8,3,8
-5,-2,1,3,6,8,3,8
-5,-2,1,3,3,6,8,8

detail explanation


array length = 8
i = 0 ;
j = length/2; => 4

indices 0 1 2 3 4 5 6 7
values 1 3 6 8 -5 -2 3 8

compare if (a[i] > a[j]) i.e a[0] and a[4] ( 1 > -5 in our example)
place a[j] in a[i] and shift every indices by one
i.e. each a[i+1]= a[i] till a[j];
i++, j++

indices 0 1 2 3 4 5 6 7
values -5 1 3 6 8 -2 3 8

now compare a[1] with a[5] ( 1 > -2) , replace a[1] with a[5] ans shift

indices 0 1 2 3 4 5 6 7
values -5 -2 1 3 6 8 3 8

i++, j++;

compare a[2] with a[6] this time a[i] < a[j], no swap and shifting is required, but dont increase j only i

indices 0 1 2 3 4 5 6 7
values -5 -2 1 3 6 8 3 8
i++; j is not increased

now a[3] with a[6] still a[3] is less than a[6] so increase i only
indices 0 1 2 3 4 5 6 7
values -5 -2 1 3 6 8 3 8


now a[4] with a[6], swap and shift, we get

indices 0 1 2 3 4 5 6 7
values -5 -2 1 3 3 6 8 8
i++, j++


now a[5] with a[7], no change required, increase only i;

similalry done

- Gaurav Khurana on March 16, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is my algo:
Consider an array: [1, 3, 6, 8, -5, -2, 3, 8]
We have to maintain two pointers 'endOfTheFirstHalf' and 'endOfTheSecondHalf'. Both pointers will indicate the maximum element in given half.
1) At the beginning the first pointer is indicating the element at index 3 = 8 whereas second pointer index 7 which is also equal 8.
2) Move second pointer till you find element which is smaller then max element in first half indicated by first pointer
in this case it is index 6 = 3;
3) Shift left all elements located between firstPtr and secPtr by one to make place for max element e.g. after first swap original array looks like this: [1, 3, 6, -5, -2, 3, 8, 8] (elements -5, -2, 3 were shift left by one position)
4) Assign max element firstPtr to its position - move element at index 3 = 8 to index 6 where previously was an element = 3
5) Repeat the process till all elements in first half are smaller the min element in sec half. Here is the output from my program:
[1, 3, 6, 8, -5, -2, 3, 8]
[1, 3, 6, -5, -2, 3, 8, 8]
[1, 3, -5, -2, 3, 6, 8, 8]
[1, -5, -2, 3, 3, 6, 8, 8]
[-5, -2, 1, 3, 3, 6, 8, 8]

Code:

public static void merge2(int arr[]) {

	int endOfSecHalf = arr.length - 1;
	int endOfFirstHalf = arr.length / 2 - 1;
	System.out.println(Arrays.toString(arr));
	while (endOfFirstHalf >= 0) {
	    // find first smaller element in sec half then the max el in first half
	    while (arr[endOfSecHalf] >= arr[endOfFirstHalf] && endOfSecHalf > endOfFirstHalf) {
		endOfSecHalf--;
	    }
	    // all elements in sec half are bigger the elements in the first
	    // half
	    if (endOfSecHalf == endOfFirstHalf) {
		// break;
		return;
	    }
	    int temp = arr[endOfFirstHalf];
	    for (int i = endOfFirstHalf + 1; i <= endOfSecHalf; i++) {
		arr[i - 1] = arr[i];
	    }
	    arr[endOfSecHalf] = temp;
	    endOfSecHalf--;
	    endOfFirstHalf--;
	    System.out.println(Arrays.toString(arr));
	}
    }

- Anonymous on June 26, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

#include<iostream>
using namespace std;
int main()
{
	int i,j,temp,n=8;
	int a[8]={1,3,6,8,-5,-2,3,8};
	i=0,j=4;
	while(i<j && j<n)
	{
		if(a[j] <= a[i])
		{
			temp=a[j];
			for(int k=j-1;k>=i;k--)
			{
				a[k+1]=a[k];
			}
			a[i]=temp;
			i++;
			j++;
		}
		else if(a[i]<a[j])i++;
	}
	
	for(i=0;i<n;i++)cout<<a[i]<<" ";
	cout<<endl;
}

- trojansmith on August 22, 2011 | Flag Reply


Add a Comment
Name:

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

Books

is a comprehensive book walking you through 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