23 Dec 2015
###Task1
You have two every large binary trees: T1, with millions of nodes, and T2, with hundreds of nodes. Create an algorithm to decide if T2 is a subtree of T1.
Have you met this question in a real interview? Yes
Example
T2 is a subtree of T1 in the following case:
1 3
/ \ /
T1 = 2 3 T2 = 4
/
4 T2 isn't a subtree of T1 in the following case:
1 3
/ \ \
T1 = 2 3 T2 = 4
/
4 Note
A tree T2 is a subtree of T1 if there exists a node n in T1 such that the subtree of n is identical to T2. That is, if you cut off the tree at node n, the two trees would be identical.
###java
/**
* Definition of TreeNode:
* public class TreeNode {
* public int val;
* public TreeNode left, right;
* public TreeNode(int val) {
* this.val = val;
* this.left = this.right = null;
* }
* }
*/
public class Solution {
/**
* @param T1, T2: The roots of binary tree.
* @return: True if T2 is a subtree of T1, or false.
*/
public boolean isSubtree(TreeNode T1, TreeNode T2) {
// write your code here
if (T2 == null) {
return true;
}
if (T1 == null) {
return false;
}
if (isSameTree(T1, T2)) {
return true;
}
if (isSubtree(T1.left, T2) || isSubtree(T1.right, T2)) {
return true;
}
return false;
}
public boolean isSameTree(TreeNode T1, TreeNode T2) {
if (T1 == null && T2 == null) {
return true;
}
if (T1 == null || T2 == null) {
return false;
}
if (T1.val != T2.val) {
return false;
}
return isSameTree(T1.left, T2.left) && isSameTree(T1.right, T2.right);
}
}
###Points
- isSubtree === one children of T1 is identical to T2
- Need extra function to determine isSameTree()
19 Dec 2015
###Task1
Given an integer array, adjust each integers so that the difference of every adjacent integers are not greater than a given number target.
| If the array before adjustment is A, the array after adjustment is B, you should minimize the sum of |
A[i]-B[i] |
Have you met this question in a real interview? Yes
Example
Given [1,4,2,3] and target = 1, one of the solutions is [2,3,2,3], the adjustment cost is 2 and it’s minimal.
Return 2.
Note
You can assume each number in the array is a positive integer and not greater than 100.
###Mark
19 Dec 2015
###Task1
Given n pieces of wood with length L[i] (integer array). Cut them into small pieces to guarantee you could have equal or more than k pieces with the same length. What is the longest length you can get from the n pieces of wood? Given L & k, return the maximum length of the small pieces.
Have you met this question in a real interview? Yes
Example
For L=[232, 124, 456], k=7, return 114.
Note
You couldn’t cut wood into float length.
Challenge
O(n log Len), where Len is the longest length of the wood.
###java
public class Solution {
/**
*@param L: Given n pieces of wood with length L[i]
*@param k: An integer
*return: The maximum length of the small pieces.
*/
public int woodCut(int[] L, int k) {
// write your code here
if (L == null || L.length == 0) {
return 0;
}
int max = 0;
for (int i = 0; i < L.length; i++) {
max = Math.max(max, L[i]);
}
int start = 1;
int end = max;
int mid;
while (start + 1 < end) {
mid = start + (end - start) / 2;
if (count(L, mid) >= k) {
start = mid;
} else {
end = mid;
}
}
if (count(L, end) >= k) {
return end;
} else if (count(L, start) >= k) {
return start;
}
return 0;
}
public int count(int[] L, int length) {
int count = 0;
for (int i = 0; i < L.length; i++) {
count += L[i] / length;
}
return count;
}
}
###Points
- Find the last length that make the number of cuts >= k;
- Initialize end to the max length of woods. why? We need keep the possibility of making it larger.
- To separate the count() function out!!!
19 Dec 2015
###Task1
Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You may assume NO duplicates in the array.
Have you met this question in a real interview? Yes
Example
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0
Challenge
O(log(n)) time
###java
public class Solution {
/**
* param A : an integer sorted array
* param target : an integer to be inserted
* return : an integer
*/
public int searchInsert(int[] A, int target) {
// write your code here
// find the first pos larger or equal to target
if (A == null || A.length == 0) {
return 0;
}
int start = 0;
int end = A.length - 1;
int mid;
while (start + 1 < end) {
mid = start + (end - start) / 2;
if (A[mid] >= target) {
end = mid;
} else {
start = mid;
}
}
if (A[start] >= target) {
return start;
} else if (A[end] >= target) {
return end;
}
return A.length;
}
}
###Points
- Find the first element >= target or the last element that <= target.
19 Dec 2015
###Task1
Sqrt(x) Show result
Implement int sqrt(int x).
Compute and return the square root of x.
Have you met this question in a real interview? Yes
Example
sqrt(3) = 1
sqrt(4) = 2
sqrt(5) = 2
sqrt(10) = 3
Challenge
O(log(x))
###Python
class Solution(object):
def mySqrt(self, x):
"""
:type x: int
:rtype: int
"""
l = 0
r = x
while l + 1 < r:
m = l + (r - l) / 2
if m * m <= x and (m + 1) * (m + 1) > x:
return m
elif m * m < x:
l = m
else:
r = m
if l * l == x:
return l
else:
return r
###Java (BETTER)
class Solution {
/**
* @param x: An integer
* @return: The sqrt of x
*/
public int sqrt(int x) {
// write your code here
if (x <= 0) {
return 0;
}
long start = 0;
long end = x;
long mid;
while (start + 1 < end) {
mid = start + (end - start) / 2;
if (mid * mid <= x) {
start = mid;
} else {
end = mid;
}
}
if (end * end <= x) {
return (int) end;
} else {
return (int) start;
}
}
}
###Points
- why long? mid * mid may overflow;
- What to find? the last element that ele * ele <= x;