Weekly #5

@Date : 2019-04-22 10:53:38

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

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

@Range : 2019/04/22 - 2019/04/30

Photo by Simon Abrams on Unsplash

Table of Contents

• algorithm
  • 701. Insert into a Binary Search Tree
  • 1008. Construct Binary Search Tree from Preorder Traversal
  • 832. Flipping an Image
  • 461. Hamming Distance
  • 338. Counting Bits
  • 104. Maximum Depth of Binary Tree
  • 739. Daily Temperatures
  • 136. Single Number
  • 226. Invert Binary Tree
  • 94. Binary Tree Inorder Traversal
  • 238. Product of Array Except Self
  • 206. Reverse Linked List
• review
• tip
• share

algorithm

701. Insert into a Binary Search Tree

Given the root node of a binary search tree (BST) and a value to be inserted into the tree, insert the value into the BST. Return the root node of the BST after the insertion. It is guaranteed that the new value does not exist in the original BST.

Note that there may exist multiple valid ways for the insertion, as long as the tree remains a BST after insertion. You can return any of them.

For example,

Given the tree:
        4
       / \
      2   7
     / \
    1   3
And the value to insert: 5

You can return this binary search tree:

         4
       /   \
      2     7
     / \   /
    1   3 5

This tree is also valid:

         5
       /   \
      2     7
     / \   
    1   3
         \
          4

Solution

Recursion:

if val > root.val:
    if root.right:
        self.insertIntoBST(root.right, val)
    else:
        root.right = TreeNode(val)
else:
    if root.left:
        self.insertIntoBST(root.left, val)
    else:
        root.left = TreeNode(val)
return root

• Python

1008. Construct Binary Search Tree from Preorder Traversal

Return the root node of a binary search tree that matches the given preorder traversal.

(Recall that a binary search tree is a binary tree where for every node, any descendant of node.left has a value < node.val, and any descendant of node.right has a value > node.val. Also recall that a preorder traversal displays the value of the node first, then traverses node.left, then traverses node.right.)

Example 1:

Input: [8,5,1,7,10,12]
Output: [8,5,10,1,7,null,12]

Note:

1. 1 <= preorder.length <= 100
2. The values of preorder are distinct.

Solution

Simple solution beats 100% time and 100% space:

root = TreeNode(preorder[0])
for x in preorder[1:]:
    p = root
    while p:
        if p.val > x:
            if p.left:
                p = p.left
            else:
                p.left = TreeNode(x)
                break
        else:
            if p.right:
                p = p.right
            else:
                p.right = TreeNode(x)
                break
return root

• Python

832. Flipping an Image

Given a binary matrix A, we want to flip the image horizontally, then invert it, and return the resulting image.

To flip an image horizontally means that each row of the image is reversed. For example, flipping [1, 1, 0] horizontally results in [0, 1, 1].

To invert an image means that each 0 is replaced by 1, and each 1 is replaced by 0. For example, inverting [0, 1, 1] results in [1, 0, 0].

Example 1:

Input: [[1,1,0],[1,0,1],[0,0,0]]
Output: [[1,0,0],[0,1,0],[1,1,1]]
Explanation: First reverse each row: [[0,1,1],[1,0,1],[0,0,0]].
Then, invert the image: [[1,0,0],[0,1,0],[1,1,1]]

Example 2:

Input: [[1,1,0,0],[1,0,0,1],[0,1,1,1],[1,0,1,0]]
Output: [[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]]
Explanation: First reverse each row: [[0,0,1,1],[1,0,0,1],[1,1,1,0],[0,1,0,1]].
Then invert the image: [[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]]

Notes:

1. 1 <= A.length = A[0].length <= 20
2. 0 <= A[i][j] <= 1

Solution

Flip and reverse in one line.

i, j = 0, len(row) - 1
while i < j:
   row[i], row[j] = 1 - row[j], 1 - row[i]

• Python

461. Hamming Distance

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Given two integers x and y, calculate the Hamming distance.

Note: 0 <= x, y < 2^31.

Example:

Input: x = 1, y = 4

Output: 2

Explanation:
1   (0 0 0 1)
4   (0 1 0 0)
       ¡ü   ¡ü

The above arrows point to positions where the corresponding bits are different.

Solution

One line in Python

def hammingDistance(self, x, y):
    return bin(x^y).count('1')

• Python

338. Counting Bits

Given a non negative integer number num. For every numbers i in the range 0 <= i <= num calculate the number of 1's in their binary representation and return them as an array.

Example 1:

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

Example 2:

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

Follow up:

• It is very easy to come up with a solution with run time O(n*sizeof(integer)). But can you do it in linear time O(n) /possibly in a single pass?
• Space complexity should be O(n).
• Can you do it like a boss? Do it without using any builtin function like __builtin_popcount in c++ or in any other language.

Solution

It's easy to solve this problem, eg [bin(i).count('1') for i in range(num+1)]. But the requirements are strict: without using any builtin function.

So I have to resort to the discussion area. Here is an awesome solution:

res = [0] * (num + 1)

for i in range(1, num + 1):
    if i & 1:
        res[i] = res[i >> 1] + 1
    else:
        res[i] = res[i >> 1]
