Invert a binary tree.

to

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 fuck off.

Analysis

This problem can be solved by using both recursion and bread first traverse or Level order traverse.

We first invert the left tree and right tree, then put the inverted right tree as the left child,

Shortest Word Distance I

Given a list of words and two words word1 and word2, return the shortest distance between these two words in the list.

For example, Assume that words = [“practice”, “makes”, “perfect”, “coding”, “makes”].

Given word1 = “coding”, word2 = “practice”, return 3. Given word1 = “makes”, word2 = “coding”, return 1.

Note

You may assume that word1 does not equal to word2, and word1 and word2 are both in the list.

Analysis

We can scan the list and use two pointers to record the most recent indexes of the two words.

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.

Analysis:

This problem can be easily solved using a recursive algorithm. As

maxDepth(root) = max(maxDepth(root.left), maxDepth(root.right) + 1 if root != null;

and maxDepth(root) == 0 if root == null;

Java solution:

https://leetcode.com/problems/maximum-depth-of-binary-tree/

Given a non-negative integer num, repeatedly add all its digits until the result has only one digit.

For example:

Given num = 38, the process is like: 3 + 8 = 11, 1 + 1 = 2. Since 2 has only one digit, return it.

Follow up:
Could you do it without any loop/recursion in O(1) runtime?

Hint:

1. A naive implementation of the above process is trivial. Could you come up with other methods?
2. What are all the possible results?
3. How do they occur,

You are playing the following Flip Game with your friend: Given a string that contains only these two characters: + and -, you and your friend take turns to flip two consecutive “++” into “-“. The game ends when a person can no longer make a move and therefore the other person will be the winner.

Write a function to compute all possible states of the string after one valid move.

For example, given s = “++++”, after one move, it may become one of the following states:

If there is no valid move,

Design a logger system that receive stream of messages along with its timestamps, each message should be printed if and only if it is not printed in the last 10 seconds.

Given a message and a timestamp (in seconds granularity), return true if the message should be printed in the given timestamp, otherwise returns false.

It is possible that several messages arrive roughly at the same time.

Example:

Logger logger = new Logger();

// logging string “foo” at timestamp 1
logger.shouldPrintMessage(1, “foo”); returns true;

// logging string “bar”

Given a collection of distinct numbers, return all possible permutations.

For example,
[1,2,3] have the following permutations:

Analysis

I will use an example to illustrate how to generate all the permutation of an array.

Given a list [1, 2, 3, 4], all the permutations consists of the four sets:
the permutations starts with 1: {1} + {permutations of array [2, 3, 4]}
the permutations starts with 2,
the permutations starts with 3,
the permutations starts with 4,

Suppose we have a function called search to generate permutations for the subarray nums[start .. end].

Search for a Range

Given a sorted array of integers, find the starting and ending position of a given target value.

Your algorithm’s runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].

Analysis:

This problem is equivalent to find the lower bound and upper bound of the target value in the sorted array.

For instance, given a sorted array [1,

LeetCode - Remove Element

Given an array and a value, remove all instances of that value in place and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

The order of elements can be changed. It doesn’t matter what you leave beyond the new length.

Example:
Given input array nums = [3,2,2,3], val = 3

Your function should return length = 2, with the first two elements of nums being 2.

Analysis

This problem is similar to another leetcode problem: Remove Duplicates from Sorted Array.

Leetcode: Remove Duplicates from Sorted Array

Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

For example,
Given input array nums = [1,1,2],

Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn’t matter what you leave beyond the new length.

Analysis

We defined two indexes: pre and cur.