United HealthGroup Interview Question Java Developers
Country: India
Interview Type: Phone Interview
When you sort the keys (list) and loop on that. You get the sorted order. Thus a sorted output
(1) sort the array with say quick sort -- nlogn
(2) get the max -- the element at the end of the sorted array o(1)
(3) scan the array , comparing each element to it previous - if duplicate - add to it max 0(n)
(4) sort the array again nlogn
(5) Scan the array again - after you pass the max element, subtract max from each element o(n)
Total cost = nlogn + 1 + n + nlogn + n
= 2nlogn + 2n
= (n+1)logn
The problem cant be done in less than nlgn because we need to use comparision sorting at one time or another
1.Sort inplace using quicksort taken nlgn time
2.set a pointer to last element of the array, now scan the array each time we get a duplicate, swap it with the pointer and move the pointer backwards, stop the scan when the value of swapped variable is greater than next variable, save this location as pivot
this takes n time
3.quicksort 0, pivot-1 and pivot-1 size this will give final output, this takes nlgn time
therefore total time is O(nlgn)
code for algo
import java.util.*;
import java.io.*;
public class Dup_sort{
public static int partition(int left, int right, int array[]){
int i = left-1;
int pivot = array[right];
for(int j = left;j<right;j++){
if(array[j] < pivot){
i++;
swap(i, j, array);
}
}
i++;
swap(i, right, array);
return i;
}
public static void swap(int i, int j, int array[]){
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
public static void quickSort(int left, int right, int array[]){
if(left >= right){
return;
}
if(left == right -1){
if(array[left] > array[right]){
swap(left, right, array);
}
return;
}
int pivot = partition(left, right, array);
quickSort(left, pivot-1, array);
quickSort(pivot+1, right, array);
}
public static int moveDuplicates(int array[], int size){
int right = size-1;
for(int i = 0;i<size-1;i++){
if(right <= i){
return right;
}
if(array[i] == array[i+1]){
swap(i, right, array);
right--;
}
}
return right;
}
public static void main(String args[]){
int array[];
int size;
Scanner scanner = new Scanner(System.in);
try{
size = scanner.nextInt();
array = new int[size];
for(int i = 0;i<size;i++){
array[i] = scanner.nextInt();
}
quickSort(0, size-1, array);
int pivot = moveDuplicates(array, size);
quickSort(0, pivot, array);
quickSort(pivot, size-1, array);
for(int i = 0;i<size;i++){
System.out.print(array[i] + " ");
}
System.out.println();
}catch(Exception e){
e.printStackTrace();
}
}
}
1. Let us say input array, { 2,9,1,5,1,4,9,7,2,1,4 }
2. Sort the array, { 1,1,1,2,2,4,4,5,7,9,9 }
3. Scan the sorted_array, to count no. of items having one or more repetitions, two or more repetitions ...
4. This total array is { 6, 4, 1, 0, ... }. It means 6 items (1,2,4,5,7,9) have one or more repetitions, 4 items (1,2,4,9) have two or more repetitions, ....
5. Create a commulative_index from total array, {0,6,10,11,11,11...)
target[0] = sorted_array[0];
commulative_index[0]++;
group=0;
for i = 1 to n-1
if( sorted_array[i] != sorted_array[i-1] )
group=0;
else
group++;
target[commulative_index[group]]=sorted_array[i];
Time Complexity: nlogn (sorting) + n (scan) + n (create commulative_index) + n (store in target)
= nlogn
Space Complexity: n (total) + n (commulative_index) + n (target) = 3n
void sortDuplicates( int a[], int n )
{
sort( a, a + n );
// create total array
int *total = new int[n+1];
int index = 1;
total[0] = 0;
total[1] = 1;
for( int i = 1; i < n; i++ )
{
total[i+1] = 0;
index = ( a[i] == a[i-1] ) ? index + 1 : 1;
total[ index ]++;
}
// create commulative_index
int *commulative_index = new int[n+1];
commulative_index[0] = 0;
for( int i = 1; i < n; i++ )
commulative_index[i] = commulative_index[i-1] + total[i];
int *target = new int[n];
target[0] = a[0];
commulative_index[0]++;
int group=0;
for( int i = 1; i < n; i++ )
{
if( a[i] != a[i-1] )
group=0;
else
group++;
target[commulative_index[group]++]=a[i];
}
for( int i = 0; i < n; i++ )
cout << target[i] << " ";
free( target );
free( commulative_index );
free( total );
}
public void sort(int[] A)
{
if(A.length ==0 ) return ;
quicksort(ref A,0,A.length-1); // nlogn for first sort
int S=0 ; int E=A.legth-1;
while(E!=0)
{
int i=S;
i++;
while(i<=E) // O(n) pass for shifting element that are duplicate to segement the array
{
if(A[i-1]==A[i])
{
int tmp = A[i-1];
A[i-1]= A[S];
A[S]== tmp;
S++;
}
}
Quicksort(ref A, S+1,E); // ksegement log k
E=S;
S=0;
}
}
Tried it without recursion, but complexity is still worst.
static void sortDuplicate(int a[])
{
Arrays.sort(a);
int n = a.length;
int temp,j;
for(int i = 1; i < n; i++)
{
if(a[i] == a[i-1])
{
temp = a[i];
for( j = i; j<n-1; j++)
{
a[j]= a[j+1];
}
a[j] = temp;
i--;
}
}
System.out.println("Sorted array:" + Arrays.toString(a));
}
public class SortDuplicates {
/**
* @param args
*/
public static void main(String[] args) {
Integer arr[]= { 2,9,1,5,1,4,9,7,2,1,4 };
ArrayList<Integer> numberList = new ArrayList<Integer>(Arrays.asList(arr));
Set<Integer> numberSet = new TreeSet<Integer>(numberList);
for (Integer i : numberSet) {
numberList.remove(i); // Remove the first instance of unique number from the list
}
for (Integer i : numberSet) {
System.out.print(i + ", ");
}
for (Integer i : numberList) {
System.out.print(i + ", ");
}
System.out.println("");
}
}
public class SortDuplicates {
/**
* @param args
*/
public static void main(String[] args) {
Integer arr[]= { 2,9,1,5,1,4,9,7,2,1,4 };
ArrayList<Integer> numberList = new ArrayList<Integer>(Arrays.asList(arr));
Set<Integer> numberSet = new TreeSet<Integer>(numberList);
for (Integer i : numberSet) {
numberList.remove(i); // Remove the first instance of unique number from the list
}
for (Integer i : numberSet) {
System.out.print(i + ", ");
}
for (Integer i : numberList) {
System.out.print(i + ", ");
}
System.out.println("");
}
}
Forgot to sort the duplicate numbers in previous two posts. This should print the results as below.
1, 2, 4, 5, 7, 9, 1, 1, 2, 4, 9,
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Set;
import java.util.TreeSet;
public class SortDuplicates {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
Integer arr[]= { 2,9,1,5,1,4,9,7,2,1,4 };
ArrayList<Integer> numberList = new ArrayList<Integer>(Arrays.asList(arr));
Set<Integer> numberSet = new TreeSet<Integer>(numberList);
for (Integer i : numberSet) {
numberList.remove(i); // Remove the first duplicate instance from the list
}
// Print the unique numbers naturally sorted by TreeSet
for (Integer i : numberSet) {
System.out.print(i + ", ");
}
// Now sort rest of the duplicate items in the list before printing
Collections.sort(numberList);
for (Integer i : numberList) {
System.out.print(i + ", ");
}
System.out.println("");
}
0. Sort the array. This will have complexity O(nlgn)
1. Then starting from the beginning of the array, count the total number of repetitions of all the elements. For ex: in the sorted array [1 1 1 2 2 3 3 3 3], the total number of repetitions would be 6 (2 1s, 1 2s, 3 3s). Set it to a variable called repetition_count, so repetition_count = 6.
3. Start two pointers, one at the end at n-1 and the other at the middle at n-repetition_count+1
4. Swap the values of the end and the middle pointer and decrement them both
5. if the end pointer has the same value as the one before one decrementing it, keep decrementing the end pointer until a new element is encountered
6. Repeat steps 4 & 5 until the end pointer gets to the index: n-repetition_count+1
Steps 3 to 6 in action below:
[1 1 1 2 2 3 3 3 3] swap and decrement both the pointers
^ ^
[1 1 3 2 2 3 3 3 1] decrement the end pointer
^ ^
[1 1 3 2 2 3 3 3 1] decrement the end pointer
^ ^
[1 1 3 2 2 3 3 3 1] decrement the end pointer
^ ^
[1 1 3 2 2 3 3 3 1] swap and decrement both the pointers
^ ^
[1 2 3 2 1 3 3 3 1] decrement the end pointer
^ ^
[1 2 3 2 1 3 3 3 1] stop
^ ^
Another alternative is to use modified merge sort. The merge procedure needs to be modified so when a duplicate is returned, it is pushed towards the end of the array. This way the merge procedure produces an array which is sorted in the first part and has repetitions in the second part. The index delimiting the sorted part with the unsorted part would be returned by the merge procedure to it's caller.
Merge sort requires O(n) extra space, so this procedure can be used if space is not at a premium.
1) Find min and max value in the array
2) Count the number of occurrence for each value in array. Keep result in a separate array say count[max-min+1]
3) Recreate the original array by traversing the 'count' array and each time decrements the count for particular value till all elements are equal 0.
Code:
public static void main(String[] args) {
int arr[] = { 2, 9, 1, 5, 1, 4, 9, 7, 2, 1, 4 };
int min = arr[0];
int max = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
} else if (arr[i] < min) {
min = arr[i];
}
}
int[] count = new int[max - min + 1];
for (int i = 0; i < arr.length; i++) {
count[arr[i] - min]++;
}
int i = 0;
while (i < arr.length) {
for (int j = 0; j < count.length; j++) {
if (count[j] > 0) {
arr[i++] = j + min;
count[j]--;
}
}
}
System.out.println(Arrays.toString(arr));
}
Time O(n), Space O(n)
If additional space is allowed,
- Cloudster August 15, 2013Assume input array is arr[]
1) Build a hashmap H of all elements in arr[] and their count .. O(N).
2) keep i=0, j=keys().length (number of keys).
3) Sort the keys() in the map and loop through all keys.
4) arr[i] = key; i++
4) for j=1 to H[key]: arr[j]=key; j++