Weekly #7

@Date : 2019-05-12 21:30:00

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

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

@Range : 2019/05/13 - 2019/05/19

Photo by Alfred Twj on Unsplash

Table of Contents

• algorithm
  • 728. Self Dividing Numbers
  • 561. Array Partition I
  • 852. Peak Index in a Mountain Array
  • 509. Fibonacci Number
  • 961. N-Repeated Element in Size 2N Array
  • 912. Sort an Array
• review
• tip
• share

algorithm

728. Self Dividing Numbers

A self-dividing number is a number that is divisible by every digit it contains.

For example, 128 is a self-dividing number because 128 % 1 == 0, 128 % 2 == 0, and 128 % 8 == 0.

Also, a self-dividing number is not allowed to contain the digit zero.

Given a lower and upper number bound, output a list of every possible self dividing number, including the bounds if possible.

Example 1:

Input: 
left = 1, right = 22
Output: [1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 15, 22]

Note:

• The boundaries of each input argument are 1 <= left <= right <= 10000.

Solution

Brute Force.

• Python

561. Array Partition I

Given an array of 2n integers, your task is to group these integers into n pairs of integer, say (a1, b1), (a2, b2), https://github.com/taseikyo/arts/blob/master., (an, bn) which makes sum of min(ai, bi) for all i from 1 to n as large as possible.

Example 1:

Input: [1,4,3,2]

Output: 4
Explanation: n is 2, and the maximum sum of pairs is 4 = min(1, 2) + min(3, 4).

Note:

• n is a positive integer, which is in the range of [1, 10000].
• All the integers in the array will be in the range of [-10000, 10000].

Solution

Sort the arr first and sum the even-index (0, 2, 4https://github.com/taseikyo/arts/blob/master.) item.

It's strange that return sum([sorted(nums)[i] for i in range(0, len(nums), 2)]) got Time Limit Exceeded error. But the following one was accepted and faster than 99.61%.

arr = sorted(nums)
return sum([arr[i] for i in range(0, len(nums), 2)])

• Python

852. Peak Index in a Mountain Array

Let's call an array A a mountain if the following properties hold:

• A.length >= 3
• There exists some 0 < i < A.length - 1 such that A[0] < A[1] < https://github.com/taseikyo/arts/blob/master. A[i-1] < A[i] > A[i+1] > https://github.com/taseikyo/arts/blob/master. > A[A.length - 1]
• Given an array that is definitely a mountain, return any i such that A[0] < A[1] < https://github.com/taseikyo/arts/blob/master. A[i-1] < A[i] > A[i+1] > https://github.com/taseikyo/arts/blob/master. > A[A.length - 1].

Example 1:

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

Example 2:

Input: [0,2,1,0]
Output: 1

Note:

• 3 <= A.length <= 10000
• 0 <= A[i] <= 10^6
• A is a mountain, as defined above.

Solution

Just Linear Scan or Binary Search.

• Python

509. Fibonacci Number

The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,

F(0) = 0,   F(1) = 1
F(N) = F(N - 1) + F(N - 2), for N > 1.

Given N, calculate F(N).

Example 1:

Input: 2
Output: 1
Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.
Example 2:

Input: 3
Output: 2
Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2.
Example 3:

Input: 4
Output: 3
Explanation: F(4) = F(3) + F(2) = 2 + 1 = 3.

Note:

• 0 ≤ N ≤ 30.

Solution

I thought sol.1 should be faster than sol.2; at lease sol.1 should consume less spacehttps://github.com/taseikyo/arts/blob/master.

# sol.1
def fib(self, N: int) -> int:
    '''48 ms    13.3 MB'''
    if N < 2:
        return N
    a, b = 0, 1
    for x in range(2, N+1):
        b, a = a+b, b
    return b

# sol.2
def fib(self, N: int) -> int:
    '''28 ms    13.1 MB'''
    tab = [0] * 31
    tab[0], tab[1] = 0, 1
    for x in range(2, N+1):
        tab[x] = tab[x-1] + tab[x-2]
    return tab[N]

• Python

961. N-Repeated Element in Size 2N Array

In a array A of size 2N, there are N+1 unique elements, and exactly one of these elements is repeated N times.

Return the element repeated N times.

Example 1:

Input: [1,2,3,3]
Output: 3
Example 2:

Input: [2,1,2,5,3,2]
Output: 2
Example 3:

Input: [5,1,5,2,5,3,5,4]
Output: 5

Note:

• 4 <= A.length <= 10000
• 0 <= A[i] < 10000
• A.length is even

Solution

• Python

912. Sort an Array

Given an array of integers nums, sort the array in ascending order.

Example 1:

Input: [5,2,3,1]
Output: [1,2,3,5]
Example 2:

Input: [5,1,1,2,0,0]
Output: [0,0,1,1,2,5]

Note:

• 1 <= A.length <= 10000
• -50000 <= A[i] <= 50000

Solution

quick sort is a great sorting method. I find an infinite loop problem (see tip #2).

• Python

review

• What is Conan? - Bincrafters - gitpage
• [Markdown] What is Conan? - Bincrafters - gitpage

The author introduces Conan to us, which is a package manager. Maybe it's similar to npm in nodejs and pip in Python.

tip

• Go Struct Anonymous Fields
• Quick Sort Infinite Loop Problem

share

• [TACO'19] Supporting Superpages and Lightweight Page Migration in Hybrid Memory Systems

Superpages are able to significantly improve TLB coverage and reduce address translation overhead. Hybrid memory systems composed of DRAM and NVM usually can provide very large memory capacity, and thus are more eager for the support of superpages.

However, superpages often preclude lightweight page migration, which is a key technique for improving performance and energy efficiency in hybrid memory systems.

This paper proposes a novel hybrid memory management mechanism named Rainbow to support both superpages and lightweight page migration.

Rainbow manages the NVM at the superpage granularity and uses the DRAM to cache frequently accessed (hot) small pages in the superpages. Correspondingly, Rainbow utilizes split TLBs to support different page sizes.

The author proposes an NVM-to-DRAM address remapping mechanism to identify the migrated small pages without splintering the superpages.