Algorithm
本周选择的算法题是：Find First and Last Position of Element in Sorted Array
规则如下：
Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.
Your algorithm’s runtime complexity must be in the order of O(log n).
If the target is not found in the array, return [-1, -1].
Example 1:
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]
Example 2:
Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]
Solution
我实现的方案：
Runtime：84 ms，快过 96.23%。
Memory：14.1 MB，低于 5.36%。
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
if len(nums) == 0: return [-1, -1]
def leftmost(find_target: int, low = 0, high = len(nums) - 1) -> int:
while low < high:
pivot_index = (low + high) // 2
if nums[pivot_index] < find_target:
low = pivot_index + 1
else:
high = pivot_index
return low
low = leftmost(target)
if nums[low] == target:
high = leftmost(target + 1, low)
return [low, high if nums[high] == target else high - 1]
else:
return [-1, -1]
这道题很明显需要用二分查找，可以使用一个 leftmost 或者 leftmost + rightmost 来实现。
Review
An introduction into the WSGI ecosystem WSGI 生态系统简介
这篇文章用清晰易懂的方式捋清了 WSGI 中各个软件的作用，评论也很精彩。
容易混淆的几个名词：
WSGI - 一个软件规范，用于解决 web server 和 python app 之间如何调用的问题。
uWSGI - 一个实现了 WSGI 规范的 web server。
uwsgi - 一个二进制协议，用于和 uWSGI（或者其他实现了 WSGI 规范的服务器）通信。nginx 在 0.8.40 版本通过
ngx_http_uwsgi_module带来了对 uwsgi 的支持。
完整的调用流程如下:
Tip
一个清除 Launch Screen 缓存的方法：
import UIKit
public extension UIApplication {
func clearLaunchScreenCache() {
do {
try FileManager.default.removeItem(atPath: NSHomeDirectory()+"/Library/SplashBoard")
} catch {
print("Failed to delete launch screen cache: \(error)")
}
}
}
来自：Quick tip: clearing your app’s launch screen cache on iOS
Share
今天重读了《分布式系统架构的冰与火》。
这篇文章回顾了分布式的发展历程，列出了分布式架构要解决的核心问题：
- 业务容量 - 单机内存条 128G，你的业务是否要将 128G 作为业务发展的上限
- 可用性 - 系统越大，组成部分就越多，是否要将整体系统的可用性押在各个服务的健壮性上
分布式技术的发展都要围绕这两个问题或其子问题来解决。这也是文中想表达的“纲”。