Problem:
Start with two arrays of strings, a and b, each in alphabetical order, possibly with duplicates. Return the count of the number of strings which appear in both arrays. The best "linear" solution makes a single pass over both arrays, taking advantage of the fact that they are in alphabetical order.
commonTwo({"a", "c", "x"}, {"b", "c", "d", "x"}) → 2
commonTwo({"a", "c", "x"}, {"a", "b", "c", "x", "z"}) → 3
commonTwo({"a", "b", "c"}, {"a", "b", "c"}) → 3
Solution:
public int commonTwo(String[] a, String[] b) {
int count = 0;
String str = "";
for (int i = 0; i < b.length; i++) {
for (int j = 0; j < a.length; j++) {
if (a[j].equals(b[i]) && !str.contains(a[j])) {
str += a[j];
count++;
}
}
}
return count;
}
You should only pass through each array once. By doing str.contains() you actually pass through many times in the background which is very inefficient. Here is a single pass solution (done in C#, you can convert to Java easily):
ReplyDeleteint ca = 0, cb = 0, sum = 0;
bool flag = true;
while (flag)
{
if (a[ca] == b[cb]) { ca++; cb++; sum++; }
else if (a[ca] < b[cb]) { ca++; }
else if (a[ca] > b[cb]) { cb++; }
if (ca == a.Length || cb == b.Length) { flag = false; }
}
return sum;
Yes, this is not the best linear solution ( double loops never makes single passes). However, your C# solution is broken.
Deleteif (ca == a.Length || cb == b.Length) { flag = false; }
will trigger at the end of either of the arrays.
Hence since the arrays can differ in length, it will not catch a match of the last element in A with a equal element further down in B.
Or...
ReplyDeletepublic int commonTwo(String[] a, String[] b) {
// commonTwo({"a", "a", "b", "b", "c"}, {"a", "b", "b", "b", "c"}) → 3
int cnt = 0;
int ind = 0;
for(int i = 0; i < a.length; i ++) {
if (i + 1 < a.length && a[i] == a[i + 1])
continue;
while(ind + 1 < b.length && a[i].compareTo(b[ind]) > 0)
ind ++;
if (a[i].compareTo(b[ind]) == 0) {
cnt ++;
ind ++;
}
}
return cnt;
}
I'll be the first to post a java solution using one loop:
ReplyDeletepublic int commonTwo(String[] a, String[] b) {
int alen=a.length,blen=b.length,count=0;
boolean match=false;
for(int i=0,j=0;i0){j++;match=false;}
else {match=true;i++;j++;}
if(i>0&&j>0&&i<alen&&j<blen
&&a[i].compareTo(a[i-1])==0
&&b[j].compareTo(b[j-1])==0)
match=false;
if(match)count++;
}
return count;
}
Ok, it messed up my post. Now I know why code posted by other people here wasn't compiling. I escaped the angle brackets and it seems to work now.
Deletepublic int commonTwo(String[] a, String[] b) {
int alen=a.length,blen=b.length,count=0;
boolean match=false;
for(int i=0,j=0;i<alen&j<blen;){
int cmp=a[i].compareTo(b[j]);
if(cmp<0){i++;match=false;}
else if(cmp>0){j++;match=false;}
else {match=true;i++;j++;}
if(i>0&&j>0&&i<alen&&j<blen
&&a[i].compareTo(a[i-1])==0
&&b[j].compareTo(b[j-1])==0)
match=false;
if(match)count++;
}
return count;
}
looking for the best solution--->
Deletepublic int commonTwo(String[] a, String[] b){
int bIndex = 0;
int result = 0;
for(int count = 0; count < a.length; count++){
if(count != 0 && a[count-1].equals(a[count])) continue;
if(bIndex >= b.length) break;
for(int bCount = bIndex; bCount < b.length; bCount++){
if(a[count].compareTo(b[bCount]) <= 0){
bIndex = bCount;
break;
}
}
if(a[count].equals(b[bIndex])){
result++;
bIndex++;
}
}
return result;
}
public int commonTwo(String[] a, String[] b) {
ReplyDeleteint count = 0;
int idxA = 0;
int idxB = 0;
while(idxA < a.length && idxB < b.length) {
if(idxA < a.length-1 && a[idxA].equals(a[idxA+1])){
idxA++;
continue;
}
if(idxB < b.length - 1 && b[idxB].equals(b[idxB+1])) {
idxB++;
continue;
}
int compare = a[idxA].compareTo(b[idxB]);
if(compare < 0)
idxA++;
else if(compare > 0)
idxB++;
else {
count++;
idxA++;
}
}
return count;
}
So I am pretty new to java but I did get this problem(after 30 minutes) and it involved a nested loop
ReplyDelete{
int count = 0;
int first = 0;
for (int c = 0; c<b.length;c++){
if (a[0] == b[c]){
count++;
break;
}
}
for (int i = 1;i<a.length;i++){
if (a[i] == a[i-1]){
continue;
}
for (int c = 0; c<b.length;c++){
if (a[i] == b[c]){
count++;
break;
}
}
}
return count;
}
public int commonTwo(String[] a, String[] b) {
ReplyDeleteSet setA = new HashSet<>(Arrays.asList(a));
Set setB = new HashSet<>(Arrays.asList(b));
int count = 0;
for (String str : setA)
count = setB.contains(str) ? count + 1 : count;
return count;
}
public int commonTwo(String[] a, String[] b) {
ReplyDeleteSet setA = new HashSet<>(Arrays.asList(a));
Set setB = new HashSet<>(Arrays.asList(b));
return (int) setA.stream()
.filter(setB::contains)
.count();
}
public int commonTwo(String[] a, String[] b) {
ReplyDeleteSet setA = new HashSet<>(Arrays.asList(a));
Set setB = new HashSet<>(Arrays.asList(b));
return (int) setA.stream()
.filter(setB::contains)
.count();
}
With lambda:
ReplyDeleteSet result = Arrays.stream(a).filter(s -> Arrays.asList(b).contains(s)).collect(Collectors.toSet());
return result.size();
}
public int commonTwo(String[] a, String[] b) {
ReplyDeleteSet result = Arrays.stream(a).filter(s -> Arrays.asList(b).contains(s)).collect(Collectors.toSet());
return result.size();
}