asked on linearIn challenge
Hi,
I am working on below challenge
how to verify one array has one other target array or not? is there is built in method for that?
please advise
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
JavaJava EEProgramming Languages-OtherProgrammingProgramming Theory
Last Comment
rrz
The arrays are sorted - you just go over them and compare the numbers.
ASKER
i will try. so two for loops needed right for each array?
Yes
ASKER
i forgot link
http://codingbat.com/prob/p134022
http://codingbat.com/prob/p134022
ASKER
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
\i tried as above failing some tests. please advise
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;
}
\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
ASKER
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;
}
}
changed contains to containsAll still getting false instead of true
ASKER CERTIFIED SOLUTION
THIS SOLUTION ONLY AVAILABLE TO MEMBERS.
View this solution by signing up for a free trial.
Members can start a 7-Day free trial and enjoy unlimited access to the platform.
ASKER
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;
}
Expected Runtried as above failing some tests. please advise
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
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;
}
}
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.
ASKER
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;
}
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;
}
}
linearIn is===>true
Not clear how and why?
Not clear how and why?What was the purpose of
29: /* else if(outer[i]< inner[x]){
30: return false;
31: }*/
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;
}
ASKER
i was thinking there are 3 cases always right when comparing
1. equals
2. greater
3. less than
1. equals
2. greater
3. less than
We search for when values match.
Why do you care if the values are greater or less than?
Why do you care if the values are greater or less than?
ASKER
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;
}
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;
}
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;
}
}
linearIn is===>true
above also passes all tests
ASKER
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;
}
}
if i keep less than else if while debugging it is going to that loop wrongly. not sure why?
ElseIf.png
ASKER
We search for when values match.
Why do you care if the values are greater or less than?
true.
i will close this
ASKER
one other thing
why above wont work? how tweak to make above collection list approach work?
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;
}
why above wont work? how tweak to make above collection list approach work?
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 ).
ASKER
so instead of list use some other collection object which can work with spread out elements?
Yes, theoretically your idea should work with Sets. If I find time, I will try to find a solution.
ASKER
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;
//}
}
}
above gives compilation error at line 21 and 22
says
The constructor HashSet<Integer>(Arrays.as
I tried to find a solution using List or Set. But, I couldn't do it.
SOLUTION
THIS SOLUTION ONLY AVAILABLE TO MEMBERS.
View this solution by signing up for a free trial.
Members can start a 7-Day free trial and enjoy unlimited access to the platform.