linearIn challenge

Hi,

I am working on below challenge

Array-3 > linearIn
prev  |  next  |  chance
Given two arrays of ints sorted in increasing order, outer and inner, return true if all of the numbers in inner appear in outer. The best solution makes only a single "linear" pass of both arrays, taking advantage of the fact that both arrays are already in sorted order.

linearIn([1, 2, 4, 6], [2, 4]) → true
linearIn([1, 2, 4, 6], [2, 3, 4]) → false
linearIn([1, 2, 4, 4, 6], [2, 4]) → true

how to verify one array has one other target array or not? is there is built in method for that?
please advise
LVL 7
gudii9Asked:
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

Gerwin Jansen, EE MVETopic Advisor Commented:
The arrays are sorted - you just go over them and compare the numbers.
0
gudii9Author Commented:
i will try. so two for loops needed right for each array?
0
Gerwin Jansen, EE MVETopic Advisor Commented:
Yes
0
Ultimate Tool Kit for Technology Solution Provider

Broken down into practical pointers and step-by-step instructions, the IT Service Excellence Tool Kit delivers expert advice for technology solution providers. Get your free copy now.

gudii9Author Commented:
0
gudii9Author Commented:
psedo code

1. convert inner array to list
2. convert outer array to list
3. check whether outer contains inner list.
4. if yes return true
5.if false return false

public boolean linearIn(int[] outer, int[] inner) {
  List o=Arrays.asList(outer);
    List i=Arrays.asList(inner);
    if(o.contains(i)){
      return true;
    }
    else return false;
}

Open in new window


\i tried as above failing some tests. please advise
Expected      Run            
linearIn([1, 2, 4, 6], [2, 4]) → true      false      X      
linearIn([1, 2, 4, 6], [2, 3, 4]) → false      false      OK      
linearIn([1, 2, 4, 4, 6], [2, 4]) → true      false      X      
linearIn([2, 2, 4, 4, 6, 6], [2, 4]) → true      false      X      
linearIn([2, 2, 2, 2, 2], [2, 2]) → true      false      X      
linearIn([2, 2, 2, 2, 2], [2, 4]) → false      false      OK      
linearIn([2, 2, 2, 2, 4], [2, 4]) → true      false      X      
linearIn([1, 2, 3], [2]) → true      false      X      
linearIn([1, 2, 3], [-1]) → false      false      OK      
linearIn([1, 2, 3], []) → true      false      X      
linearIn([-1, 0, 3, 3, 3, 10, 12], [-1, 0, 3, 12]) → true      false      X      
linearIn([-1, 0, 3, 3, 3, 10, 12], [0, 3, 12, 14]) → false      false      OK      
linearIn([-1, 0, 3, 3, 3, 10, 12], [-1, 10, 11]) → false      false      OK      
other tests
X      
Your progress graph for this problem
0
gudii9Author Commented:
import java.util.Arrays;
import java.util.List;

public class LinearIn {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] outer = { 1, 2, 4, 6 };
		int[] inner = { 2, 4 };
		System.out.println("is-->" + linearIn(outer, inner));
	}

	public static boolean linearIn(int[] outer, int[] inner) {
		List o = Arrays.asList(outer);
		List i = Arrays.asList(inner);
		if (o.containsAll(i)) {
			return true;
		} else
			return false;
	}

}

Open in new window

is-->false

changed contains to containsAll still getting false instead of true
0
Gerwin Jansen, EE MVETopic Advisor Commented:
I would just start with the shortest array and try to find values in the longest array, increase indexes as needed. When you reach the end you have either true or false.
0

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
gudii9Author Commented:
public boolean linearIn(int[] outer, int[] inner) {
		int match=0;
		int x=0;
		if(inner.length==0){
			return true;
		}
		
		 for (int i = 0; i < outer.length; i++) {
			 
			 
			 if(outer[i]==inner[x]){
				 match++;
				 x++;
			 }
			 else if(outer[i]>inner[x]){
				 return false;
			 }
			 else if(outer[i]< inner[x]){
				 return false;
			 }
			 if(match==inner.length){
				 return true;
			 }
			
		}
		 return false;
		}

