Problem with doubles as key in HashMap in Java

Question

I came across an interview question for which I am not sure what the correct answer is.

The problem is below.

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

The way I solved it by looping through the element and storing the diff between target and element as key and index of the current element in a map.

Then later on when the diff appears in the array, I can look up in map which element has this diff and at what index in the map.

Up to now it is fine.

However, for a follow-up question, "What if the elements are double"

I am not sure what is the issue if any.

When searching I came across a couple of posts mentioning correct way to compute a hashcode using logical shift and using or. However, I see the similar logic is used in Java's Double.hashcode function.

I thought that the problem could be when computing diff, there might be precision loss. Hence, it might end up mapping to a different hash bucket.

However, when I tried, I couldn't come up with such an input. What is the actual problem? And how do I test/solve it?

Java

I tried simply changing the numbers to double, but the logic worked fine.

Patricia Shanahan · Accepted Answer · 2019-09-03 16:23:37Z

2

This program illustrates the problem, with a two element array:

public strictfp class Test {
  public static void main(String[] args) {
    double in[] = {1e10, Math.nextUp(1e10)};
    double target = 2e10;
    System.out.println(in[0]+in[1]);
    double diff = target-in[0];
    System.out.println(diff);
    System.out.println(in[1] == diff);
    System.out.println(in[0]+in[1] == target);
  }
}

output:

2.0E10
1.0E10
false
true

The problem is that your logic assumes that there is only one value that, when added to an element of your array, gives the target sum. Because of rounding, with double elements, there can be multiple values that give the same sum.

In my example, the sum of the two elements of the array is equal to the target, but the second element is not equal to the difference between in[0] and the target.

My first thought on a solution to the floating point version of the problem is as follows:

Create an array of ordered pairs containing value and index.
Sort by value.
For each element x, do a binary search for an element y such that x.value + y.value is equal to the target.
If you find one, return [x.index, y.index]

This is O(n log(n)) where the int version was O(n).

edited Sep 3, 2019 at 16:23

answered Sep 3, 2019 at 3:10

Patricia Shanahan

26.2k4 gold badges42 silver badges75 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

user6640997 Over a year ago

Thank you!! this is what I was looking for!

user6640997 Over a year ago

Any comments on how to solve it if we have to go about it?

Collectives™ on Stack Overflow

Problem with doubles as key in HashMap in Java

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related