I guess finite fields $k = \mathbb{F}_{q}$ satisfy this property, namely we can take $$ f = ((x_{1}-a_{1})^{q-1}-1) \dotsb ((x_{n}-a_{n})^{q-1}-1) - (-1)^{n} $$ for any $n$.
In fact we have a Lagrange interpolation formula for finite fields, see this answer.
