## Hamming Distance

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Given two integers x and y, calculate the Hamming distance.

Note:
0 ≤ x, y < 231.

Solution I:

class Solution(object):
def hammingDistance(self, x, y):
"""
:type x: int
:type y: int
:rtype: int
"""
str1 = bin(x)[2:]
str2 = bin(y)[2:]
len1 = len(str1)
len2 = len(str2)
num = abs(len1 - len2)
if len1 < len2:
str1 = '0' * num + str1
elif len2 < len1:
str2 = '0' * num + str2

res = 0
for i in range(0, len(str1)):
if str1[i] != str2[i]:
res += 1
return res

slt = Solution()
print(slt.hammingDistance(x=3, y=4))

Solution II:

class Solution(object):
def hammingDistance(self, x, y):
return bin(x ^ y).count('1')

via: http://zhangzhenyu.com.cn/, all copyright by Mr.zzy.

## FIZZ BUZZ

Write a program that outputs the string representation of numbers from 1 to n.

But for multiples of three it should output Fizz instead of the number and for the multiples of five output Buzz. For numbers which are multiples of both three and five output FizzBuzz.

Example:

Input:
n = 15

Output:
Return:
[
"1",
"2",
"Fizz",
"4",
"Buzz",
"Fizz",
"7",
"8",
"Fizz",
"Buzz",
"11",
"Fizz",
"13",
"14",
"FizzBuzz"
]

Solution Ⅰ:

class Solution(object):
def fizzBuzz(self, n):
"""
:type n: int
:rtype: List[str]
"""
self = []
for i in range(1, n+1):
if i % 15 == 0:
self.append('FizzBuzz')
elif i % 3 == 0:
self.append('Fizz')
elif i % 5 == 0:
self.append('Buzz')
else:
self.append(str(i))

return self

Solution Ⅱ:

class Solution(object):
def fizzBuzz(self, n):
"""
:type n: int
:rtype: List[str]
"""
self = []
for x in range(1, n+1):
self.append("Fizz"[x % 3 * 4:] + "Buzz"[x % 5 * 4:] or x)
return self

via: http://zhangzhenyu.com.cn/, all copyright by Mr.zzy.

## Programming not coding

Programming not coding

Russian Doll Envelopes

You have a number of envelopes with widths and heights given as a pair of integers (w, h). One envelope can fit into another if and only if both the width and height of one envelope is greater than the width and height of the other envelope.

What is the maximum number of envelopes can you Russian doll? (put one inside other)

Example:
Given envelopes = [[5,4],[6,4],[6,7],[2,3]], the maximum number of envelopes you can Russian doll is 3 ([2,3] => [5,4] => [6,7]).

Solution:

class Solution(object):
"""docstring for Solution"""
def maxEnvelopes(self, envelopes):
nums = sorted(envelopes,
cmp = lambda x,y: x - y if x != y else y - x)
size = len(nums)
dp = []
for x in range(size):
low, high = 0, len(dp) - 1
while low <= high:
mid = (low + high) / 2
if dp[mid] < nums[x]:
low = mid + 1
else:
high = mid - 1
if low < len(dp):
dp[low] = nums[x]
else:
dp.append(nums[x])
return len(dp)

## Path Sum II

Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum.

Solution:

/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector> pathSum(TreeNode* root, int sum) {
vector > collect;
vector solution;
if(root!=NULL)
GetPath(root, sum, 0, solution, collect);
return collect;
}

void GetPath(TreeNode* node, int sum, int cal, vector& solution, vector >& collect)  {
solution.push_back(node->val);
cal += node->val;
if(cal == sum && node->left == NULL && node->right == NULL)
{
collect.push_back(solution);
}
else
{
if(node->left != NULL)
{
GetPath(node->left, sum, cal, solution, collect);
}
if(node->right != NULL)
{
GetPath(node->right, sum, cal, solution, collect);
}
}
solution.pop_back();
cal -= node->val;
return;
}
};

Given two binary strings, return their sum (also a binary string).

For example,
a = "11"
b = "1"
Return "100".

Solution:

/*Split the whole step into two binary characters added and carry.
In fact all similar additions can be disassembled like this.*/
class Solution {
public:
string addBinary(string a, string b) {
string result = "";
int c = 0;
int i = a.size()-1;
int j = b.size()-1;

while(i>=0 || j>=0 || c==1)
{
c += i >= 0 ? a[i--] - '0' : 0;
c += j >= 0 ? b[j--] - '0' : 0;
result = char(c%2 + '0') + result;
c /= 2;
}
return result;
}
};

## Find Peak Element

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] = -∞.

For 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.

Solution:

class Solution {
public:
int findPeakElement(vector& num) {
int n = num.size();
if(n == 1)
{
return 0;
}

int start = 0;
int end = n - 1;
int mid = 0;

while(start <= end) { mid = start + (end - start) / 2; if((mid == 0 || num[mid] >= num[mid - 1]) && (mid == n - 1 || num[mid] >= num[mid + 1])) // mid is peak
{
return mid;
} else if(mid > 0 && num[mid-1] > num[mid]) // mid is left
{
end = mid - 1;
} else // mid is right
{
start = mid + 1;
}
}
return mid;
}
};

## Divide a number by 3

Divide a number by 3 without using *, /, +, -, % operators

===========================

This question has been asked in an Oracle interview.

How would you divide a number by 3 without using */+-%, operators?

The number may be signed or unsigned.

===========================

unsigned add(char const zero[], unsigned const x, unsigned const y) {
// this exploits that &foo[bar] == foo+bar if foo is of type char*
return (int)(uintptr_t)(&((&zero[x])[y]));
}

unsigned div_by(unsigned const x, unsigned const by) {
unsigned floor = 0;
for (unsigned cmp = 0, r = 0; cmp <= x;) {
floor = r;
}
return floor;
}

===========================

Using cloud computing 😀

Google Search: 30 divided by 3

INTERSETING…

## Product of Array Except Self

Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Solve it without division and in O(n).

For example, given [1,2,3,4], return [24,12,8,6].

Solution:

class Solution(object):
def productExceptSelf(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
# output[i] = (x0 * x1 * ... * xi-1) * (xi+1 * .... * xn-1)
size = len(nums)
output =  * size
left = 1
for x in range(size - 1):
left *= nums[x]
output[x + 1] *= left
right = 1
for x in range(size - 1, 0, -1):
right *= nums[x]
output[x - 1] *= right
return output

## Single Number

Q1: Given an array of integers, every element appears twice except for one. Find that single one.

Solution:

class Solution(object):
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
ans = nums
for i in range(1, len(nums)):
ans = ans ^ nums[i]
return ans