URL Shortener - Airbnb

https://instant.1point3acres.com/thread/196339
Often, we want to encode raw IDs in our database by hiding them behind some 2-way decodeable hash. So, a URL which would have at one time been: https://www.airbnb.com/rooms/848662 becomes https://www.airbnb.com/rooms/kljJJ324hjkS_ We decode the ID kljJJ324hjkS to 848662 on our backend and serve the relevant content. 

At some point, we start getting 404 errors from clients requesting a certain URL of the form https://www.airbnb.com/rooms/kljjj324hjks This can happen if certain clients, email services, or url shorteners "sanitize" the url. Unfortunately, this change breaks decoding and the resource cannot be found. To assess how big of a deal this is, we may want to recover the IDs of the targets that were 404ing. 

Given a method decode(testEncStr) which will return the decoded int id if testEncStr is decodeable or will throw an exception (or return null) if not, implement a new method decodeFind(String badEncStr) which takes a string and returns the decoded int id. 

airbnb面试题汇总

看描述好像是url里的id如果有某些位置大小写换了会导致原来的url decode有问题，需要重写encode方法，回溯改某些位的大小写判断

    int decode(string url) {
        string dUrl = "kljJJ324hijkS_";
        if (url == dUrl) return 848662;
        return -1;
    }

    int decodeFind(string url) {
        return helper(url, 0);
    }

private:
    int helper(string s, int idx) {
        if (idx == s.length())
            return decode(s);
        if (isalpha(s[idx])) {
            int uid = helper(s.substr(0, idx) + char(tolower(s[idx])) + s.substr(idx + 1), idx + 1);
            int lid = helper(s.substr(0, idx) + char(toupper(s[idx])) + s.substr(idx + 1), idx + 1);
            if (uid != -1 || lid != -1)
                return uid != -1 ? uid : lid;
            return -1;
        } else {
            return helper(s, idx + 1);
        }
    }