Problem

The demons had captured the princess (P) and imprisoned her in the bottom-right corner of a dungeon. The dungeon consists of M x N rooms laid out in a 2D grid. Our valiant knight (K) was initially positioned in the top-left room and must fight his way through the dungeon to rescue the princess.

The knight has an initial health point represented by a positive integer. If at any point his health point drops to 0 or below, he dies immediately.

Some of the rooms are guarded by demons, so the knight loses health (negative integers) upon entering these rooms; other rooms are either empty (0’s) or contain magic orbs that increase the knight’s health (positive integers).

In order to reach the princess as quickly as possible, the knight decides to move only rightward or downward in each step.

Write a function to determine the knight’s minimum initial health so that he is able to rescue the princess.

For example, given the dungeon below, the initial health of the knight must be at least 7 if he follows the optimal path RIGHT-> RIGHT -> DOWN -> DOWN.

Note:

• The knight’s health has no upper bound.
• Any room can contain threats or power-ups, even the first room the knight enters and the bottom-right room where the princess is imprisoned.

Problem

Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.

Calling next() will return the next smallest number in the BST.

Example:

1
2
3
4
5
6
7
8
9
10

BSTIterator iterator = new BSTIterator(root);
iterator.next();    // return 3
iterator.next();    // return 7
iterator.hasNext(); // return true
iterator.next();    // return 9
iterator.hasNext(); // return true
iterator.next();    // return 15
iterator.hasNext(); // return true
iterator.next();    // return 20
iterator.hasNext(); // return false

Note:

• next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.
• You may assume that next() call will always be valid, that is, there will be at least a next smallest number in the BST when next() is called.

Problem

Given an integer n, return the number of trailing zeroes in n!.

Example 1:

1
2
3

Input: 3
Output: 0
Explanation: 3! = 6, no trailing zero.

Example 2:

1
2
3

Input: 5
Output: 1
Explanation: 5! = 120, one trailing zero.

Note: Your solution should be in logarithmic time complexity.

Problem

Given a column title as appear in an Excel sheet, return its corresponding column number.

For example:

1
2
3
4
5
6
7
8

    A -> 1
    B -> 2
    C -> 3
    ...
    Z -> 26
    AA -> 27
    AB -> 28
    ...

Example 1:

1
2

Input: "A"
Output: 1

Example 2:

1
2

Input: "AB"
Output: 28

Example 3:

1
2

Input: "ZY"
Output: 701

Problem

Design and implement a TwoSum class. It should support the following operations: add and find.

add - Add the number to an internal data structure.

find - Find if there exists any pair of numbers which sum is equal to the value.

Example 1:

1
2
3

add(1); add(3); add(5);
find(4) -> true
find(7) -> false

Example 2:

1
2
3

add(3); add(1); add(2);
find(3) -> true
find(6) -> false

Problem

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

Example 1:

1
2

Input: [3,2,3]
Output: 3

Example 2:

1
2

Input: [2,2,1,1,1,2,2]
Output: 2

Problem

Given a positive integer, return its corresponding column title as appear in an Excel sheet.

For example:

1
2
3
4
5
6
7
8

    1 -> A
    2 -> B
    3 -> C
    ...
    26 -> Z
    27 -> AA
    28 -> AB
    ...

Example 1:

1
2

Input: 1
Output: "A"

Example 2:

1
2

Input: 28
Output: "AB"

Example 3:

1
2

Input: 701
Output: "ZY"

Problem

Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2.

Note:

• Your returned answers (both index1 and index2) are not zero-based.
• You may assume that each input would have exactly one solution and you may not use the same element twice.

Example:

1
2
3

Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore index1 = 1, index2 = 2.

Problem

Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.

If the fractional part is repeating, enclose the repeating part in parentheses.

Example 1:

1
2

Input: numerator = 1, denominator = 2
Output: "0.5"

Example 2:

1
2

Input: numerator = 2, denominator = 1
Output: "2"

Example 3:

1
2

Input: numerator = 2, denominator = 3
Output: "0.(6)"

Problem

Compare two version numbers version1 and version2. If version1 > version2 return 1; if version1 < version2 return -1; otherwise return 0.

You may assume that the version strings are non-empty and contain only digits and the . character.

The . character does not represent a decimal point and is used to separate number sequences.

For instance, 2.5 is not “two and a half” or “half way to version three”, it is the fifth second-level revision of the second first-level revision.

You may assume the default revision number for each level of a version number to be 0. For example, version number 3.4 has a revision number of 3 and 4 for its first and second level revision number. Its third and fourth level revision number are both 0.

Example 1:

1
2

Input: version1 = "0.1", version2 = "1.1"
Output: -1

Example 2:

1
2

Input: version1 = "1.0.1", version2 = "1"
Output: 1

Example 3:

1
2

Input: version1 = "7.5.2.4", version2 = "7.5.3"
Output: -1

Example 4:

1
2
3

Input: version1 = "1.01", version2 = "1.001"
Output: 0
Explanation: Ignoring leading zeroes, both “01” and “001" represent the same number “1”

Example 5:

1
2
3

Input: version1 = "1.0", version2 = "1.0.0"
Output: 0
Explanation: The first version number does not have a third level revision number, which means its third level revision number is default to "0"

Note:

• Version strings are composed of numeric strings separated by dots . and this numeric strings may have leading zeroes.
• Version strings do not start or end with dots, and they will not be two consecutive dots.