This problem was addressed nicely in this functional pearl by Jeremy Gibbons, et al.: http://www.cs.ox.ac.uk/jeremy.gibbons/publications/rationals... . As interesting as the result is, however, it's a pretty well-made point that research-level ideas from the programming languages community are not really software engineering interview material in the vast majority of cases.
This is yet another example of "rockstar developer"-itis, wherein startups are given to believe that they need the best of the best when in fact they do not. This particular example is entirely egregious because they asked her about something that requires enumerating the rationals when what they really wanted was an iOS code monkey. Then they fired her, based on their own shoddy interview.