Solved

mergeTwo  challenge

Posted on 2016-08-30
13
71 Views
Last Modified: 2016-09-09
Hi,
i am working one below challenge
http://codingbat.com/prob/p139150

i was not clear on below description


Start with two arrays of strings, A and B, each with its elements in alphabetical order and without duplicates. Return a new array containing the first N elements from the two arrays. The result array should be in alphabetical order and without duplicates. A and B will both have a length which is N or more. The best "linear" solution makes a single pass over A and B, taking advantage of the fact that they are in alphabetical order, copying elements directly to the new array.

how below results are 40 each? please advise
mergeTwo(["a", "c", "z"], ["b", "f", "z"], 3) → ["a", "b", "c"]//i expected output  ["a", "c", "z"."b", "f", "z]??
mergeTwo(["a", "c", "z"], ["c", "f", "z"], 3) → ["a", "c", "f"]
mergeTwo(["f", "g", "z"], ["c", "f", "g"], 3) → ["c", "f", "g"]
0
Comment
Question by:gudii9
13 Comments
 
LVL 28

Expert Comment

by:Bill Bach
Comment Utility
You are missing this note: containing the first N elements from the two arrays.  Note that there is a third parameter to the function call, which is 3 in each case.  Therefore, you will only be returning an array of size 3, and NOT the culmination of both arrays.  This is the first reason why your "expected output" is wrong -- there should only be 3 elements returned.

The second reason your "expected output" is wrong is because you are not returning the array in alphabetical order, which was also clearly indicated in the specs.
0
 
LVL 7

Author Comment

by:gudii9
Comment Utility
You are missing this note: containing the first N elements from the two arrays.  Note that there is a third parameter to the function call, which is 3 in each case.  Therefore, you will only be returning an array of size 3, and NOT the culmination of both arrays.  This is the first reason why your "expected output" is wrong -- there should only be 3 elements returned.

The second reason your "expected output" is wrong is because you are not returning the array in alphabetical order, which was also clearly indicated in the specs.

i got meaning now. let me think psuedo code and code?
0
 
LVL 84

Assisted Solution

by:ozo
ozo earned 250 total points
Comment Utility
public String[] mergeTwo(String[] a, String[] b, int n) {
  String[] c= new String[n];
  int ax=0; int bx=0; int cx=0;
  for( cx=0;cx<n;){
    int d=a[ax].compareTo(b[bx]);
    c[cx++] = d<0?a[ax++]:d>0?b[bx++]:a[bx++*0+ax++];
  }
  return c;
}
0
 
LVL 37

Accepted Solution

by:
zzynx earned 250 total points
Comment Utility
@ozo, it's probably correct working code, but way too 'obscure' for gudii9 I'm afraid.
@gudii9, here's a better human readable version:

public String[] mergeTwo(String[] a, String[] b, int n) {
  String[] c= new String[n];
  int aIndex=0, bIndex=0, cIndex=0;
  for( cIndex=0; cIndex<n; cIndex++) {
      int compareResult = a[aIndex].compareTo(b[bIndex]); // compare an element of array a with one of array b
      if (compareResult == 0) { // The elements are equal
          c[cIndex] = a[aIndex]; // add it to the result array c
          aIndex++; // increment the "working index" of both arrays
          bIndex++;
      } else if (compareResult < 0) { // The element of array a comes alphabetically before the one in array b
          c[cIndex] = a[aIndex]; // add the smallest to the result array c
          aIndex++; // increment the working index of array a
      } else if (compareResult > 0) {  // The element of array b comes alphabetically before the one in array a
          c[cIndex] = b[bIndex]; // add the smallest to the result array c
          bIndex++; // increment the working index of array b
      }
  }
  return c;  // return the result array
} 

Open in new window

0
 
LVL 7

Author Comment

by:gudii9
Comment Utility
this is quite a bit of code to digest
0
 
LVL 7

Author Comment

by:gudii9
Comment Utility
any other simple approach?
0
How your wiki can always stay up-to-date

Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
- Increase transparency
- Onboard new hires faster
- Access from mobile/offline

 
LVL 37

Expert Comment

by:zzynx
Comment Utility
any other simple approach?
You can't tell a story in one sentence.
0
 
LVL 7

Author Comment

