The gray code is a binary numeral system where two successive values differ in only one bit.

Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.

Example

Given n = 2, return [0,1,3,2]. Its gray code sequence is:

1
2
3
4

00 - 0
01 - 1
11 - 3
10 - 2

Note:

For a given n, a gray code sequence is not uniquely defined.

For example, [0,2,3,1] is also a valid gray code sequence according to the above definition.

For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that.

A peak element is an element that is greater than its neighbors.

Given an input array where num[i] ≠ num[i+1], find a peak element and return its index.

The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.

You may imagine that num[-1] = num[n] = -∞.

Example

in array [1, 2, 3, 1], 3 is a peak element and your function should return the index number 2.

Note:

Your solution should be in logarithmic complexity.

Given a string array words, find the maximum value of length(word[i]) * length(word[j]) where the two words do not share common letters. You may assume that each word will contain only lower case letters. If no such two words exist, return 0.

Example 1:

Given [“abcw”, “baz”, “foo”, “bar”, “xtfn”, “abcdef”]

Return 16

The two words can be “abcw”, “xtfn”.

Example 2:

Given [“a”, “ab”, “abc”, “d”, “cd”, “bcd”, “abcd”]

Return 4

The two words can be “ab”, “cd”.

Example 3:

Given [“a”, “aa”, “aaa”, “aaaa”]

Return 0

No such pair of words.

There are N gas stations along a circular route, where the amount of gas at station i is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.

Return the starting gas station’s index if you can travel around the circuit once, otherwise return -1.

Note: The solution is guaranteed to be unique.

Remove all elements from a linked list of integers that have value val.

Example

• Given: 1 –> 2 –> 6 –> 3 –> 4 –> 5 –> 6, val = 6
• Return: 1 –> 2 –> 3 –> 4 –> 5

Given an array containing n distinct numbers taken from 0, 1, 2, …, n, find the one that is missing from the array.

Example

n nums = [0, 1, 3] return 2.

Note

Yourlgorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?

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

• Given numerator = 1, denominator = 2, return “0.5”.
• Given numerator = 2, denominator = 1, return “2”.
• Given numerator = 2, denominator = 3, return “0.(6)”.

Hint

• No scary math, just apply elementary math knowledge. Still remember how to perform a long division?
• Try a long division on 4/9, the repeating part is obvious. Now try 4/333. Do you see a pattern?
• Be wary of edge cases! List out as many test cases as you can think of and test your code thoroughly.

Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are +, - and *

Example 1

1
2
3
4
5

Input: "2-1-1".

((2-1)-1) = 0
(2-(1-1)) = 2
Output: [0, 2]

Example 2

1
2
3
4
5
6
7
8

Input: "2*3-4*5"

(2*(3-(4*5))) = -34
((2*3)-(4*5)) = -14
((2*(3-4))*5) = -10
(2*((3-4)*5)) = -10
(((2*3)-4)*5) = 10
Output: [-34, -14, -10, -10, 10]

Sort a linked list using insertion sort.

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Note

You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2. The number of elements initialized in nums1 and nums2 are m and n respectively.