Remove all elements from a linked list of integers that have value val.

Example
Given: 1 -> 2 -> 6 -> 3 -> 4 -> 5 -> 6, val = 6
Return: 1 -> 2 -> 3 -> 4 -> 5

Analysis

To solve this problem, we keep two pointers pre and cur when scanning the LinkedList. Once the current node’s value equals to the target value, we remove the cur node by set pre.next = cur.next;

To make the implementation easier,

Intersection of Two unsorted Arrays

Given two arrays, write a function to compute their intersection.

Example:
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2].

Note:

• Each element in the result must be unique.
• The result can be in any order.

Analysis

Since the two arrays are unsorted, we can use HashSet to solve the problem easily.

We can also solve the problem by first sorting the two arrays, and using the algorithm of finding intersection of two sorted arrays.

Given an array nums, write a function to move all 0‘s to the end of it while maintaining the relative order of the non-zero elements.

For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0].

Note:

1. You must do this in-place without making a copy of the array.
2. Minimize the total number of operations.

Analysis

We can use a pointer zeroIndex to always point to the index of the first 0. We scan the array, if we encounter a non-zero element,

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 given a m x n 2D grid initialized with these three possible values.

1. -1 - A wall or an obstacle.

2. 0 - A gate.

3. INF - Infinity means an empty room. We use the value 231 - 1 = 2147483647 to represent INF as you may assume that the distance to a gate is less than 2147483647. Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, it should be filled with INF.

For example,

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,

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 determine if the starting player can guarantee a win.

For example, given s = “++++”, return true. The starting player can guarantee a win by flipping the middle “++” to become “+-+”.

Follow up:
Derive your algorithm’s runtime complexity.