Given a sorted array of integers, find the starting and ending position of a given target value.

Your algorithm’s runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

Example

Given [5, 7, 7, 8, 8, 10] and target value 8,

return [3, 4].

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

• Integers in each row are sorted in ascending from left to right.
• Integers in each column are sorted in ascending from top to bottom.

Example

Consider the following matrix:

1
2
3
4
5
6
7

[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]

Given target = 5, return true.

Given target = 20, return false.

Determine whether an integer is a palindrome. Do this without extra space.

Some hints: * Could negative integers be palindromes? (ie, -1)

• If you are thinking of converting the integer to string, note the restriction of using extra space.

• You could also try reversing an integer. However, if you have solved the problem “Reverse Integer”, you know that the reversed integer might overflow. How would you handle such case?

• There is a more generic way of solving this problem.

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Example

Given [3,2,1,5,6,4] and k = 2, return 5.

Note:

You may assume k is always valid, 1 ≤ k ≤ array’s length.

Divide two integers without using multiplication, division and mod operator.

If it is overflow, return MAX_INT.

Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.

Example 1:

1
2
3
4
5

Input: k = 3, n = 7

Output:

[[1,2,4]]

Example 2:

1
2
3
4
5

Input: k = 3, n = 9

Output:

[[1,2,6], [1,3,5], [2,3,4]]

Given two words (beginWord and endWord), and a dictionary’s word list, find the length of shortest transformation sequence from beginWord to endWord, such that:

• Only one letter can be changed at a time
• Each intermediate word must exist in the word list

Example:

beginWord = “hit”

endWord = “cog”

wordList = [“hot”,“dot”,“dog”,“lot”,“log”]

As one shortest transformation is “hit” -> “hot” -> “dot” -> “dog” -> “cog”,

return its length 5.

Note:

• Return 0 if there is no such transformation sequence.
• All words have the same length.
• All words contain only lowercase alphabetic characters.

Given numRows, generate the first numRows of Pascal’s triangle.

For example, given numRows = 5, Return

1
2
3
4
5
6
7

[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]

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

Example:

1
2
3
4
5
6
7

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

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

Example:

Given [100, 4, 200, 1, 3, 2],

The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

Your algorithm should run in O(n) complexity.