Solved

linearIn  challenge

Posted on 2016-08-14
23
111 Views
Last Modified: 2016-08-20
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
0
Comment
Question by:gudii9
  • 13
  • 7
  • 3
23 Comments
 
LVL 37

Expert Comment

by:Gerwin Jansen, EE MVE
ID: 41756186
The arrays are sorted - you just go over them and compare the numbers.
0
 
LVL 7

Author Comment

by:gudii9
ID: 41756466
i will try. so two for loops needed right for each array?
0
 
LVL 37

Expert Comment

by:Gerwin Jansen, EE MVE
ID: 41756558
Yes
0
How our DevOps Teams Maximize Uptime

Our Dev teams are like yours. They’re continually cranking out code for new features/bugs fixes, testing, deploying, responding to production monitoring events and more. It’s complex. So, we thought you’d like to see what’s working for us. Read the use case whitepaper.

 
LVL 7

Author Comment

by:gudii9
ID: 41760217
0
 
LVL 7

Author Comment

by:gudii9
ID: 41760238
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
 
LVL 7

Author Comment

by:gudii9
ID: 41760258
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
 
LVL 37

Accepted Solution

by:
Gerwin Jansen, EE MVE earned 250 total points
ID: 41760811
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
 
LVL 7

Author Comment

by:gudii9
ID: 41761940
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
 
LVL 27

Expert Comment

by:rrz
ID: 41762650
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
 
LVL 7

Author Comment

by:gudii9
ID: 41762935
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
 
LVL 27

Expert Comment

by:rrz
ID: 41762999
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
 
LVL 7

Author Comment

by:gudii9
ID: 41763007
i was thinking there are 3 cases always right when comparing
1. equals
2. greater
3. less than
0
 
LVL 27

Expert Comment

by:rrz
ID: 41763013
We search for when values match.
Why do you care if the values are greater or less than?
0
 
LVL 7

Author Comment

by:gudii9
ID: 41763024
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
 
LVL 7

Author Comment

by:gudii9
ID: 41763032
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
 
LVL 7

Author Comment

by:gudii9
ID: 41763035
We search for when values match.
Why do you care if the values are greater or less than?

true.

i will close this
0
 
LVL 7

Author Comment

by:gudii9
ID: 41763046
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
 
LVL 27

Expert Comment

by:rrz
ID: 41763067
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
 
LVL 7

Author Comment

by:gudii9
ID: 41763150
so instead of list use some other collection object which can work with spread out elements?
0
 
LVL 27

Expert Comment

by:rrz
ID: 41763271
Yes, theoretically  your idea should work with Sets.  If I find time, I will try to find a solution.
0
 
LVL 7

Author Comment

by:gudii9
ID: 41763354
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
 
LVL 27

Expert Comment

by:rrz
ID: 41763369
I tried to find a solution using List or Set. But, I couldn't do it.
0
 
LVL 27

Assisted Solution

by:rrz
rrz earned 250 total points
ID: 41763768
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

Featured Post

Announcing the Most Valuable Experts of 2016

MVEs are more concerned with the satisfaction of those they help than with the considerable points they can earn. They are the types of people you feel privileged to call colleagues. Join us in honoring this amazing group of Experts.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
xampp tool 12 52
maven module vs maven project 3 25
JavaFX TableView not displaying correctly 3 21
Object Oriented Programming, C#, referencing, scoping. 13 48
This is an explanation of a simple data model to help parse a JSON feed
In this post we will learn how to connect and configure Android Device (Smartphone etc.) with Android Studio. After that we will run a simple Hello World Program.
The viewer will learn how to use the return statement in functions in C++. The video will also teach the user how to pass data to a function and have the function return data back for further processing.
With the power of JIRA, there's an unlimited number of ways you can customize it, use it and benefit from it. With that in mind, there's bound to be things that I wasn't able to cover in this course. With this summary we'll look at some places to go…

825 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