Open in new window

Expected      Run            
linearIn([1, 2, 4, 6], [2, 4]) → true      false      X      
linearIn([1, 2, 4, 6], [2, 3, 4]) → false      false      OK      
linearIn([1, 2, 4, 4, 6], [2, 4]) → true      false      X      
linearIn([2, 2, 4, 4, 6, 6], [2, 4]) → true      false      X      
linearIn([2, 2, 2, 2, 2], [2, 2]) → true      true      OK      
linearIn([2, 2, 2, 2, 2], [2, 4]) → false      false      OK      
linearIn([2, 2, 2, 2, 4], [2, 4]) → true      false      X      
linearIn([1, 2, 3], [2]) → true      false      X      
linearIn([1, 2, 3], [-1]) → false      false      OK      
linearIn([1, 2, 3], []) → true      true      OK      
linearIn([-1, 0, 3, 3, 3, 10, 12], [-1, 0, 3, 12]) → true      false      X      
linearIn([-1, 0, 3, 3, 3, 10, 12], [0, 3, 12, 14]) → false      false      OK      
linearIn([-1, 0, 3, 3, 3, 10, 12], [-1, 10, 11]) → false      false      OK      
other tests
X
tried as above failing some tests. please advise

package com.upcast;

public class LinearIn {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] outer={1,2,4,6};
		int[] inner={2,4};
		System.out.println("linearIn is===>"+linearIn(outer,inner));

	}
	public static boolean linearIn(int[] outer, int[] inner) {
		int match=0;
		int x=0;
		if(inner.length==0){
			return true;
		}
		
		 for (int i = 0; i < outer.length; i++) {
			 
			 
			 if(outer[i]==inner[x]){
				 match++;
				 x++;
			 }
			 else if(outer[i]>inner[x]){
				 return false;
			 }
			 else if(outer[i]< inner[x]){
				 return false;
			 }
			 if(match==inner.length){
				 return true;
			 }
			
		}
		 return false;
		}

}

Open in new window

linearIn is===>false
0
rrzCommented:
You should take Gerwin Jansen advice in his last comment above here.
I would just start with the shortest array ...
 Also debug statements would help here too.
0
gudii9Author Commented:
public boolean linearIn(int[] outer, int[] inner) {
		int match=0;
		int x=0;
		if(inner.length==0){
			return true;
		}
		
		 for (int i = 0; i < outer.length; i++) {
			 
			 
			 if(outer[i]==inner[x]){
				 match++;
				 x++;
			 }
			 else if(outer[i]>inner[x]){
				 return false;
			 }
			/* else if(outer[i]< inner[x]){
				 return false;
			 }*/
			 if(match==inner.length){
				 return true;
			 }
			
		}
		 return false;
		}

Open in new window


Expected      Run            
linearIn([1, 2, 4, 6], [2, 4]) → true      true      OK      
linearIn([1, 2, 4, 6], [2, 3, 4]) → false      false      OK      
linearIn([1, 2, 4, 4, 6], [2, 4]) → true      true      OK      
linearIn([2, 2, 4, 4, 6, 6], [2, 4]) → true      true      OK      
linearIn([2, 2, 2, 2, 2], [2, 2]) → true      true      OK      
linearIn([2, 2, 2, 2, 2], [2, 4]) → false      false      OK      
linearIn([2, 2, 2, 2, 4], [2, 4]) → true      true      OK      
linearIn([1, 2, 3], [2]) → true      true      OK      
linearIn([1, 2, 3], [-1]) → false      false      OK      
linearIn([1, 2, 3], []) → true      true      OK      
linearIn([-1, 0, 3, 3, 3, 10, 12], [-1, 0, 3, 12]) → true      true      OK      
linearIn([-1, 0, 3, 3, 3, 10, 12], [0, 3, 12, 14]) → false      false      OK      
linearIn([-1, 0, 3, 3, 3, 10, 12], [-1, 10, 11]) → false      false      OK      
other tests
OK      
package com.upcast;

