Skip to content

Latest commit

 

History

History
88 lines (71 loc) · 3.9 KB

Leo-20180825.md

File metadata and controls

88 lines (71 loc) · 3.9 KB

Leo Lei | 雷雨

Aug 25, 2018

1. Leetcode

Sliding Window Maximum

Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Return the max sliding window.

Example:

Input: nums = [1,3,-1,-3,5,3,6,7], and k = 3
Output: [3,3,5,5,6,7] 
Explanation: 

Window position                Max
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

Analysis

The brute force solution is simple and straightforward: for each sliding window, get the max value with max() method. The time would be O(Nk).

However, there are lots of redundant computation in above approach: by sliding the window, only the tail and the head of the window are changed, thus the max value of the previous window (prev_max) already says a lot of things about the current window (curr_max): prev_max could potentially be the curr_max, as long as it's greater than the new member and is still in the window. In the case where prev_max is gone, we need to find a new max in current window. The question is how to perserve such information.

Since we want to know when prev_max is moving out of the window, we can store the index of the max value. Also, we want to find the next max value if prev_max is out, we can store all the indices of all candidates - in certain order. That's where a deque, or "double ended queue", shines - new candidates keep coming on one end while old max gets popped out on the other end.

Implementation

class Solution:
    def maxSlidingWindow(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        res = []
        dq = collections.deque()
        for i, num in enumerate(nums):
            # clean dq before add i
            while dq and nums[dq[-1]] < num:
                dq.pop()
            dq.append(i) 
            
            # remove the max_id when it's out of window
            # next item would be the new max_id
            if i - dq[0] == k:
                dq.popleft()
            
            if i >= k - 1:
                res.append(nums[dq[0]])
                
        return res

2. Article and comment

Network Security Protocols by K2E Security

SSL, SSH and IPSec - Swarthmore College, CS91 Computer Security, Fall 2016

key messages:

  1. SSH is working with application layer and used for replacing insecure apps such as telnet
  2. SSL/TLS is implemented at the top of transportation layer. It uses Public Key Infrastructure(PKI) which is computational intensive due to the overhead. It runs on top of TCP only. HTTPS = HTTP + SSL/TLS.

    A public key infrastructure (PKI) is a system for the creation, storage, and distribution of digital certificates which are used to verify that a particular public key belongs to a certain entity.

  3. IPSec runs at the networking layer. It doesn't rely on PKI and used mostly for larger corporations, e.g. IPSec VPN. It can secure TCP, UDP and SCTP

3. New skill/tool

  • Use [Grub 2] for managing dual boots: install Ubuntu Desktop 16.04 along with Windows 10.
  • Create bootable USB drives with Rufus

4. Share an article

None