by:gudii9
Comment Utility
public String[] mergeTwo(String[] a, String[] b, int n) {
  String[] c= new String[n];
  int aIndex=0, bIndex=0, cIndex=0;
  for( cIndex=0; cIndex<n; cIndex++) {
      int compareResult = a[aIndex].compareTo(b[bIndex]); // compare an element of array a with one of array b
      if (compareResult == 0) { // The elements are equal
          c[cIndex] = b[bIndex]; // add it to the result array c
          aIndex++; // increment the "working index" of both arrays
          bIndex++;
      } else if (compareResult < 0) { // The element of array a comes alphabetically before the one in array b
          c[cIndex] = a[aIndex]; // add the smallest to the result array c
          aIndex++; // increment the working index of array a
      } else if (compareResult > 0) {  // The element of array b comes alphabetically before the one in array a
          c[cIndex] = b[bIndex]; // add the smallest to the result array c
          bIndex++; // increment the working index of array b
      }
  }
  return c;  // return the result array
} 

Open in new window


if both equal i can say as below right which passes all tests

  c[cIndex] = b[bIndex]; // add it to the result array c

instead of
  c[cIndex] = a[aIndex]; // add it to the result array c
0
 
LVL 7

Author Comment

by:gudii9
Comment Utility
public class Test {

   public static void main(String args[]) {
      String str1 = "Strings are immutable";
	  String str2 = "Strings are immutable";
      String str3 = "Integers are not immutable";

      int result = str1.compareTo( str2 );
      System.out.println(result);
	  
      result = str2.compareTo( str3 );
      System.out.println(result);
	 
      result = str3.compareTo( str1 );
      System.out.println(result);
   }
}
This produces the following result:

0
10
-10

Open in new window

