Normally, I'd disagree, but part of starting a URL shortening company would seem to be a commitment to keep it working in the future, partially because its so easy and partially because URLs shouldn't die.
Charitably, we'll say they have a billion URLs. Each mapping is maybe 8bytes->256bytes. So they have a max of 264GB of data. That would fit on a heroku postgres dev plan, and the code to run it would take a single engineer half a day to put it on heroku.