Check if I have a phone number
Rewritten to match the new edited version of the question

What you want to think about is the size of the state for a DFA corresponding to a regular expression to match the number in question.

(I don't know how to draw DFAs here so work with my hand waving if you can.)

Since the thing you are looking for is a constant string the regular expression is just that string, say for example 6041234567. As a DFA this is a start node connected 10 intermediate nodes and a final accepting node. Then each of these nodes connect to the next node if the next character is the right one in the stream or back to the start if it is an incorrect input.  If you ever reach the final accepting node you have found the phone number and can do a happy dance.

That is all a setup for the fact that the only thing that matters state-wise is the current node you are matching on.  In my simple example here there are 12 nodes total, so you really only need 4 bits of data.

So you could have one upped the interviewer and said that in reality all you needed is a single nybble, instead of a whole byte. 

A note about loop unrolling and state hiding

You can also achieve this by just writing a long list of checks for each individual digit as David commented above with what appears to be zero state.  But what that long list of checks is really doing is just moving the state into the program counter. You can do that with any fixed length matching problem, it is technically true but not really interesting.

One can also argue that I am moving state into the DFA, how is that represented? That is a fair cop, if one is being super pedantic, we would have to specify things like "A DFA is a 5-tuple consisting of yada yada yada" when we really need that precision.  Unless you were interviewing for a position in CS theory or compiler design no interviewer would be going there.

The reason that I am pretty certain that my answer is the right one in this case is that this question sounds like one that is asked all the time.  About half-way through a Theory of Computation course right after you learn about using DFAs to match REGEXPs you will look into the number of states and how to represent them.  This gives a nice intuition about the complexity and "size" of the various languages they match.  It also nicely segues into the way that removing determinism can greatly shrink the resulting transition graph and going the other way can result in an explosion in the number of states.