public class LinearIn {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] outer={1,2,4,6};
		int[] inner={2,4};
		System.out.println("linearIn is===>"+linearIn(outer,inner));

	}
	public static boolean linearIn(int[] outer, int[] inner) {
		int match=0;
		int x=0;
		if(inner.length==0){
			return true;
		}
		
		 for (int i = 0; i < outer.length; i++) {
			 
			 
			 if(outer[i]==inner[x]){
				 match++;
				 x++;
			 }
			 else if(outer[i]>inner[x]){
				 return false;
			 }
			/* else if(outer[i]< inner[x]){
				 return false;
			 }*/
			 if(match==inner.length){
				 return true;
			 }
			
		}
		 return false;
		}

}

Open in new window

linearIn is===>true

Open in new window

when i comment last else if it passes all tests.

Not clear how and why?
0
rrzCommented:
Not clear how and why?
What was the purpose of
29:			/* else if(outer[i]< inner[x]){
30:				 return false;
31:			 }*/

Open in new window

Please tell us what you were thinking when you wrote that .  
Anyway, your code looks good.  Here is mine.
public boolean linearIn(int[] outer, int[] inner) {
    boolean found = false;
    int j = 0;
    for(int i = 0; i < inner.length; i++){
        for(int k = j; k < outer.length; k++){
          if(inner[i] == outer[k]){
            j = k;
            found = true;
            break;
          } 
        }
        if(!found)return false;
        found = false;
    }
   return true;
}

Open in new window

I don't know which is better.
0
gudii9Author Commented:
i was thinking there are 3 cases always right when comparing
1. equals
2. greater
3. less than
0
rrzCommented:
We search for when values match.
Why do you care if the values are greater or less than?
0
gudii9Author Commented:
public boolean linearIn(int[] outer, int[] inner) {
		int match=0;
		int x=0;
		if(inner.length==0){
			return true;
		}
		
		 for (int i = 0; i < outer.length; i++) {
			 
			 
			 if(outer[i]==inner[x]){
				 match++;
				 x++;
			 }
			 /*else if(outer[i]>inner[x]){
				 return false;
			 }*/
			/* else if(outer[i]< inner[x]){
				 return false;
			 }*/
			 if(match==inner.length){
				 return true;
			 }
			
		}
		 return false;
		}

Open in new window


actually i could comment other else if still fine as i need to worry only about == case

public boolean linearIn(int[] outer, int[] inner) {
		int match=0;
		int x=0;
		if(inner.length==0){
			return true;
		}
		
		 for (int i = 0; i < outer.length; i++) {
			 
			 
			 if(outer[i]==inner[x]){
				 match++;
				 x++;
			 }
			 /*else if(outer[i]>inner[x]){
				 return false;
			 }*/
			/* else if(outer[i]< inner[x]){
				 return false;
			 }*/
			 if(match==inner.length){
				 return true;
			 }
			
		}
		 return false;
		}

Open in new window

Expected      Run            
linearIn([1, 2, 4, 6], [2, 4]) → true      true      OK      
linearIn([1, 2, 4, 6], [2, 3, 4]) → false      false      OK      
linearIn([1, 2, 4, 4, 6], [2, 4]) → true      true      OK      
linearIn([2, 2, 4, 4, 6, 6], [2, 4]) → true      true      OK      
linearIn([2, 2, 2, 2, 2], [2, 2]) → true      true      OK      
linearIn([2, 2, 2, 2, 2], [2, 4]) → false      false      OK      
linearIn([2, 2, 2, 2, 4], [2, 4]) → true      true      OK      
linearIn([1, 2, 3], [2]) → true      true      OK      
linearIn([1, 2, 3], [-1]) → false      false      OK      
linearIn([1, 2, 3], []) → true      true      OK      
linearIn([-1, 0, 3, 3, 3, 10, 12], [-1, 0, 3, 12]) → true      true      OK      
linearIn([-1, 0, 3, 3, 3, 10, 12], [0, 3, 12, 14]) → false      false      OK      
linearIn([-1, 0, 3, 3, 3, 10, 12], [-1, 10, 11]) → false      false      OK      
other tests
OK      
package com.upcast;

