Comparing products given three seperate lists

Question

You are given a list of n products, each with a name, price and weight.

Find out how many duplicates of a product are present within the list. A duplicate is a product with all parameters, equal to some other product.

input is 3 lists

   Name Price Weight
 1. ball 2     1
 2. box  2     2
 3. ball 2     1
 4. ball 2     1
 5. box  2     3

output:

    2

explanation:

   (1.) is same as (3.) and is also same as (4.) so there is 2... 1->3 and 1->4

Function Description

numDuplicates has the following parameter(s):

name: string array of size n, where names[i] denotes the name of the ith product

price: int array of size n, where prices[i] denotes the price of the ith product

weight: int array of size n, where weights[i] denotes the weight of the ith product

function you need to fill out:

public static int numDuplicates(List<String> name, List<Integer> price, List<Integer> weight) {
// Write your code here
    //return an int
}

this is what i wrote for my code and is O(n^2) but some test-cases are running out of time so i think it wants an O(n) solution but i cant think of it...

 class Result {

/*
 * Complete the 'numDuplicates' function below.
 *
 * The function is expected to return an INTEGER.
 * The function accepts following parameters:
 *  1. STRING_ARRAY name
 *  2. INTEGER_ARRAY price
 *  3. INTEGER_ARRAY weight
 */

    public static int numDuplicates(List<String> name, List<Integer> price, List<Integer> weight) {
    int count = 0;
    List<obj> classList = new ArrayList<obj>();
    for(int i=0; i<name.size(); i++){
        obj holder = new obj(name.get(i),price.get(i),weight.get(i));
        classList.add(holder);
    }
    for(int i=0; i<classList.size(); i++){
        for(int j=i+1; j<classList.size();j++){
            if(classList.get(i).isDuplicate(classList.get(j))){
                count++;
                classList.remove(classList.get(j));
                j--;
            }
        }
    }
    return count;
 }

}

class obj{
  String name;
  int price;
  int weight;
  public obj(String name, int price, int weight){
      this.name = name;
      this.price = price;
      this.weight = weight;
  }
  public boolean isDuplicate(obj x){
      if(this.name.equals(x.name) && this.price == x.price && this.weight == x.weight){
          return true;
      }
      return false;
   }
}

i created my own object class, and i created a compare method but i think it might be inefficent

Solution 1

public static int numDuplicates(List<String> name, List<Integer> price, List<Integer> weight) {
        Set<String> uniqueProducts = new HashSet<String>();
        for (int i = 0; i < name.size(); i++)
            uniqueProducts.add(name.get(i) + " " + price.get(i) + " " + weight.get(i)); 
        return name.size() - uniqueProducts.size();
}

Solution 2

For :

public static int numDuplicates(List<String> name, List<Integer> price, List<Integer> weight) {
// Write your code here
    //return an int
}

Use Like below:

public static int numDuplicates(List<String> name, List<Integer> price, List<Integer> weight) {
List<String> f1 = new ArrayList<String>();

int countTotal = name.size();

for (int i = 0; i < countTotal; i++) {
    f1.add(name.get(i) + price.get(i) + weight.get(i));
}

//Unique List item
Set<String> uniqueItemSet = new HashSet<String>(f1);

Integer uniqueItems = uniqueItemSet.size();
int countAll = f1.size();
return(countAll-uniqueItems);
    }

Comments

[user4581301]

More language tags attracts more eyes to your question, but remember that no small number of those extra eyes aren't interested in solving, or qualified to solve, Java problems. Some will be annoyed. Anyway, there is no need to think something is inefficient. You can profile the code, prove that it is inefficient, and learn exactly what is most inefficient so that you know where to focus your efforts.

[Questions]

@user4581301 you can answer this question in any language, i just gave my answer in java, so even if its done in python i don't mind... Hackerrank says its inefficient, i know it is O(n^2) which is making it inefficient so it wants a O(n) answer, i have been trying but i can't think of an O(n) answer.

[user4581301]

Try this: Before you add to the List try to put the item in a Set. If it's is already in the Set, it's a duplicate. Count it and don't add to the list. You'll have to meet the Set equality requirements and it's been well over a decade since I wrote any amount of Java. I can't remember them, but Java had really good docs. That alone should get you down to a bit worse than O(N), probably N Log N.

[user4581301]

You definitely don't want to read in everything and then remove duplicates, that's for suckers. Don't put duplicates in in the first place. Save you the whole second set of loops.

[Mritunjai Singh]

Please use above code hope using that you can achieve O(n) efficiency

[Eduardo Mauro]

This solution it not good. Instead of a list use a HashMap. After inserting all keys (concatenate the values of each item) use the number of elements in the HashMap as the result.

[ansh sachdeva]

Welcome to the site. Please add some more explanation regarding how this code works, for the better understanding of author and other community members

[flemadap]

On the produce = names.get(i).... You should use separator, because if price and weight have different value but the same concatenated result, it would be a wrong product hash key.