xyz Interview Question
Applications DevelopersTeam: 5
Country: India
Interview Type: Written Test
class MergeArray {
private void heapSort(int[] arr) {
...
}
public int[] mergeIntoSortedArray(int[] arr1, int[] arr2) {
sorting(arr1);
sorting(arr2);
int[] out = new int[arr1.length + arr2.length];
int j = 0;
int k = 0;
int i = 0;
while (j < arr1.length && k < arr2.length) {
if (arr1[j] < arr2[k]) {
out[i++] = arr1[j++];
} else {
out[i++] = arr2[k++];
}
}
while (j < arr1.length) {
out[i++] = arr1[j++];
}
while (k < arr2.length) {
out[i++] = arr2[k++];
}
return out;
}
}
public class MergeTwoArrayIntoSortedArray {
public static void main(String[] args) {
int[] arr1 = new int[] {2,5,8,9};
int[] arr2 = new int[] {6,3,4,7,1};
MergeArray mMergeArray = new MergeArray();
System.out.println("MERGED SORTED ARRAY: "
+ Arrays.toString(mMergeArray.mergeIntoSortedArray(arr1, arr2)));
}
}
public class MergeSort {
public static void main(String[] args) {
int[] array1 = { 2, 5, 8, 9 };
int[] array2 = { 6, 3, 4, 7, 1 };
int[] array3 = new int[array1.length + array2.length];
array3 = getSortedArray(array1, array2, array3);
for (int i = 0; i < array3.length; i++) {
System.out.print(array3[i] + " ");
}
}
private static int[] getSortedArray(int[] array1, int[] array2, int[] array3) {
array2 = sortArray(array2);
array1 = sortArray(array1);
int a1 = 0, a2 = 0, a3 = 0;
while (a1 < array1.length && a2 < array2.length) {
if (array1[a1] < array2[a2]) {
array3[a3] = array1[a1];
a1++;
a3++;
} else {
array3[a3] = array2[a2];
a2++;
a3++;
}
}
while (a1 < array1.length) {
array3[a3] = array1[a1];
a1++;
a3++;
}
while (a2 < array2.length) {
array3[a3] = array2[a2];
a2++;
a3++;
}
return array3;
}
private static int[] sortArray(int[] array) {
for (int i = 0; i < array.length; i++) {
for (int j = 0; j < array.length; j++) {
if (array[i] < array[j]) {
int temp = array[j];
array[j] = array[i];
array[i] = temp;
}
}
}
return array;
}
}
public class MergeSort {
public static void main(String[] args) {
int[] array1 = { 2, 5, 8, 9 };
int[] array2 = { 6, 3, 4, 7, 1 };
int[] array3 = new int[array1.length + array2.length];
array3 = getSortedArray(array1, array2, array3);
for (int i = 0; i < array3.length; i++) {
System.out.print(array3[i] + " ");
}
}
private static int[] getSortedArray(int[] array1, int[] array2, int[] array3) {
array2 = sortArray(array2);
array1 = sortArray(array1);
int a1 = 0, a2 = 0, a3 = 0;
while (a1 < array1.length && a2 < array2.length) {
if (array1[a1] < array2[a2]) {
array3[a3] = array1[a1];
a1++;
a3++;
} else {
array3[a3] = array2[a2];
a2++;
a3++;
}
}
while (a1 < array1.length) {
array3[a3] = array1[a1];
a1++;
a3++;
}
while (a2 < array2.length) {
array3[a3] = array2[a2];
a2++;
a3++;
}
return array3;
}
private static int[] sortArray(int[] array) {
for (int i = 0; i < array.length; i++) {
for (int j = 0; j < array.length; j++) {
if (array[i] < array[j]) {
int temp = array[j];
array[j] = array[i];
array[i] = temp;
}
}
}
return array;
}
}
public static void main(String []args)
{
int a[] = {2,5,8,9};
int b[] = {6,3,4,7,1};
int c[] = new int[a.length+b.length];
//copy both a,b to c
int i=0;
for(int j=0;j<a.length;j++)
c[i++] = a[j];
for(int j=0;j<b.length;j++)
c[i++] = b[j];
//now merge sort
Arrays.sort(c);
System.out.println(Arrays.toString(c));
}
public class MergTwoArrays {
public static void main(String[] args) {
int[] arr1 = {0,2,5,8,9};
int[] arr2 = {6,3,4,7,1,8,12};
arr1 = sortArray(arr1);
for(int x: arr1){
System.out.print(x+",");
}
System.out.println("\n");
arr2 = sortArray(arr2);
for(int x1: arr2){
System.out.print(x1+",");
}
System.out.println("\n");
int[] mergedAndSortedArray = Merg(arr1,arr2);
for(int a : mergedAndSortedArray){
System.out.print(a+",");
}
}
public static int[] Merg(int[] arr1, int[] arr2){
int i=0,ls = 0;
int le = arr1.length-1;
int j=0,rs = 0;
int re = arr2.length-1;
int[] finalArray = new int[arr1.length+arr2.length];
int k=0;
while(i <=le && j<=re){
if(arr1[i]<arr2[j]){
finalArray[k] = arr1[i];
i++;
}else{
finalArray[k] = arr2[j];
j++;
}
k++;
}
while(i<=le){
finalArray[k] = arr1[i];
i++;
}
while(j<=re){
finalArray[k] = arr2[j];
j++;
}
return finalArray;
}
public static int[] sortArray(int[] arr){
for(int k=1;k<arr.length;k++){
int temp = arr[k];
int j = k-1;
while(j>=0 && arr[j]>temp){
arr[j+1] = arr[j];
j--;
}
arr[j+1] = temp;
}
return arr;
}
}
public class MergTwoArrays {
public static void main(String[] args) {
int[] arr1 = {0,2,5,8,9};
int[] arr2 = {6,3,4,7,1,8,12};
arr1 = sortArray(arr1);
for(int x: arr1){
System.out.print(x+",");
}
System.out.println("\n");
arr2 = sortArray(arr2);
for(int x1: arr2){
System.out.print(x1+",");
}
System.out.println("\n");
int[] mergedAndSortedArray = Merg(arr1,arr2);
for(int a : mergedAndSortedArray){
System.out.print(a+",");
}
}
public static int[] Merg(int[] arr1, int[] arr2){
int i=0,ls = 0;
int le = arr1.length-1;
int j=0,rs = 0;
int re = arr2.length-1;
int[] finalArray = new int[arr1.length+arr2.length];
int k=0;
while(i <=le && j<=re){
if(arr1[i]<arr2[j]){
finalArray[k] = arr1[i];
i++;
}else{
finalArray[k] = arr2[j];
j++;
}
k++;
}
while(i<=le){
finalArray[k] = arr1[i];
i++;
}
while(j<=re){
finalArray[k] = arr2[j];
j++;
}
return finalArray;
}
public static int[] sortArray(int[] arr){
for(int k=1;k<arr.length;k++){
int temp = arr[k];
int j = k-1;
while(j>=0 && arr[j]>temp){
arr[j+1] = arr[j];
j--;
}
arr[j+1] = temp;
}
return arr;
}
}
public class MergTwoArrays {
public static void main(String[] args) {
int[] arr1 = {0,2,5,8,9};
int[] arr2 = {6,3,4,7,1,8,12};
arr1 = sortArray(arr1);
for(int x: arr1){
System.out.print(x+",");
}
System.out.println("\n");
arr2 = sortArray(arr2);
for(int x1: arr2){
System.out.print(x1+",");
}
System.out.println("\n");
int[] mergedAndSortedArray = Merg(arr1,arr2);
for(int a : mergedAndSortedArray){
System.out.print(a+",");
}
}
public static int[] Merg(int[] arr1, int[] arr2){
int i=0,ls = 0;
int le = arr1.length-1;
int j=0,rs = 0;
int re = arr2.length-1;
int[] finalArray = new int[arr1.length+arr2.length];
int k=0;
while(i <=le && j<=re){
if(arr1[i]<arr2[j]){
finalArray[k] = arr1[i];
i++;
}else{
finalArray[k] = arr2[j];
j++;
}
k++;
}
while(i<=le){
finalArray[k] = arr1[i];
i++;
}
while(j<=re){
finalArray[k] = arr2[j];
j++;
}
return finalArray;
}
public static int[] sortArray(int[] arr){
for(int k=1;k<arr.length;k++){
int temp = arr[k];
int j = k-1;
while(j>=0 && arr[j]>temp){
arr[j+1] = arr[j];
j--;
}
arr[j+1] = temp;
}
return arr;
}
import java.util.HashMap;
public class MergeTwoArra {
public static void main(String[] args) {
// TODO Auto-generated method stub
int a[] = {2,5,8,9};
int b[] = {6,3,4,7,1};
int c[] = new int[a.length + b.length];
int i =0;
HashMap<Integer,Integer> int_map = new HashMap<Integer,Integer>();
int map_size = a.length;
map_size += b.length;
int value=0;
for(i=0;i<a.length;i++)
{
value = int_map.getOrDefault(a[i], 0);
int_map.put(a[i], ++value);
value = 0;
}
for(i=0;i<b.length;i++)
{
value = int_map.getOrDefault(b[i], 0);
int_map.put(b[i], ++value);
value=0;
}
int count= 0;
for(i=0;i<=map_size;i++)
{
value = int_map.getOrDefault(i, 0);
if (value > 0)
{
for(int j=0;j<value;j++)
{
c[count++] = i;
}
}
}
}
}
private static void arrayMerging() {
int a[]={1,3,4,5,6};
int b[]={7,8,9,10,11};
int c[]=new int[a.length+b.length];
System.arraycopy(a, 0, c, 0, a.length);
System.arraycopy(b, 0, c, a.length, b.length);
Arrays.sort(c);
try{
for(int i=0;i<c.length;i++){
System.out.print(c[i]+" ");
}
}catch (Exception e) {
e.printStackTrace();
}
}
private static void arrayMerging() {
int a[]={1,3,4,5,6};
int b[]={7,8,9,10,11};
int c[]=new int[a.length+b.length];
System.arraycopy(a, 0, c, 0, a.length);
System.arraycopy(b, 0, c, a.length, b.length);
Arrays.sort(c);
try{
for(int i=0;i<c.length;i++){
System.out.print(c[i]+" ");
}
}catch (Exception e) {
e.printStackTrace();
}
}
There is a sorting algorithm called external merge sort that can help you with this. Essentially in the beginning you sort the two smaller arrays using something like quicksort, so you have 1 = {2,5,8,9} and 2= {1,3,4,6,7}. Then you check the first element of both arrays, and put the smaller in the third array: min(1[0], 2[0]), so now you have 3 = {1}. Then you "advance" to the second element in the array that you used, and now compare the second element of that array and the first element of the other array, so you check min(1[0], 2[1]). So now array 3 looks like 3 = {1,2}.
- cemkadioglu91 April 03, 2015