Weekly #3

@Date : 2019-04-08 10:19:05

@Author : Lewis Tian (taseikyo@gmail.com)

@Link : https://taseikyo.github.io

@Range : 2019/04/08 - 2019/04/14

Photo by Ian Matyssik on Unsplash

Table of Contents

• algorithm
  • 463. Island Perimeter
  • 344. Reverse String
  • 986. Interval List Intersections
  • 349. Intersection of Two Arrays
• review
• tip
• share

algorithm

463. Island Perimeter

You are given a map in form of a two-dimensional integer grid where 1 represents land and 0 represents water.

Grid cells are connected horizontally/vertically (not diagonally). The grid is completely surrounded by water, and there is exactly one island (i.e., one or more connected land cells).

The island doesn't have "lakes" (water inside that isn't connected to the water around the island). One cell is a square with side length 1. The grid is rectangular, width and height don't exceed 100. Determine the perimeter of the island.

Example:

Input:
[[0,1,0,0],
 [1,1,1,0],
 [0,1,0,0],
 [1,1,0,0]]

Output: 16

Explanation: The perimeter is the 16 yellow stripes in the image below:

Solution

Solving this problem is pretty simple, but how to reduce the time complexity is a little troublesome.

First, I defined a function to get the values of adjacent cells. But the runtime was not acceptable.

def getGrid(self, grid, x, y):
    X = len(grid)
    Y = len(grid[0])
    if x < 0 or x >= X:
        return 1
    if y < 0 or y >= Y:
        return 1
    return 1 - grid[x][y]

Later I got a solution, defaultdict. When an IndexError occurs, it will return a default value. Great, this is what I want.

d = defaultdict(int)
for i in range(len(grid)):
    for j in range(len(grid[0])):
        d[(i,j)] = grid[i][j]
if grid[x][y]==1:
    pm += 4 - (d[(x-1, y)] + d[(x+1, y)] \
        + d[(x, y+1)] + d[(x, y-1)])

There is an awesome solution, however it is a bit hard to understand.

• Python

344. Reverse String

Write a function that reverses a string. The input string is given as an array of characters char[].

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

You may assume all the characters consist of printable ascii characters.

Example 1:

Input: ["h","e","l","l","o"]
Output: ["o","l","l","e","h"]

Example 2:

Input: ["H","a","n","n","a","h"]
Output: ["h","a","n","n","a","H"]

Solution

• C

986. Interval List Intersections

Given two lists of closed intervals, each list of intervals is pairwise disjoint and in sorted order.

Return the intersection of these two interval lists.

(Formally, a closed interval [a, b] (with a <= b) denotes the set of real numbers x with a <= x <= b. The intersection of two closed intervals is a set of real numbers that is either empty, or can be represented as a closed interval. For example, the intersection of [1, 3] and [2, 4] is [2, 3].)

Example 1:

Input: A = [[0,2],[5,10],[13,23],[24,25]], B = [[1,5],[8,12],[15,24],[25,26]]
Output: [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]
Reminder: The inputs and the desired output are lists of Interval objects, and not arrays or lists.

Note:

1. 0 <= A.length < 1000
2. 0 <= B.length < 1000
3. 0 <= A[i].start, A[i].end, B[i].start, B[i].end < 10^9

Solution

My solution is very stupid; it's time complexity is unacceptable.

There is an awesome algorithm.

while i < len(A) and j < len(B):
    # Let's check if A[i] intersects B[j].
    # lo - the startpoint of the intersection
    # hi - the endpoint of the intersection
    lo = max(A[i].start, B[j].start)
    hi = min(A[i].end, B[j].end)
    if lo <= hi:
        ans.append(Interval(lo, hi))

    # Remove the interval with the smallest endpoint
    if A[i].end < B[j].end:
        i += 1
    else:
        j += 1

• Python

349. Intersection of Two Arrays

Given two arrays, write a function to compute their intersection.

Example 1:

Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2]

Example 2:

Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [9,4]

Note:

• Each element in the result must be unique.
• The result can be in any order.

Solution

First, convert the two arrays to set. Then find the intersection of the two sets.

def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
    '''40 ms    13.2 MB'''
    return list(set(nums1)-(set(nums1) - set(nums2)))

• Python

review

• How do hypervisors handle second-level address translation? - Stephen J. Bigelow - searchservervirtualization
• [Markdown] How do hypervisors handle second-level address translation? - Stephen J. Bigelow - searchservervirtualization

The author talks about second-level address translation in hypervisor-based virtualization system.

• Intel's implementation of second-level address translation is called extended page tables.
• AMD implements SLAT through rapid virtualization indexing, which is also dubbed nested page tables.

However some hypervisors, such as Hyper-V in Windows 8, abandon software-based memory virtualization and require hardware-assisted second-level address translation for normal operation.

tip

• python visualization using plotly_express

share

• [ASPLOS'17] Thermostat: Application-transparent page management for two-tiered main memory

This paper presents Thermostat, an application-transparent hugepage-aware mechanism to place pages in a dual technology hybrid memory system, while achieving both the cost advantages of two-tiered memory and performance advantages of transparent huge pages.

Thermostat mechanism comprises four components:

1. a sampling mechanism that randomly selects a subset of pages for access-rate monitoring
2. a monitoring mechanism that counts accesses to sampled pages while limiting maximum overhead
3. a classification policy to select pages to place in slow memory
4. a mechanism to monitor and detect mis-classified pages or behavior changes and migrate pages back to fast memory