Weekly #2

@Date : 2019-04-01 14:50:24

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

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

@Range : 2019/04/01 - 2019/04/07

Weekly #2 Photo by Mikhail Vasilyev on Unsplash

Table of Contents

algorithm

905. Sort Array By Parity

Easy

Given an array A of non-negative integers, return an array consisting of all the even elements of A, followed by all the odd elements of A.

You may return any answer array that satisfies this condition.

Example 1:

Input: [3,1,2,4]
Output: [2,4,3,1]
The outputs [4,2,3,1], [2,4,1,3], and [4,2,1,3] would also be accepted.

Note:

  1. 1 <= A.length <= 5000
  2. 0 <= A[i] <= 5000

Solution

There are several solutions. First, write all the even elements first, then write all the odd elements.

def sortArrayByParity1(self, A: List[int]) -> List[int]:
    '''68 ms    13.8 MB'''
    even = []
    odd = []
    for x in A:
        if x % 2:
            odd.append(x)
        else:
            even.append(x)
    return even + odd

def sortArrayByParity0(self, A: List[int]) -> List[int]:
    '''84 ms    13.8 MB'''
    even = [x for x in A if x % 2 == 0]
    odd = [x for x in A if x % 2]
    return even + odd

Second, in-place exchange. We'll maintain two pointers i and j.

Then, there are 4 cases for (A[i] % 2, A[j] % 2):

  1. If it is (0, 1), then everything is correct: i++ and j--.
  2. If it is (1, 0), we swap them so they are correct, then continue.
  3. If it is (0, 0), only the i place is correct, so we i++ and continue.
  4. If it is (1, 1), only the j place is correct, so we j-- and continue.
def sortArrayByParity(self, A: List[int]) -> List[int]:
    ''' 68 ms   13.8 MB'''
    i, j = 0, len(A) - 1
    while i < j:
        if A[i] % 2 > A[j] % 2:
            A[i], A[j] = A[j], A[i]

        if A[i] % 2 == 0:
            i += 1

        if A[j] % 2 == 1:
            j -= 1
    return A

1018. Binary Prefix Divisible By 5

Easy

Given an array A of 0s and 1s, consider N_i: the i-th subarray from A[0] to A[i] interpreted as a binary number (from most-significant-bit to least-significant-bit.)

Return a list of booleans answer, where answer[i] is true if and only if N_i is divisible by 5.

Example 1:

Input: [0,1,1]
Output: [true,false,false]
Explanation: 
The input numbers in binary are 0, 01, 011; which are 0, 1, and 3 in base-10.  Only the first number is divisible by 5, so answer[0] is true.

Example 2:

Input: [1,1,1]
Output: [false,false,false]

Solution

I do not think this problem is easy. My first attempt was Time Limit Exceeded and I have no idea how to mitigate the time complexity. Maybe the reason is I only did few leetcode problems.

I got the trick from the post. The solution is quite clever.

def prefixesDivBy5(self, A):
    '''100 ms   16.1 MB'''
    for i in range(1, len(A)):
        A[i] += A[i - 1] * 2 % 5
    return [a % 5 == 0 for a in A]

657. Robot Return to Origin

Easy

There is a robot starting at position (0, 0), the origin, on a 2D plane. Given a sequence of its moves, judge if this robot ends up at (0, 0) after it completes its moves.

The move sequence is represented by a string, and the character moves[i] represents its ith move. Valid moves are R (right), L (left), U (up), and D (down). If the robot returns to the origin after it finishes all of its moves, return true. Otherwise, return false.

Note: The way that the robot is "facing" is irrelevant. "R" will always make the robot move to the right once, "L" will always make it move left, etc. Also, assume that the magnitude of the robot's movement is the same for each move.

Example 1:

Input: "UD"
Output: true 
Explanation: The robot moves up once, and then down once. All moves have the same magnitude, so it ended up at the origin where it started. Therefore, we return true.

Solution

This problem is quite easy in Python where string has count method. In other languages, we can use a simple solution. Use x and y to indicate the position of the robot.

804. Unique Morse Code Words

Easy

International Morse Code defines a standard encoding where each letter is mapped to a series of dots and dashes, as follows: "a" maps to ".-", "b" maps to "-https://github.com/taseikyo/arts/blob/master.", "c" maps to "-.-.", and so on.

For convenience, the full table for the 26 letters of the English alphabet is given below:

[".-","-https://github.com/taseikyo/arts/blob/master.","-.-.","-https://github.com/taseikyo/arts/blob/master",".","https://github.com/taseikyo/arts/blob/master-.","--.","https://github.com/taseikyo/arts/blob/masterhttps://github.com/taseikyo/arts/blob/master","https://github.com/taseikyo/arts/blob/master",".---","-.-",".-https://github.com/taseikyo/arts/blob/master","--","-.","---",".--.","--.-",".-.","https://github.com/taseikyo/arts/blob/master.","-","https://github.com/taseikyo/arts/blob/master-","https://github.com/taseikyo/arts/blob/master.-",".--","-https://github.com/taseikyo/arts/blob/master-","-.--","--https://github.com/taseikyo/arts/blob/master"]

