Interview Questions | Learn for Master - Part 6
• LeetCode move zeroes

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,

• Leetcode Invert Binary Tree

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,

• LeetCode Shortest Word Distance I II and III

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.

• Leetcode – 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.

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.

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,
• Leetcode – Wall and Gates

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,

• LeetCode － Flip Game

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,

• LeetCode – Flip Game II

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 “+–+”.

• Leetcode – Palindrome Permutation

Given a string, determine if a permutation of the string could form a palindrome.

For example, “code” -> False, “aab” -> True, “carerac” -> True.

Hint:

Consider the palindromes of odd vs even length. What difference do you notice? Count the frequency of each character. If each character occurs even number of times, then it must be a palindrome. How about character which occurs odd number of times?

Analysis

A native solution is to generate the permutation of the string, then check whether it is a palindrome.

A better solution is suggested from the above hint.

• LeetCode – Logger Rate Limiter

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”