4
\$\begingroup\$

I'm trying to solve this fairly straight forward challenge:

Problem Statement

In computer science, a set is an abstract data type that can store certain values, without any particular order, and no repeated values. {1,2,3} is an example of a set, but {1,2,2} is not a set. Today you will learn how to use sets in java by solving this problem.

You are given n pairs of strings. Two pairs (a,b) and (c,d) are identical if a=b and c=d. That also implies (a,b) is not same as (b,a). After taking each pair as input, you need to print number of unique pairs you currently have.

Note: Brute force solution will not earn full points.

This works, but I'm getting a timeout on the last test case (10.000 elements to go through).

import java.io.*;
import java.util.*;

public class Solution {

    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        Set<Pair> pairs = new HashSet<>();
        final int N = s.nextInt();

        for(int i = 0; i < N; i++) {
            String first = s.next();
            String second = s.next();

            pairs.add(new Pair(first, second));
            System.out.println(pairs.size());
        }       
    }

    public static class Pair {
        String first, second;
        Pair(String first, String second) {
            this.first = first;
            this.second = second;
        }

        @Override public int hashCode() {
            return first.hashCode();
        }

        @Override public boolean equals(Object other) {
            if (other == this) {
                return true;
            }
            if (!(other instanceof Pair)) {
                return false;
            }

            Pair otherPair = (Pair) other;
            return (first.equals(otherPair.first) && second.equals(otherPair.second))
                || (first.equals(otherPair.second) && second.equals(otherPair.first));
        }

    }
}
\$\endgroup\$
  • 3
    \$\begingroup\$ The problem's definition of equality seems broken. If (a,b)=(c,d) => a=b and c=d, then (a,b)=(c,d) => (b,a)=(c,d) by definition. But the problem specifically says that (a,b) and (b,a) are not identical. I'm fairly certain it's supposed to be "a=c and b=d". \$\endgroup\$ – cHao May 16 '15 at 19:42
5
\$\begingroup\$

Clearly, janos solution is the simplest, but it'd probably break for the input

a b
a  b

Moreover, it circumvents the learning effect (I guess, it's about learning to write a class with equals and hashCode).

As often, Lombok makes it trivial:

@EqualsAndHashCode
public static class Pair {
    private final String first, second;
}

hashCode

The inefficiency was most probably caused by

@Override public int hashCode() {
    return first.hashCode();
}

which is correct, but leads to many collisions due to ignoring second. Something like

    return first.hashCode() + 123456789 * second.hashCode();

would solve it (the multiplier should be odd, anything else doesn't matter much).

equals

  return (first.equals(otherPair.first) && second.equals(otherPair.second))
            || (first.equals(otherPair.second) && second.equals(otherPair.first));

This contradicts the part

implies (a,b) is not same as (b,a).

If it ever worked, then only because of the asymmetry in hashCode.

Why?

Two equals objects must have the same hashCode, otherwise the HashSet doesn't work properly (as the hash determines the index where the lookup starts). Violating this rule is a serious bug with which you may spend many funny debugging days.

This time, it helped you. After

set.put(new Pair("a", "b"));

the query

set.contains(new Pair("b", "a"));

erroneously returns false, although according to equals, the pair is there. However, it doesn't get found due to the non-equal hashCode. Analogously, after

set.put(new Pair("b", "a"));

you managed to contradict

set is an abstract data type that can store certain values, without any particular order, and no repeated values.

Note that this is not guaranteed to happen as the hashes may coincide and only a part of them gets used.

\$\endgroup\$
  • \$\begingroup\$ What do you mean by the last line in your answer? \$\endgroup\$ – Nilzone- May 16 '15 at 20:51
  • \$\begingroup\$ Thanks for such a detailed answer. Is it enough to remove this part of the equals? || (first.equals(otherPair.second) && second.equals(otherPair.first)? \$\endgroup\$ – Nilzone- May 16 '15 at 21:15
  • \$\begingroup\$ @Nilzone- For correctness, yes. For speed, I'd suggest to change the hashCode as well as ignoring one half of the pair is too bad. Use first.hashCode() - second.hashCode() if you're scared of the multiplication (+ is slightly worse because of the symmetry). \$\endgroup\$ – maaartinus May 16 '15 at 21:26
  • \$\begingroup\$ One more question. When I used first.hashCode() + second.hashCode() I got the wrong answer on some of the test cases. Why do you think that is? \$\endgroup\$ – Nilzone- May 16 '15 at 21:31
  • 1
    \$\begingroup\$ @Nilzone- Re-read my last paragraph. Your hashCode matched your equals (both were symmetrical), so this part worked correctly. But your equals didn't match what you should do. +++ With your working code, there were two bugs sort of cancelling each other. \$\endgroup\$ – maaartinus May 16 '15 at 21:36
4
\$\begingroup\$

Given the problem description, it seems you don't need to worry about pairs at all. You can simply shove all data lines into a Set, and finally print the size:

public static void main(String[] args) {
    Scanner s = new Scanner(System.in);
    Set<String> lines = new HashSet<>();
    final int N = s.nextInt();
    s.nextLine();

    for (int i = 0; i < N; i++) {
        lines.add(s.nextLine());
    }       
    System.out.println(lines.size());
}

Unless, the n pairs of strings are not on individual lines, but you in fact have a sequence of integers on one line. In that case you can adapt the main loop:

    for (int i = 0; i < N; i++) {
        lines.add(s.nextInt() + ":" + s.nextInt());
    }       
\$\endgroup\$
  • \$\begingroup\$ oh my god.... You're absolutely right. I'm feeling pretty stupid right now. It's way to easy to think the problem is much worse than what it actually is. \$\endgroup\$ – Nilzone- May 16 '15 at 19:34
  • \$\begingroup\$ I guess, I could break you code via a b\na b. \$\endgroup\$ – maaartinus May 16 '15 at 20:36
3
\$\begingroup\$

Since @janos and @maaartinus have adequately covered the performance concerns, I'll touch on two other supplementary things:

  1. try-with-resources

    You should use try-with-resources on your Scanner object:

    public static void main(String[] args) {
        try (Scanner scanner = new Scanner(System.in)) {
            // ...
        }
    }
    
  2. Objects utility class from Java 7

    Since you are already using Java 7, you can consider using the Objects utility class to greatly standardize the way to do hashCode() and equals():

    public static final class Pair {
    
        private final String[] pair;
        private final int hashCode;
    
        public Pair(String first, String second) {
            pair = new String[] { first, second };
            hashCode = Objects.hash(first, second);
        }
    
        @Override
        public boolean equals(Object o) {
            return o instanceof Pair && Objects.deepEquals(pair, ((Pair) o).pair);
        }
    
        @Override
        public int hashCode() {
            return hashCode;
        }
    }
    

    Since the pair of Strings are expected to remain immutable, you can create an array of out them to facilitate the deepEquals() usage and also pre-compute the hash code by using hash(Object...). These cuts down on the 'boilerplate-like' code you'll be required to write for the two String values otherwise. I've chosen to make the class final so that you can be sure instanceof will only work for Pair instances.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.