Java > AP-1 > commonTwo (CodingBat Solution)

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;
}


8 comments :

  1. 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):

    int 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;

    ReplyDelete
    Replies
    1. Yes, this is not the best linear solution ( double loops never makes single passes). However, your C# solution is broken.

      if (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.

      Delete
  2. Or...

    public 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;

    }

    ReplyDelete
  3. I'll be the first to post a java solution using one loop:

    public 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;
    }

    ReplyDelete
    Replies
    1. 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.

      public 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;
      }

      Delete
    2. looking for the best solution--->

      public 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;
      }

      Delete
  4. public int commonTwo(String[] a, String[] b) {
    int 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;
    }

    ReplyDelete
  5. So I am pretty new to java but I did get this problem(after 30 minutes) and it involved a nested loop
    {
    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;
    }

    ReplyDelete

Follow Me

If you like our content, feel free to follow me to stay updated.

Subscribe

Enter your email address:

We hate spam as much as you do.

Upload Material

Got an exam, project, tutorial video, exercise, solutions, unsolved problem, question, solution manual? We are open to any coding material. Why not upload?

Upload

Copyright © 2012 - 2014 Java Problems  --  About  --  Attribution  --  Privacy Policy  --  Terms of Use  --  Contact