0

Here is an interview question:

$f:[0,1]\rightarrow [0,1],$ a 'almost' monotone increasing function. Given 10 inputs and their outputs, how can you find the best estimation of $f(x) = 0.5?$

I think using interpolation is best here. However almost monotone increasing seems very tricky. Is there any good idea behind it?

rhkoulen
  • 306
user6703592
  • 535

1 Answers1

0

Pick the closest solution above $0.5$, closest solution below $0.5$, then assume linearity of $f$ on that domain and calculate where $0.5$ would lie in that domain.

This method is really fallible though, especially given that the function can decrease.

rhkoulen
  • 306
  • then we only use the information of 2 points and the left 8 points are useless. – user6703592 Nov 19 '21 at 19:00
  • I just gave the simplest thing I could think of. I believe almost monotone is just a term that the interviewer uses to remove any ideas of a "correct" solution and take the interviewee out of their comfort zone. Quite often they don't really care what solution you come up with, rather how you thought around it. – rhkoulen Nov 19 '21 at 21:28
  • If you want a solution that utilizes the information from all 10 points, you could perform a regression on the data then solve for 0.5. – rhkoulen Nov 19 '21 at 21:29
  • for regression and interpolation, which one is better? – user6703592 Nov 20 '21 at 04:38
  • I'm not sure. To be honest, I haven't learned much about regressions, but from what I've seen, methods require the user to guess what type of function the data is, so there's no way to create a general form solution. Also, with the interpolation method, using the intermediate value theorem, an $x$ such that $f(x)=0.5$ must exist in the domain between our two selected points. This allows us to get an exact upper bound on our error, which I think is nice. – rhkoulen Nov 20 '21 at 06:15