Problem

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Examples

1
2
3

Input: coins = [1, 2, 5], amount = 11
Output: 3 
Explanation: 11 = 5 + 5 + 1

1
2

Input: coins = [2], amount = 3
Output: -1

Problem

You are given coins of different denominations and a total amount of money. Write a function to compute the number of combinations that make up that amount. You may assume that you have infinite number of each kind of coin.

Examples

1
2
3
4
5
6
7

Input: amount = 5, coins = [1, 2, 5]
Output: 4
Explanation: there are four ways to make up the amount:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

1
2
3

Input: amount = 3, coins = [2]
Output: 0
Explanation: the amount of 3 cannot be made up just with coins of 2.

1
2

Input: amount = 10, coins = [10] 
Output: 1

Note

• 0 <= amount <= 5000
• 1 <= coin <= 5000
• the number of coins is less than 500
• the answer is guaranteed to fit into signed 32-bit integer

Problem

Given an input string, reverse the string word by word.

Example

1
2

Input: "the sky is blue",
Output: "blue is sky the".

Note

• A word is defined as a sequence of non-space characters.
• Input string may contain leading or trailing spaces. However, your reversed string should not contain leading or trailing spaces.
• You need to reduce multiple spaces between two words to a single space in the reversed string.

Problem

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

Example

Given the below binary tree and sum = 22,

1
2
3
4
5
6
7

      5
     / \
    4   8
   /   / \
  11  13  4
 /  \      \
7    2      1

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

Note

A leaf is a node with no children.

Program

Given a binary tree, return the postorder traversal of its nodes’ values.

Example

1
2
3
4
5
6
7
8

Input: [1,null,2,3]
   1
    \
     2
    /
   3

Output: [3,2,1]

Problem

Given a binary tree, return the preorder traversal of its nodes’ values.

Example

1
2
3
4
5
6
7
8

Input: [1,null,2,3]
   1
    \
     2
    /
   3

Output: [1,2,3]

Depth First Search

Preorder

• Basic recursive steps (Center => Center.left => Center.right)
  1. Check if the current node is empty or null.
  2. Display the data part of the root (or current node).
  3. Traverse the left subtree by recursively calling the pre-order function.
  4. Traverse the right subtree by recursively calling the pre-order function.

Inorder

• Basic recursive steps (Center.left => Center => Center.right)
  1. Check if the current node is empty or null.
  2. Traverse the left subtree by recursively calling the in-order function.
  3. Display the data part of the root (or current node).
  4. Traverse the right subtree by recursively calling the in-order function.
• In a binary search tree, in-order traversal retrieves data in sorted order.

Postorder

• Basic recursive steps (Center.left => Center.right => Center)
  1. Check if the current node is empty or null.
  2. Traverse the left subtree by recursively calling the post-order function.
  3. Traverse the right subtree by recursively calling the post-order function.
  4. Display the data part of the root (or current node).

Problem

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +, -, *, /. Each operand may be an integer or another expression.

Examples

1
2
3

Input: ["2", "1", "+", "3", "*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9

1
2
3

Input: ["4", "13", "5", "/", "+"]
Output: 6
Explanation: (4 + (13 / 5)) = 6

1
2
3
4
5
6
7
8
9
10

Input: ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]
Output: 22
Explanation: 
  ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

Boundary Conditions

• Will there be any divided by zero operation?
• Can the given RPN expression be wrong?
  • Not matched
  • Expression includes invalid characters

Solution

Method:

Time Complexity:

Space Complexity:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

class Solution:
    def evalRPN(self, tokens):
        """
        :type tokens: List[str]
        :rtype: int
        """
        if len(tokens) == 1:
            return int(tokens.pop())

        val = 0
        stack = []
        operators = set(['+', '-', '*', '/'])
        
        for token in tokens:
            if token not in operators:
                stack.append(token)
            else:
                l2 = int(stack.pop())
                l1 = int(stack.pop())
                if token == '+':
                    val = l1 + l2
                elif token == '-':
                    val = l1 - l2
                elif token == '*':
                    val = l1 * l2
                elif token == '/':
                    val = int(l1 / l2)

                stack.append(str(val))
        
        return val

or

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution:
    def evalRPN(self, tokens):
        """
        :type tokens: List[str]
        :rtype: int
        """
        stack = []
        operators = {'+': lambda x, y: x + y, \
                     '-': lambda x, y: x - y, \
                     '*': lambda x, y: x * y, \
                     '/': lambda x, y: int(x/y)}
        
        for token in tokens:
            if token not in operators:
                stack.append(token)
            else:
                l2 = int(stack.pop())
                l1 = int(stack.pop())
                val = operators[token](l1, l2)
                stack.append(str(val))
        
        return int(stack.pop())

List Methods[1] and its Basic Analyses[2]

append(): O(1)

extend(): O(k)

insert(): O(n)

remove(): O(n)

index(): O(n)

count(): O(n)

pop(): O(1)

reverse(): O(n)

sort(): O(n log n)

copy(): O(n)

clear(): O(n)