public class LinearIn {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] outer={1,2,4,6};
		int[] inner={2,4};
		System.out.println("linearIn is===>"+linearIn(outer,inner));

	}
	public static boolean linearIn(int[] outer, int[] inner) {
		int match=0;
		int x=0;
		if(inner.length==0){
			return true;
		}
		
		 for (int i = 0; i < outer.length; i++) {
			 
			 
			 if(outer[i]==inner[x]){
				 match++;
				 x++;
			 }
			/* else if(outer[i]>inner[x]){
				 return false;
			 }*/
			/* else if(outer[i]< inner[x]){
				 return false;
			 }*/
			 if(match==inner.length){
				 return true;
			 }
			
		}
		 return false;
		}

}

Open in new window


linearIn is===>true

above also passes all tests
0
gudii9Author Commented:
package com.upcast;

public class LinearIn {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] outer={1,2,4,6};
		int[] inner={2,4};
		System.out.println("linearIn is===>"+linearIn(outer,inner));

	}
	public static boolean linearIn(int[] outer, int[] inner) {
		int match=0;
		int x=0;
		if(inner.length==0){
			return true;
		}
		
		 for (int i = 0; i < outer.length; i++) {
			 
			 
			 if(outer[i]==inner[x]){
				 match++;
				 x++;
			 }
			/* else if(outer[i]>inner[x]){
				 return false;
			 }*/
			else if(outer[i]< inner[x]){
				 return false;
			 }
			 if(match==inner.length){
				 return true;
			 }
			
		}
		 return false;
		}

}

Open in new window


if i keep less than else if while debugging it is going to that loop wrongly. not sure why?
ElseIf.png
0
gudii9Author Commented:
We search for when values match.
Why do you care if the values are greater or less than?

true.

i will close this
0
gudii9Author Commented:
one other thing

public boolean linearIn(int[] outer, int[] inner) {
  List o=Arrays.asList(outer);
    List i=Arrays.asList(inner);
    if(o.contains(i)){
      return true;
    }
    else return false;
}

Open in new window


why above wont work? how tweak to make above collection list approach work?
0
rrzCommented:
above collection list approach work?

I don't think it will work for all cases.  For instance , this case from codingBat tests
linearIn([-1, 0, 3, 3, 3, 10, 12], [-1, 0, 3, 12]) → true
the values of the second array are spread out. Where a List would require them to be sequential (next to each other).  
I don't know why it didn't work for the easier cases(where the elements were sequential ).
0
gudii9Author Commented:
so instead of list use some other collection object which can work with spread out elements?
0
rrzCommented:
Yes, theoretically  your idea should work with Sets.  If I find time, I will try to find a solution.
0
gudii9Author Commented:
package com.upcast;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class LinearIn {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] outer={1,2,4,6};
		int[] inner={2,3,4};
		System.out.println("linearIn is===>"+linearIn(outer,inner));

	}
	public static boolean linearIn(int[] outer, int[] inner) {
		
		//public boolean linearIn(int[] outer, int[] inner) {
			 // List o=Arrays.asList(outer);
			 //   List i=Arrays.asList(inner);
			    Set<Integer> set1 = new HashSet<Integer>(Arrays.asList(outer));
			    Set<Integer> set2 = new HashSet<Integer>(Arrays.asList(inner));
			    if(set1.contains(set2)){
			      return true;
			    }
			    else return false;
			//}
	}

}

Open in new window


above gives compilation error at line 21 and 22
says

The constructor HashSet<Integer>(Arrays.asList(outer)) is undefined
0
rrzCommented:
I tried to find a solution using List or Set. But, I couldn't do it.
0
rrzCommented:
I finally found a solution.  
public boolean linearIn(int[] outer, int[] inner) {
		Set<Integer> outerSet = new HashSet<Integer>();
		Set<Integer> innerSet = new HashSet<Integer>();
		for(int i = 0; i < outer.length; i++){
			outerSet.add(outer[i]);
		}
		for(int j = 0; j < inner.length; j++){
			innerSet.add(inner[j]);
		}
		return outerSet.containsAll(innerSet);
}

Open in new window

0
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
Java

From novice to tech pro — start learning today.

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.