Weekly #1
@Date : 2019/03/25 09:39:50
@Author : Lewis Tian (taseikyo@gmail.com)
@Link : https://taseikyo.github.io
@Range : 2019/03/25 - 2019/03/31
Table of Contents
algorithm
1. Two Sum
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
Solution
The simplest solution is brute force search, but the time complexity is \(O(n^2)\). In Python, to mitigate the time complexity, I use a dict to cache the difference of the current value for later use. But in C, I just use brute force search.
2. Add Two Numbers
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Example:
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.
Solution
Just keep track of carry and sum bit-by-bit from head to tail. Here is a fast algorithm:
head = new ListNode(0);
cur = head
while (l1 != null || l2 != null) {
x = l1 ? l1.val : 0;
y = l2 ? l2.val : 0;
sum = carry + x + y;
carry = sum / 10;
cur.next = new ListNode(sum % 10);
cur = cur.next;
if (l1) l1 = l1.next;
if (l2) l2 = l2.next;
}
if (carry > 0) {
cur.next = new ListNode(carry);
}
return head.next;
66. Plus One
Given a non-empty array of digits representing a non-negative integer, plus one to the integer.
The digits are stored such that the most significant digit is at the head of the list, and each element in the array contain a single digit.
You may assume the integer does not contain any leading zero, except the number 0 itself.
Example 1:
Input: [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.
Example 2:
Input: [4,3,2,1]
Output: [4,3,2,2]
Explanation: The array represents the integer 4321.
Solution
This problem is a bit like 2. Add Two Numbers.
771. Jewels and Stones
You're given strings J representing the types of stones that are jewels, and S representing the stones you have. Each character in S is a type of stone you have. You want to know how many of the stones you have are also jewels.
The letters in J are guaranteed distinct, and all characters in J and S are letters. Letters are case sensitive, so "a" is considered a different type of stone from "A".
Example 1:
Input: J = "aA", S = "aAAbbbb"
Output: 3
Example 2:
Input: J = "z", S = "ZZ"
Output: 0
- Note:
- S and J will consist of letters and have length at most 50.
- The characters in J are distinct.
Solution
This problem is quite easy in Python. Just one line can solve it.
return sum(S.count(i) for i in J)
709. To Lower Case
Implement function ToLowerCase() that has a string parameter str, and returns the same string in lowercase.
Example 1:
Input: "Hello"
Output: "hello"
Example 2:
Input: "here"
Output: "here"
Example 3:
Input: "LOVELY"
Output: "lovely"
Solution
Check whether each character is between 'A' and 'Z'.
595. Big Countries
There is a table World
+-----------------+------------+------------+--------------+---------------+
| name | continent | area | population | gdp |
+-----------------+------------+------------+--------------+---------------+
| Afghanistan | Asia | 652230 | 25500100 | 20343000 |
| Albania | Europe | 28748 | 2831741 | 12960000 |
| Algeria | Africa | 2381741 | 37100000 | 188681000 |
| Andorra | Europe | 468 | 78115 | 3712000 |
| Angola | Africa | 1246700 | 20609294 | 100990000 |
+-----------------+------------+------------+--------------+---------------+
A country is big if it has an area of bigger than 3 million square km or a population of more than 25 million.
Write a SQL solution to output big countries' name, population and area.
For example, according to the above table, we should output:
+--------------+-------------+--------------+
| name | population | area |
+--------------+-------------+--------------+
| Afghanistan | 25500100 | 652230 |
| Algeria | 37100000 | 2381741 |
+--------------+-------------+--------------+
Solution
617. Merge Two Binary Trees
Given two binary trees and imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not.
You need to merge them into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of new tree.
Example 1:
Input:
Tree 1 Tree 2
1 2
/ \ / \
3 2 1 3
/ \ \
5 4 7
Output:
Merged tree:
3
/ \
4 5
/ \ \
5 4 7
Note: The merging process must start from the root nodes of both trees.
Solution
977. Squares of a Sorted Array
Given an array of integers A sorted in non-decreasing order, return an array of the squares of each number, also in sorted non-decreasing order.
Example 1:
Input: [-4,-1,0,3,10]
Output: [0,1,9,16,100]
Example 2:
Input: [-7,-3,2,3,11]
Output: [4,9,9,49,121]
Note:
- 1 <= A.length <= 10000
- -10000 <= A[i] <= 10000
- A is sorted in non-decreasing order.
Solution
Split the array into two parts, negative and positive. Then iterate over the negative part in reverse, and the positive part in the forward direction.
review
This article mainly introduce Unikernel. Vineesh (the author) reviews the history of Library operating System and talks about the drawbacks of libOS. In the end, Vineesh compares Docker with Unikernel, and concludes that the advantages of Unikernels such as low boot time, security, and lightweight packaging will be in focus when enhancing containerized solutions and virtualizations in future.
tip
Use carbon to generate awesome code images.
share
- [ASPLOS'18] Making Huge Pages Actually Useful
This paper presents a method of using huge pages effectively, named Illuminator.
In Linux Buddy Allocator, there are two Pageblocks, Unmovable & Movable and hybrid pageblocks remain unknown to the allocator. As a result, majority of pageblocks will eventually become hybrid, both in Unmovable & Movable Pageblocks, leading to permanent fragmentation.
To address fragmentation-via-pollution, the author adds a Hybrid Pageblocks to store hybrid pageblocks. When memory becomes scarce, Linux compacts memory to provide huge page. Because hybrid pageblocks remain unknown to the Linux kernel, compacting hybrid pageblocks can be a waste of effort.
In Illuminator, kernel will skip Hybrid Pageblocks during compaction. Illuminator only compacts Moveable Pageblocks. Illuminator also reclaims pageblocks from the hybrid region when Hybrid Pageblock contains only movable (or free) pages.