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](http://mathoverflow.net/a/231571/15505).