How to store a key with multiple values in HashTable?

user_14459522 0
Viewed 91

Given two arrays of integers(for example) X = [1, 1, 1, 7, 7, 7] and Y = [1, 1, 1, 8, 8, 8] to find the number of occurances of the highest appearing fraction where fraction is in the form of X[i]/Y[i] is a problem which we can solve using a HashTable to avoid O(N^2) complexity.

How do I insert entries (key, value) where key may contain multiple values? If I declare a class Fraction then the reference will be hashed and it won't work. The workaround that I used was to represent the fraction as a string X[i] concatanated with Y[i] but I am wondering if there's a better way to do this.

    static int maximumOccuringFraction(int[] X, int[] Y) {
        HashMap<String, Integer> freq = new HashMap<String, Integer>();
        int res = 1;
        for(int i = 0; i < Y.length; i++) {
            int n = X[i];
            int d = Y[i];

            String s = String.valueOf(n) + String.valueOf(d);

            if(freq.containsKey(s)) {
                res = Math.max(res, freq.get(s) + 1);
                freq.put(s, freq.get(s) + 1);
            }
            else {
                freq.put(s, 1);
            }
        }

        return res;
    }

Thanks in advance.

algorithm java
1 Answers

You should have a fraction class that overrides equals and hashcode

Here's what you can do:

public class Fraction {
  int numerator, denominator;
  public equals(Object o) {
    if (o instanceof Fraction) {
      Fraction f = (Fraction) o;
      return f.numerator == numerator && f.denominator == denominator;
    }
    return false;
  }
  public int hashCode() {
    return numerator * denominator * denominator;
  }

}

Now use this Fraction class in your Map

user_12914920
Related