说到Leetcode设计题，那种构造自己的数据结构的感觉非常快乐，尤其是用O(1)或者O(logn)时间复杂度实现其中方法的快乐更是难以言喻。这不连着两个夜晚AC了两道设计题，开心的一批，珍惜这最后的快乐吧。
1797. 设计一个验证系统

class AuthenticationManager

=begin
    :type time_to_live: Integer
=end
    def initialize(time_to_live)
      @h = {}
      @t = time_to_live
    end


=begin
    :type token_id: String
    :type current_time: Integer
    :rtype: Void
=end
    def generate(token_id, current_time)
      @h[token_id] = current_time
    end


=begin
    :type token_id: String
    :type current_time: Integer
    :rtype: Void
=end
    def renew(token_id, current_time)
      if @h.has_key?(token_id)
        if current_time - @h[token_id] < @t
          @h[token_id] = current_time
        else
          return nil
        end
      else
        return nil
      end
    end


=begin
    :type current_time: Integer
    :rtype: Integer
=end
    def count_unexpired_tokens(current_time)
      @h.keys.select {|it| current_time - @h[it] < @t}.length
    end


end

# Your AuthenticationManager object will be instantiated and called as such:
# obj = AuthenticationManager.new(time_to_live)
# obj.generate(token_id, current_time)
# obj.renew(token_id, current_time)
# param_3 = obj.count_unexpired_tokens(current_time)

981. 基于时间的键值存储

class TimeMap
    def initialize()
      @h = {}
    end


=begin
    :type key: String
    :type value: String
    :type timestamp: Integer
    :rtype: Void
=end
    def set(key, value, timestamp)
      if @h.has_key?(key)
        @h[key].push([value,timestamp])
      else
        @h[key] = [[value,timestamp]]
      end
    end


=begin
    :type key: String
    :type timestamp: Integer
    :rtype: String
=end
    def get(key, timestamp)
      unless @h.has_key?(key)
        return ""
      else
        n = @h[key].bsearch_index {|it| it[1] >= timestamp}
        if n == nil
          return @h[key][-1][0]
        elsif @h[key][n][1] == timestamp
          return @h[key][n][0]
        elsif n == 0 && @h[key][n][1] > timestamp
          return ""
        elsif n > 0 && @h[key][n][1] > timestamp
          return @h[key][n-1][0]
        end
      end
          
    end


end

# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap.new()
# obj.set(key, value, timestamp)
# param_2 = obj.get(key, timestamp)