设计模式

• 观察者（Observer），LiveData
• 单例（Singleton），double check
• 适配器（Adapter），RecyclerView.Adapter
• 装饰器（Decorator），ContextWrapper
• 代理模式（Proxy），例如 VPN、Retrofit
• 责任链（Chain of Responsibility），OkHttp 大体上就是个责任链模式
• 建造者（Builder）
• 工厂（Factory）

代理模式强调不能直接访问一个对象，只能通过代理间接访问，不能直接访问的原因比如：权限校验、操作日志、RPC，比如 AIDL 生成的 IAidlInterface.Stub.Proxy 类就是代理了 remote IBinder

装饰器模式强调增强对象的功能：把一个对象的功能拆分为几部分，在运行时按需组装，比如：BufferedOutputStream、JarOutputStream、ZipOutputStream

实现 LRU

map + 双端链表，链尾是最近使用过的，链头是最久未使用的

• get(key)，通过 map 可以在 O(1) 时间内找到 value，然后把 value 从双端链表中断开并移到链尾，双端链表的特性使得「断开」操作很容易实现
• put(key, value)，把 value 添加到链尾，当超过容量限制时，从链头逐个移除 value 直到满足容量限制

几个重要的排序算法

• 归并排序 O(nlogn) step 从 1 逐步递增，合并两个长度为 step 的已排序区间，当 step > length/2 时，已排序区间就等于整个数组 合并两个有序区间很简单，用「双指针法」即可
• 快速排序 O(nlogn) 双指针，一个在头一个在尾，取第一个元素为「基准」（挖出一个坑），从尾部找一个比「基准」小的填入坑，然后又从头部找一个比「基准」大的填入尾部的坑，循环往复直到双指针碰头，那么这个位置就是「基准」的位置 每一轮都可以找出一个元素的排序后的位置，从整体看，这个元素和它左右两块是已排序的 然后递归操作左右两块区间直到区间长度为 1