Background

Python is a powerful and concise language and I believe one-liners can show its beauty and help people have a better understanding of its features, especially its built-in functions. For examples, it push you to use list comprehension, reduce(), map(), filter() and lambda function.

However, keep in mind that one-line is not the ultimate goal instead of readability and performance.

Please work on the puzzles before you click on “Solution”.

Problem 1

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

Input: [-4,-1,0,3,10]
Output: [0,1,9,16,100]

Side Notes

1. O(n), 2 pointers.

Problem 2

Write a function to multiply two positive integers a and b without using the * operator (or / operator). You can use addition, subtraction, and bit shifting.

Side Notes

1. Works for 32-bit integers.

Problem 3

We have a list of points on the plane. Find the K closest points to the origin (0, 0).

(Here, the distance between two points on a plane is the Euclidean distance.)

You may return the answer in any order. The answer is guaranteed to be unique (except for the order that it is in.)

Problem 4

Given N, calculate Fibonacci number F(N), starting from 0 and 1.

Problem 5

In an alien language, surprisingly they also use english lowercase letters, but possibly in a different order. The order of the alphabet is some permutation of lowercase letters.

Given a sequence of words written in the alien language, and the order of the alphabet, return true if and only if the given words are sorted lexicographically in this alien language.

Example

Input: words = ["hello","leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz"
Output: true

Problem 6

You are given an n x n 2D matrix representing an image.

Rotate the image by 90 degrees (clockwise).

Note

You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.

Problem 7

There is a list of sorted integers from 1 to n. Starting from left to right, remove the first number and every other number afterward until you reach the end of the list.

Repeat the previous step again, but this time from right to left, remove the right most number and every other number from the remaining numbers.

We keep repeating the steps again, alternating left to right and right to left, until a single number remains.

Find the last number that remains starting with a list of length n.

Example

Input:
n = 9,
1 2 3 4 5 6 7 8 9
2 4 6 8
2 6
6

Output:
6

Problem 8

Find the index of nth occurrence of substring b in string a.

Side Notes

1. If finding 4th of b in a is -1, then obviously the result of 5th should also be -1.
2. y is [0, 1, 2, 3, ...], increase 1 at a time, so it always increases slower than x (the indices), so y > x + 1 is equivalent to x == -1 and y != 0.