【面试高频题】源于「场景八股文」的算法题

站长

2023年07月25日 11:34 · 阅读数 13

题目描述

这是 LeetCode 上的 535. TinyURL 的加密与解密 ，难度为中等。

Tag : 「哈希表」、「模拟」

TinyURL 是一种 URL 简化服务，比如：当你输入一个 URL https://leetcode.com/problems/design-tinyurl 时，它将返回一个简化的URL http://tinyurl.com/4e9iAk 。

请你设计一个类来加密与解密 TinyURL 。

加密和解密算法如何设计和运作是没有限制的，你只需要保证一个 URL 可以被加密成一个 TinyURL ，并且这个 TinyURL 可以用解密方法恢复成原本的 URL 。

实现 Solution 类：

Solution() 初始化 TinyURL 系统对象。
String encode(String longUrl) 返回 longUrl 对应的 TinyURL 。
String decode(String shortUrl) 返回 shortUrl 原本的 URL。题目数据保证给定的 shortUrl 是由同一个系统对象加密的。

示例：

输入：url = "https://leetcode.com/problems/design-tinyurl"

输出："https://leetcode.com/problems/design-tinyurl"

解释：
Solution obj = new Solution();
string tiny = obj.encode(url); // 返回加密后得到的 TinyURL 。
string ans = obj.decode(tiny); // 返回解密后得到的原本的 URL 。

提示：

1<=url.length<=1041 <= url.length <= 10^41<=url.length<=104
题目数据保证 url 是一个有效的 URL

模拟 + 哈希表

对于每个 longUrl 我们都在「大写字母/小写字母/数字」中随机 k=6k = 6k=6 位作为其映射标识，这需要使用一个哈希表 tiny2Origin 进行记录。

同时了防止相同的 longUrl 多次调用，确保 encode 服务的「幂等性」，我们再额外建立哈希表 origin2Tiny 来记录原串和映射标识的对应关系。

Java 代码：

public class Codec {
    Map<String, String> origin2Tiny = new HashMap<>(), tiny2Origin = new HashMap<>();
    String str = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890";
    String prefix = "https://acoier.com/tags/";
    int k = 6;
    Random random = new Random();
    public String encode(String longUrl) {
        while (!origin2Tiny.containsKey(longUrl)) {
            char[] cs = new char[k];
            for (int i = 0; i < k; i++) cs[i] = str.charAt(random.nextInt(str.length()));
            String cur = prefix + String.valueOf(cs);
            if (tiny2Origin.containsKey(cur)) continue;
            tiny2Origin.put(cur, longUrl);
            origin2Tiny.put(longUrl, cur);
        }
        return origin2Tiny.get(longUrl);
    }
    public String decode(String shortUrl) {
		return tiny2Origin.get(shortUrl);
    }
}

Python 代码：

class Codec:
    def __init__(self):
        self.origin_to_tiny = {}
        self.tiny_to_origin = {}
        self.k = 6
        self.prefix = 'https://acoier.com/tags/'
        self.ss = string.ascii_letters + string.digits

    def encode(self, longUrl: str) -> str:
        while longUrl not in self.origin_to_tiny.keys():
            cur = ''.join([self.ss[random.randint(0,len(self.ss) - 1)] for _ in range(self.k)])
            if cur in self.tiny_to_origin.keys():
                continue
            self.tiny_to_origin[cur] = longUrl
            self.origin_to_tiny[longUrl] = cur
        return self.origin_to_tiny[longUrl]
        
    def decode(self, shortUrl: str) -> str:
        return self.tiny_to_origin[shortUrl]

时间复杂度：encode 操作复杂度为 O(C+L)O(C + L)O(C+L)，其中 C=6C = 6C=6 为短串长度，LLL 为传入参数 longUrl 的长度（存入哈希表需要计算 longUrl 哈希值，该过程需要遍历 longUrl）；decode 操作复杂度为 O(C)O(C)O(C)，其中 LLL 为传入参数 shortUrl 的长度，该长度固定为 prefix 长度加 666
空间复杂度：O(K×L)O(K \times L)O(K×L)，其中 KKK 为调用次数，LLL 为平均 longUrl 长度

关于使用「自增 `id`」的答疑

群里有同学问到为啥要使用「哈希存储映射关系」的方式，而不是用「自增 id」的方式，感觉可能是一部分同学的共同疑惑，这里统一回答一下。

其中两点较为致命的弊端是：

使用「自增 id」更容易被枚举；

（再补充，提出原问题的好奇宝宝又问了另外一个问题）关于被枚举的坏处：粗略来说会导致安全性下降，被攻击的可能性大大增强。因为可枚举意味着，不能光靠 URL 特定发放来确保安全。

结合具体场景来说，假设某个活动日期生成了短 URL 的活动链接，只有特定用户可以访问，可枚举意味着竞品只需要大概知道你自增 id 当前在什么范围即可拿到活动链接，即使活动链接做了鉴权，也能通过攻击手段导致服务请求数量突增，影响真实的活动用户使用。

或许这个场景并不致命，竞品要拿到活动链接有很多方式，未必是通过枚举短 URL 来做到。

但另外一个场景则是致命的，就是可枚举会导致使用短 URL 服务的「验证服务」失效。

例如某个服务会通过「邮件/短信」发送短 URL 链接，让用户通过点击短 URL 来验证是否为某个「邮箱/手机号」的拥有者，短 URL 可枚举，意味着只需要知道当前自增 id 大概范围，就可通过枚举的方式访问到真实的验证地址，从而实现「不收到某个邮件/短信」也可以通过验证的目的。
相比于使用「哈希存储映射关系」的方式，不好重用：

举个🌰，例如映射关系都是 777 天过期，每天会产生了 101010 个短 URL，当进行到第 888 天，此时 id 已经自增到 717171，同时第一天产生的短 URL 已过期，但是实现上，我们不好将 id 进行回拨（需要考虑当重用数字用完后要回到 717171 的位置）。也就是说，发现而且重用某些数字段（过期的 id）会为“自增”带来困扰，而引入「重用池」则违背了选择自增方案的初衷。

但「哈希存储映射关系」要实现重用则是简单的，如果随机产生的短 URL 发生冲突，只需要直接拒绝进行重试即可，一旦产生短 URL 无冲突，则可以直接使用。同时由于随机通常服从某种分布，我们无须引入「过期时间戳」等信息，即可达到「某个短 URL 在使用后的一段时间后，都不会被随机到（不会在过期后就被迅速重用）」的作用，这一点可以通过调大 kkk 值来进一步保证。

防杠声明：当然，如果你只是在单纯的做算法题，就当我没说 🤣

最后

这是我们「刷穿 LeetCode」系列文章的第 No.535 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

更多更全更热门的「笔试/面试」相关资料可访问排版精美的合集新基地 🎉🎉

【面试高频题】源于「场景八股文」的算法题

题目描述

模拟 + 哈希表

关于使用「自增 id」的答疑

最后

关于使用「自增 `id`」的答疑