It's never too late to learn to be a master
Given two sorted arrays or lists, get their union and intersection.
For example, if the input arrays are:
int[] list1 = {1, 3, 4, 5, 6, 7}
int[] list2 = {2, 3, 5, 6}
Then the union is {1, 2, 3, 4, 5, 6, 7} and the Intersection is {3, 5, 6}.
Analysis
We can solve this problem using the same idea of merging sorted list.
Union of two sorted lists algorithm
define two index variables p1 and p2, initialized as 0
define List<Integer>
[Read More...]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:
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,
[Read More...]Invert a binary tree.
|
1 2 3 4 5 |
4 / \ 2 7 / \ / \ 1 3 6 9 |
to
|
1 2 3 4 5 |
4 / \ 7 2 / \ / \ 9 6 3 1 |
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,
[Read More...]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.
[Read More...]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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
//Definition for a binary tree node. class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } } class MaxDepth { public int maxDepth(TreeNode root) { if(root == null) return 0; int leftMaxDepth = maxDepth(root.left); int rightMaxDepth = maxDepth(root.right); return Math.max(leftMaxDepth, rightMaxDepth) + 1; } } |
https://leetcode.com/problems/maximum-depth-of-binary-tree/
[Read More...]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:
You are given a m x n 2D grid initialized with these three possible values.
-1 - A wall or an obstacle.
0 - A gate.
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,
[Read More...]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:
|
1 2 3 4 5 6 |
[ "--++", "+--+", "++--" ] |
If there is no valid move,
[Read More...]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.
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.
[Read More...]
Rss Feeds