we are basically looping to fill array C by giving n as it size and going less than n

 for( cIndex=0; cIndex<n; cIndex++) {


then we are checking below

 int compareResult = a[aIndex].compareTo(b[bIndex]); // compare an element of array a with one of array b
      if (compareResult == 0) { // The elements are equal
fill c with either a or b element as both same increment a and b

else if   if (compareResult < 0) {
fill C with 'a' element as 'a' is less than 'b' and increment a as that is already filled


else  if (compareResult > 0) {
fill C with b element as 'a' is greater than 'b' and increment b as that is already filled
0
 
LVL 7

Author Comment

by:gudii9
Comment Utility
public String[] mergeTwo(String[] a, String[] b, int n) {
  
  String[] c=new String[n];
  int aIndex=0,bIndex=0,cIndex=0;
  int compareVal=a[aIndex].compareTo(b[bIndex]);
  for(cIndex=0;cIndex<n;cIndex++){
    
    if(compareVal==0){
      c[cIndex]=a[aIndex];
      aIndex++;
      bIndex++;
    }
    
     else if(compareVal<0){
     // c(cIndex[i])=a(aIndex[i]);
      c[cIndex]=a[aIndex];
      aIndex++;
      //bIndex++;
    }
    
     else if(compareVal>0){
      //c(cIndex[i])=b(bIndex[i]);
      //aIndex++;
       c[cIndex]=b[bIndex];
      bIndex++;
    }
  }
  return c;
} 

Open in new window


when i tried as above failing below tests
Expected      Run            
mergeTwo(["a", "c", "z"], ["b", "f", "z"], 3) → ["a", "b", "c"]      ["a", "c", "z"]      X      
mergeTwo(["a", "c", "z"], ["c", "f", "z"], 3) → ["a", "c", "f"]      ["a", "c", "z"]      X      
mergeTwo(["f", "g", "z"], ["c", "f", "g"], 3) → ["c", "f", "g"]      ["c", "f", "g"]      OK      
mergeTwo(["a", "c", "z"], ["a", "c", "z"], 3) → ["a", "c", "z"]      ["a", "c", "z"]      OK      
mergeTwo(["a", "b", "c", "z"], ["a", "c", "z"], 3) → ["a", "b", "c"]      ["a", "b", "c"]      OK      
mergeTwo(["a", "c", "z"], ["a", "b", "c", "z"], 3) → ["a", "b", "c"]      ["a", "c", "z"]      X      
mergeTwo(["a", "c", "z"], ["a", "c", "z"], 2) → ["a", "c"]      ["a", "c"]      OK      
mergeTwo(["a", "c", "z"], ["a", "c", "y", "z"], 3) → ["a", "c", "y"]      ["a", "c", "z"]      X      
mergeTwo(["x", "y", "z"], ["a", "b", "z"], 3) → ["a", "b", "x"]      ["a", "b", "z"]      X      
other tests
X      
please advise
0
 
LVL 7

Author Comment

by:gudii9
Comment Utility
package com.solution;

import java.util.Arrays;

public class MergeTwo {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		String[] a={"a", "c", "z"};
		String[] b={"b", "f", "z"};
		System.out.println("is--->"+Arrays.toString(mergeTwo(a,b,3)));

	}
	
	public static String[] mergeTwo(String[] a, String[] b, int n) {
		  
		  String[] c=new String[n];
		  int aIndex=0,bIndex=0,cIndex=0;
		  int compareVal=a[aIndex].compareTo(b[bIndex]);
		  for(cIndex=0;cIndex<n;cIndex++){
		    
		    if(compareVal==0){
		      c[cIndex]=a[aIndex];
		      aIndex++;
		      bIndex++;
		    }
		    
		     else if(compareVal<0){
		     // c(cIndex[i])=a(aIndex[i]);
		      c[cIndex]=a[aIndex];
		      aIndex++;
		      //bIndex++;
		    }
		    
		     else if(compareVal>0){
		      //c(cIndex[i])=b(bIndex[i]);
		      //aIndex++;
		       c[cIndex]=b[bIndex];
		      bIndex++;
		    }
		  }
		  return c;
		} 

}

Open in new window


above give wrong output as below

is--->[a, c, z]
please advise
0
 
LVL 7

Author Comment

by:gudii9
Comment Utility
i see i made a mistake. i have to open beyondcompare to compare working and not working code. compareVal(compareResult) i put outside for loop which is resulting -1 all the time. i fixed and passing all tests now
public String[] mergeTwo(String[] a, String[] b, int n) {
  
  String[] c=new String[n];
  int aIndex=0,bIndex=0,cIndex=0;
 
  for(cIndex=0;cIndex<n;cIndex++){
     int compareVal=a[aIndex].compareTo(b[bIndex]);
    if(compareVal==0){
      c[cIndex]=a[aIndex];
      aIndex++;
      bIndex++;
    }
    
     else if(compareVal<0){
     // c(cIndex[i])=a(aIndex[i]);
      c[cIndex]=a[aIndex];
      aIndex++;
      //bIndex++;
    }
    
     else if(compareVal>0){
      //c(cIndex[i])=b(bIndex[i]);
      //aIndex++;
       c[cIndex]=b[bIndex];
      bIndex++;
    }
  }
  return c;
} 

Open in new window

0
 
LVL 7

Author Comment

by:gudii9
Comment Utility
package com.solution;

import java.util.Arrays;

public class MergeTwo {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		String[] a={"a", "c", "z"};
		String[] b={"b", "f", "z"};
		System.out.println("is--->"+Arrays.toString(mergeTwo(a,b,3)));

	}
	
	public static String[] mergeTwo(String[] a, String[] b, int n) {
		  
		  String[] c=new String[n];
		  int aIndex=0,bIndex=0,cIndex=0;
		  int compareVal=a[aIndex].compareTo(b[bIndex]);//c.compareTo(b)===>i thought 1 but coming -1
		  
		  
		  for(cIndex=0;cIndex<n;cIndex++){
			  System.out.println("compareVal is====>"+compareVal);
		    if(compareVal==0){
		      c[cIndex]=a[aIndex];
		      aIndex++;
		      bIndex++;
		    }
		    
		     else if(compareVal<0){
		     // c(cIndex[i])=a(aIndex[i]);
		      c[cIndex]=a[aIndex];
		      aIndex++;
		      //bIndex++;
		    }
		    
		     else if(compareVal>0){
		      //c(cIndex[i])=b(bIndex[i]);
		      //aIndex++;
		       c[cIndex]=b[bIndex];
		      bIndex++;
		    }
		  }
		  return c;
		} 

}

Open in new window


above is misplaced code resulting same -1

compareVal is====>-1
compareVal is====>-1
compareVal is====>-1
is--->[a, c, z]

as index values not updating keep on printing a only
0

Featured Post

Threat Intelligence Starter Resources

Integrating threat intelligence can be challenging, and not all companies are ready. These resources can help you build awareness and prepare for defense.

Join & Write a Comment

A short article about problems I had with the new location API and permissions in Marshmallow
Basic understanding on "OO- Object Orientation" is needed for designing a logical solution to solve a problem. Basic OOAD is a prerequisite for a coder to ensure that they follow the basic design of OO. This would help developers to understand the b…
Viewers will learn about the regular for loop in Java and how to use it. Definition: Break the for loop down into 3 parts: Syntax when using for loops: Example using a for loop:
This tutorial will introduce the viewer to VisualVM for the Java platform application. This video explains an example program and covers the Overview, Monitor, and Heap Dump tabs.

772 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

9 Experts available now in Live!

Get 1:1 Help Now