Now, given a list of words, each word can be written as a concatenation of the Morse code of each letter. For example, "cba" can be written as "-.-https://github.com/taseikyo/arts/blob/master--https://github.com/taseikyo/arts/blob/master.", (which is the concatenation "-.-." + "-https://github.com/taseikyo/arts/blob/master." + ".-"). We'll call such a concatenation, the transformation of a word.

Return the number of different transformations among all words we have.

Example:

Input: words = ["gin", "zen", "gig", "msg"]
Output: 2
Explanation: 
The transformation of each word is:
"gin" -> "--https://github.com/taseikyo/arts/blob/master.-."
"zen" -> "--https://github.com/taseikyo/arts/blob/master.-."
"gig" -> "--https://github.com/taseikyo/arts/blob/master.--."
"msg" -> "--https://github.com/taseikyo/arts/blob/master.--."

There are 2 different transformations, "--https://github.com/taseikyo/arts/blob/master.-." and "--https://github.com/taseikyo/arts/blob/master.--.".

Note:

  • The length of words will be at most 100.
  • Each words[i] will have length in range [1, 12].
  • words[i] will only consist of lowercase letters.

Solution

In python, use set to store the concatenation and return the number of the concatenation.

559. Maximum Depth of N-ary Tree

Easy

Given a n-ary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

For example, given a 3-ary tree:

559. Maximum Depth of N-ary Tree

We should return its max depth, which is 3.

Note:

  • The depth of the tree is at most 1000.
  • The total number of nodes is at most 5000.

Solution

Deep-first-search algorithm

985. Sum of Even Numbers After Queries

Easy

We have an array A of integers, and an array queries of queries.

For the i-th query val = queries[i][0], index = queries[i][1], we add val to A[index]. Then, the answer to the i-th query is the sum of the even values of A.

(Here, the given index = queries[i][1] is a 0-based index, and each query permanently modifies the array A.)

Return the answer to all queries. Your answer array should have answer[i] as the answer to the i-th query.

Example 1:

Input: A = [1,2,3,4], queries = [[1,0],[-3,1],[-4,0],[2,3]]
Output: [8,6,2,4]
Explanation: 
At the beginning, the array is [1,2,3,4].
After adding 1 to A[0], the array is [2,2,3,4], and the sum of even values is 2 + 2 + 4 = 8.
After adding -3 to A[1], the array is [2,-1,3,4], and the sum of even values is 2 + 4 = 6.
After adding -4 to A[0], the array is [-2,-1,3,4], and the sum of even values is -2 + 4 = 2.
After adding 2 to A[3], the array is [-2,-1,3,6], and the sum of even values is -2 + 6 = 4.

Note:

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

Solution

Maintain array sum.

S = sum(x for x in A if x % 2 == 0)
ans = []

for x, k in queries:
    if A[k] % 2 == 0: S -= A[k]
    A[k] += x
    if A[k] % 2 == 0: S += A[k]
    ans.append(S)

review

The author talks about Fuzzy Hash. She argues that fuzzy hash should be used in Security Operations Center (SOC) instead of hash.

Commonly used hash functions today are highly sensitive to bitwise changes. So it is highly time-consuming for malware detection. Nevertheless fuzzy hashing is a technique that's used to identify similarities in binary data, regardless of the slight changes between them.

And there are several leading types of Fuzzy Hashes:

  • Context Triggered Piecewise Hashing (CTPH)
  • Ssdeep
  • Sdhash
  • Imphash
  • Locality Sensitive Hashing (or LSH)
  • Virus Total

These algorythms have endless potential in improving and providing more solutions in information security field, which makes them a must-have in every SOC analyst's tool kit and assures you'll hear about it again in the future.

tip

There are several ways to loop vector, but I prefer the last one:

for (auto val : valList) {
    cout << val << endl;
}

share

  • [VEE'15] Proactively Breaking Large Pages to Improve Memory Overcommitment Performance in VMware ESXi

This paper proposes a new host large page management policy.

Basically, identifying 'cold' large pages and allow breaking them when host free memory is sufficient.

A new clear state is added to ESXi memory management where all large pages (including 'hot' large page; in high state only 'cold' one can broken) can be proactively broken.

The author implements a policy to adjust the clear state threshold based on the host memory consumption rate.

In the clear state, page sharing scan rate is adjusted using the proposed VM large page shareability estimator to efficiently reclaim memory through page sharing.

Overall, by sharing small pages earlier, the amount of memory that needs to be reclaimed through expensive ballooning or swapping later can be reduced.

results matching ""

    No results matching ""