Problem: Alice chooses a secret polynomial $p(x)$ with nonnegative integer coefficients. Bob wants to discover this polynomial by querying Alice for the value of $p(x)$ for some integer $x$ of Bob’s choice. What is the minimal number of queries Bob needs to determine $p(x)$ exactly?
I got this problem from https://jeremykun.com/2014/11/18/learning-a-single-variable-polynomial-or-the-power-of-adaptive-queries/ [the answer is here, so, if you want to think about the problem, you should be careful :) ]