return res

• Python

104. Maximum Depth of Binary Tree

Given a binary 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.

Note: A leaf is a node with no children.

Example:

Given binary tree [3,9,20,null,null,15,7],
    3
   / \
  9  20
    /  \
   15   7
return its depth = 3.

Solution

Recursion:

if not root: return 0
else: return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1

• Python

739. Daily Temperatures

Given a list of daily temperatures T, return a list such that, for each day in the input, tells you how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, put 0 instead.

For example, given the list of temperatures T = [73, 74, 75, 71, 69, 72, 76, 73], your output should be [1, 1, 4, 2, 1, 1, 0, 0].

Note: The length of temperatures will be in the range [1, 30000]. Each temperature will be an integer in the range [30, 100].

Solution

For a given x, if T[x+1] > T[x], the gap is 1. Otherwise, iterate from x+1 to the end to find the warmer index.

There is a trick. If T[i] > T[x], the i is the index (i.e gap is i - x); if ret[i] == 0, that means there is not warmer temperature i.e. gap is 0 (because T[i] <= T[x]).

The increment ret[i] skip the colder temperature.

def dailyTemperatures(self, T):
    '''296 ms  16.6 MB'''
    if not T: return []
    ret = [0] * len(T)
    for x in range(len(T)-2,-1,-1):
        if T[x] < T[x+1]:
            ret[x] = 1
        else:
            i = x + 1
            while True:
                if T[i] > T[x]:
                    ret[x] = i - x
                    break
                if ret[i] == 0:
                    ret[x] = 0
                    break
                i += ret[i]
    return ret

• Python

136. Single Number

Given a non-empty array of integers, every element appears twice except for one. Find that single one.

Note:

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Example 1:

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

Example 2:

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

Solution

Just use XOR.

for x in nums[1:]:
    nums[0] ^= x
return nums[0]

• Python

226. Invert Binary Tree

Invert a binary tree.

Example:

Input:

     4
   /   \
  2     7
 / \   / \
1   3 6   9

Output:

     4
   /   \
  7     2
 / \   / \
9   6 3   1

Trivia: This problem was inspired by this original tweet by Max Howell:

Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so f* off.

Solution

Recursion.

• Python

94. Binary Tree Inorder Traversal

Given a binary tree, return the inorder traversal of its nodes' values.

Example:

Input: [1,null,2,3]
   1
    \
     2
    /
   3
Output: [1,3,2]

Follow up: Recursive solution is trivial, could you do it iteratively?

Solution

Iterative solution:

node = root
stack = []
ans = []
while node or stack:
    if node:
        stack.append(node)
        node = node.left
    else:
        node = stack.pop()
        ans.append(node.val)
        node = node.right
return ans

• Python

238. Product of Array Except Self

Given an array nums of n integers where n > 1, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Example:

Input:  [1,2,3,4]
Output: [24,12,8,6]

Note: Please solve it without division and in O(n).

Follow up:

Could you solve it with constant space complexity? (The output array does not count as extra space for the purpose of space complexity analysis.)

Solution

An awesome solution from disscuss area)

def productExceptSelf(self, nums: List[int]) -> List[int]:
    '''108 ms   20.7 MB'''
    ans = [0] * len(nums)

    # forward pass
    p = 1
    for x in range(len(nums)):
        ans[x] = p
        p *= nums[x]

    # backward pass
    p = 1
    for x in reversed(range(len(nums))):
        ans[x] *= p
        p *= nums[x]

    return ans

forward pass: multiply the nums before it; backward pass: multiply the nums after it

• Python

206. Reverse Linked List

Reverse a singly linked list.

Example:

Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL

Follow up:

A linked list can be reversed either iteratively or recursively. Could you implement both?

Solution

• iteratively

p, q = None, head
while q:
    n = q.next
    q.next = p
    p, q = q, n
return p

• recursively

if not head or not head.next: return head
p = self.reverseList(head.next)
head.next.next = head
head.next = None

return p

• Python

review

• Why I Love Golang - Sagi Serge Nadir - medium
• [Markdown] Why I Love Golang - Sagi Serge Nadir - medium

tip

• Go enumeration, typedefine and typealias

• Python list loop

In Python row[~i] means row[-i-1] or row[len(row) - 1 - i], that is i-th value of the row, counting from the right.

share

• [ASPLOS'15] Supporting superpages in non-contiguous physical memory

Superpages are critical for workloads with large memory footprints. Traditional 2MB superpages are not suitable for memory with retired pages, because a superpage must be mapped to large contiguous physical memory.

This paper proposes gaptolerant sequential mapping (GTSM) to allow mapping a superpage to memory with retired pages. The authors propose GT-PDE which has a block selection bitmap to support GTSM. The authors also proposes P-GT-PDE, a variant of GT-PDE, which can reduce the size of the page table by 50%.

The evaluation shows that the performance of GT-PDE and P-GT-PDE is close to the ideal 2MB superpaging (i.e., with no retired pages). For large-footprint workloads, the 4MB-page GT-PDE achieves 96.8% of traditional 2MB superpaging, while tolerating memory faults.