> Once they hit their limit, do they start erasing the oldest ones? The most inactive ones?

Let's do the math. If we assume that a service only uses a-z, A-Z and 0-9 as characters for the shortened URL, we have a set of 62 characters.

/x -> 62

/xx -> 62^2 = 3,844

/xxx -> 62^3 = 238,328

/xxxx -> 62^4 = 14,776,336

/xxxxx -> 62^5 = 916,132,832

/xxxxxx -> 62^6 = 56,800,235,584

In the worst case scenario, the URL shortener will have to use a 6 character identifier at some point, giving them a complessive coverage of almost 58 billion URLs.

The 4 characters they are currently using will only be enough for a while. They'll switch to 5 soon enough.