5

I came across this question while looking for Amazon interview questions and wanted to ask.

Given a number, how can you find the closest number in a series of floating point data?

If everything is integer , answer is substracting the number from every number in the array, then look for the element with minimum absolute value in the array.

But when it comes to floating points, it should be highly nontirival.

Ani ideas?? Thanks.

Dogacan Sbdb
  • 69
  • 4
  • 2
    Why do you think floating point changes the algorithm? – Mark Ransom May 13 '15 at 19:43
  • 1
    What exactly does "series" mean? Can you sort it and use binary search? Binary search shouldn't have problems with floating point. – Kolmar May 13 '15 at 19:45
  • `If everything is integer , answer is substracting the number from every number in the array, then look for the minimal element of the array.` don't you mean minimal absolute value (i.e. closest to zero)? Or am I completely misunderstanding what you are trying to achieve? – amit May 13 '15 at 19:47
  • 2
    @MarkRansom The problem with floating-point is limited precision. Examples: 1) `x=1e100, arr=[-1, 1, 0]`. Answer should be `1`, but all `abs` values of differences are equal to `1e100`; 2) `x = 1; arr = [-1e100, 1e100]`. Then answer should be `1e100` but both `abs` of differences are equal to `1e100`. (and binary search won't help in the latter case as well...) – Kolmar May 13 '15 at 19:55
  • @amit, you got it completely correct. I meant absolute value, my writing wasn't correct. – Dogacan Sbdb May 13 '15 at 20:03
  • brute force? subtract all the values. Convert the original floating point numbers to values in the arbitrary precision library format. Check for closest value using that format since it doesn't include rounding errors. – Jay May 13 '15 at 20:04
  • @Kolmar , let's say num=2. Then we have [1.9999999, 2.000000000001, 2.00000000000001]. – Dogacan Sbdb May 13 '15 at 20:05
  • @Kolmar thanks for those illuminating examples. – Mark Ransom May 13 '15 at 20:25
  • does anyone think this maybe related to machine epsilon (how to estimate and how to apply), like this post : http://stackoverflow.com/questions/4915462/how-should-i-do-floating-point-comparison – shole May 14 '15 at 07:51

1 Answers1

4

The problem with floats is rounding errors. However, comparison of floats is not subject to rounding errors: therefore, you can correctly find the number just bigger and just smaller than x in linear time:

sm = -inf;
bg = inf;
for(i from 0 to n)
  if(arr[i] > x && arr[i] < bg)
    bg = arr[i];
  if(arr[i] < x && arr[i] > sm)
    sm = arr[i];

Now you only need to determine which of these two numbers is closer to x. Since bg is bigger and sm is smaller, the only time you can have rounding error is when bg >> x or x >> sm; in either of these cases, it will only increase the magnitude of the rounded difference.

(If the magnitudes are the same, for instance if x=1 and arr=[1e100, -1e100], you can know that x is closer to the value with the same sign as itself.)

Kittsil
  • 2,349
  • 13
  • 22