ChaoSXDemon
BAN USERGenerally, recursion is the more "intuitive" method to used to solve tree type problems. However, I personally believe that, if you can point out that recursion is cache unfriendly and sometimes wasteful of program stack, then you have an edge against other interviewees who did not point out this. Therefore, I think it is best that we DO NOT use recursion to solve this problem. Therefore, some key data structures to use would be the stack (for depth-first) and the queue (for breath-first). Let's take a look at this possible solution in Java:
Let's define the data structure:
public class BinaryTreeNode<T>
{
public T mData = null;
public BinaryTreeNode<T> mLeft = null;
public BinaryTreeNode<T> mRight = null;
}
The high-level description of our algorithm will be the following:
1. Find a node in the target tree that is the same
2. Once that's found, test systematically if all the target's nodes are the same as the other
3. If no such nodes are found, we do not have a sub-set
Let's define the equality test method:
private static boolean isSubTreeHelper(BinaryTreeNode a, BinaryTreeNode b)
{
if(a == b)
{
return true;
}
if(a == null || b == null)
{
return false;
}
LinkedList<BinaryTreeNode> a_queue = new LinkedList<BinaryTreeNode>();
LinkedList<BinaryTreeNode> b_queue = new LinkedList<BinaryTreeNode>();
a_queue.add(a);
b_queue.add(b);
while(a_queue.isEmpty() == false && b_queue.isEmpty() == false)
{
BinaryTreeNode a_node = a_queue.poll();
BinaryTreeNode b_node = b_queue.poll();
if(a_node.mData.equals(b_node.mData) == false)
{
return false;
}
if(a_node.mLeft != null)
{
a_queue.add(a_node.mLeft);
}
if(a_node.mRight != null)
{
a_queue.add(a_node.mRight);
}
if(b_node.mLeft != null)
{
b_queue.add(b_node.mLeft);
}
if(b_node.mRight != null)
{
b_queue.add(b_node.mRight);
}
}
return true;
}
The above method walks both tree in a breath-first left-to-right order to determine if each node are the same. If any nodes are different, false is returned. Note that the above method does not assume the two trees being compared must have the same depth. That is if either a or b finishes comparison and all the nodes that's been compared are the same, the method returns true regardless of b having any more nodes.
Given the above method, we can then write a method to find the first matching node and test at that node if there is an equality:
public static boolean isSubTree(BinaryTreeNode a, BinaryTreeNode b)
{
if(a == b)
{
return true;
}
if(a == null || b == null)
{
return false;
}
LinkedList<BinaryTreeNode> b_queue = new LinkedList<BinaryTreeNode>();
b_queue.add(b);
while(b_queue.isEmpty() == false)
{
BinaryTreeNode current_node = b_queue.poll();
if(current_node.mData.equals(a.mData) == true)
{
if(BinaryTree.isSubTreeHelper(a, current_node) == true)
{
return true;
}
}
if(current_node.mLeft != null)
{
b_queue.add(current_node.mLeft);
}
if(current_node.mRight != null)
{
b_queue.add(current_node.mRight);
}
}
return false;
}
Let's add a handy tree creation method that simply constructs a tree in a breath-first order from the given elements:
public static <T> BinaryTreeNode<T> createBinaryTree(T... elements)
{
if(elements == null)
{
return null;
}
LinkedList<BinaryTreeNode<T>> queue = new LinkedList<BinaryTreeNode<T>>();
BinaryTreeNode<T> root = new BinaryTreeNode<T>();
root.mData = elements[0];
int i = 1;
queue.add(root);
while(i < elements.length)
{
BinaryTreeNode<T> node = queue.poll();
node.mLeft = new BinaryTreeNode<T>();
node.mLeft.mData = elements[i++];
if(i >= elements.length)
{
break;
}
queue.add(node.mLeft);
node.mRight = new BinaryTreeNode<T>();
node.mRight.mData = elements[i++];
if(i >= elements.length)
{
break;
}
queue.add(node.mRight);
}
return root;
}
Here's the main test code:
public static void main(String[] args)
{
BinaryTreeNode<Integer> root = BinaryTree.createBinaryTree(1, 2);
root.mLeft.mRight = BinaryTree.createBinaryTree(2, 3, 4);
root.mLeft.mLeft = BinaryTree.createBinaryTree(5, 6);
root.mLeft.mRight.mLeft.mLeft = BinaryTree.createBinaryTree(7, 8, 9);
System.out.println("");
System.out.println(BinaryTree.isSubTree(BinaryTree.createBinaryTree(2, 3, 4), root));
}
Root looks like this:
1
/
/
2
/ \
5 2
/ / \
6 3 4
/
7
/ \
8 9
Please point out anything I left out! Thanks!
- ChaoSXDemon January 15, 2015A Power Set is defined as the set that includes all subsets. For example, say we have the following set: {0, 1, 2}. Subset of this set is: {}, {0}, {1}, {2}, {0, 1}, {0, 2}, {1, 2}, {0, 1, 2}. Now if we put all of these into a set, then this set is called the Power Set of {0, 1, 2}.
- ChaoSXDemon June 03, 2013The idea is simple:
Since both arrays are sorted, simply loop through until one of the array is finished. Take which ever is smaller (if we are making ascending order. If not, reverse this step and take the larger) and put it at the new larger list. Add remaining items if there is any left.
Code in Java:
public int[] merge(int[] a, int[] b){
int[] result = new int[a.length + b.length];
int i = 0, j = 0, k = 0;
while(j < a.length && k <b.length) result[i++] = a[j] < b[k] ? a[j++] : b[k++];
if(j < a.length) System.arraycopy(a, j, result, i, a.length - j);
else if(k <b.length) System.arraycopy(b, k, result, i, b.length - k);
return result
}
The idea here is to show you are using System.arraycopy() instead of simply assigning values from one array to another. Java's System.arraycopy() will use native faster memory copy function such as "memmove()".
- ChaoSXDemon June 01, 2013I agree with the trie or prefix tree. @Lucas, yes I believe it covers that case. Imagine you are scanning one row (or column) and you have say "abcdautomobilezzz" and when you start at the second 'a' and traverse down to 'o' which makes "auto", you can use a wordCount variable in your trie to indicate this is a word. The algorithm will continue if more char matches; in this case, "mobile" matches.
- ChaoSXDemon May 28, 2013Intuitively we use recursion to traverse a tree structure and that takes at most O(logN) stack space. Therefore, no matter what we do, we cannot achieve worse case of O(1) space complexity. Having said that, our best effort will enable us to only use O(logN) space instead of O(N), putting the entire Tree in a List with in-order traversal.
We can use a stack structure to keep track of which node we are currently visiting. By in-order traversal, we visit all the left nodes, then root, then right. Thus, we push all the left nodes to the stack, and next() returns the left most node on the stack. If there are none, return the root and push the right node onto the stack. We simply repeat till we printed everything.
Here's the structure of the tree node:
public class BinaryTreeNode<T> {
public T item;
public BinaryTreeNode<T> left;
public BinaryTreeNode<T> right;
public BinaryTreeNode(T item){
this.item = item;
left = null;
right = null;
}
}
Here's the iterator class:
import java.util.Stack;
public class InOrderIterator<T> {
private BinaryTreeNode<T> tree;
private Stack<BinaryTreeNode<T>> stack;
private boolean flag; //Indicates if we have added the left most node
public InOrderIterator(BinaryTreeNode<T> t){
tree = t;
stack = new Stack<BinaryTreeNode<T>>();
BinaryTreeNode<T> current = tree;
while(current != null){
stack.push(current);
current = current.left;
}
flag = true; //We have added all left most nodes
}
public boolean hasNext(){
return !stack.isEmpty();
}
public T next(){
BinaryTreeNode<T> current = stack.peek();
//Push all left nodes if there is any
if(!flag){
while(current.left != null) {
stack.push(current.left);
current = current.left;
flag = true; //We have now added all the left most nodes
}
//If both left == null, then we won't have any more left sub-trees to add
if(current.right == null) flag = true;
}
//At this point, there is no more left node from the top of the stack
current = stack.pop();
if(current.right != null) {
stack.push(current.right);
flag = false; //We may have more left sub-trees to add now that the right sub-tree is added
}
return current.item;
}
}
Here's a test code to test it out:
public class Test{
public static void main(String[] args){
BinaryTreeNode<Integer> tree = Tree.makeBalancedTree(new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11});
System.out.println();
InOrderIterator<Integer> itr = new InOrderIterator<Integer>(tree);
while(itr.hasNext()) System.out.print(itr.next() + " ");
}
public static BinaryTreeNode<Integer> makeBalancedTree(int[] array){
return addToTree(array, 0, array.length-1);
}
private static BinaryTreeNode<Integer> addToTree(int[] array, int start, int end){
if(end < start) return null;
int mid = (start+end)>>1;
BinaryTreeNode<Integer> n = new BinaryTreeNode<Integer>(new Integer(array[mid]));
n.left = addToTree(array, start, mid - 1);
n.right = addToTree(array, mid + 1, end);
return n;
}
}
The output is:
1 2 3 4 5 6 7 8 9 10 11
We can use the XOR swap to avoid using an extra variable. We increase start while decrease end at each loop. If start has reached end or less than end, then the reverse has completed. The reason it is < instead of = is because with an even number of elements such as:
"abcd"
start = a (or index 0)
end = d (or index 3)
If the terminating condition is start != end, then when start = 1 and end = 2, after the swap of "b" and "c", start = 2, and end = 1 which makes the statement start != end evaluates to true. This will actually undo the reverse.
There is one catch using XOR swap: what ever you are swapping cannot be at the same memory address. If you know that it's gonna use the same memory address, use a normal swap with a "temp" variable.
Here's code in C:
void reverse(char* start, char* end){
while(start < end){
*start ^= *end;
*end ^= *start;
*start ^= *end;
start++;
end--;
}
}
Edit: Here's some explanation for Jack:
As indicated by the question, we are required to find the answer in O(N) or better time. Thus, sorting is not an option since it takes O(nlogn) time for any comparison based sorting algorithm. Finally, the question hinted to use a binary search meaning to cut things in halves and try to find the first occurring "1".
Typically, a binary search starts by looking at the middle of an array (or the root if it's a binary search tree), and if the middle (or root) is smaller than the item we are looking for, we go right else we go left. By going either direction, we effectively skipped half of the original array (or tree). This operation is O(logn) which is better than O(N).
However, the input is not sorted and so not all items on the left of the middle is smaller than the middle. This means, not all zeros are on the left side of the middle and not all ones are on the right side. This means, without sorting, the worse case is O(N).
Since the question insist on using "binary search", we can try to skip half of the list at a time until we hit a "1" that is on the left most side.
Here's my code in Python (now with comments):
def findOneHelper(bString, start, end):
#we are on the left most side of the sub-array
if(start == end):
#check if this left most index is "1"
if(bString[start] == "1"):
return start;
return -1;
#calculate the middle index of the array. Note that >> 1 is the same as divide by 2
mid = start+((end-start)>>1);
#Keep going left until we have reached the base case (left most index)
t = findOneHelper(bString, start, mid);
if(t != -1):
#if an index is found, return that to indicate this is where the first "1"
return t;
#Check the right half
return findOneHelper(bString, mid+1, end);
def findOne(bString):
return findOneHelper(bString, 0, len(bString)-1);
The output for: 00001101000001010100000
>>> findOne("00001101000001010100000")
4
Test cases:
>>> findOne("000000000000000000000")
-1
>>> findOne("111111111111111111111")
0
Indeed as you pointed out that if an optimal solution cannot be divisible by the largest cake and k, k-1, ... 1, then my algorithm does not find the optimal solution. I thought about the log(n) part, but due to my calculate waste algorithm and the condition that if it return -1, my assignCake function will return the previous result, I had no way to tell the difference between if I had gone to far by cutting down half, or I have simply gone one step too far (thus previous result is correct).
How would you prove that there is always at least one cake that it has no waste?
The largest cake will contain (composed of) smaller cakes simple because it is larger. For example, {4, 4, 2}, 4 can be composed of 2+2. The algorithm divides the largest cake for everyone at first but as it progresses, it tries to divide less and less of the largest cake to everyone. During the last iteration, the largest cake will only be shared with one person. Keep in mind that we cannot mix cakes and so to minimize waste, we always want to share the max number of cake. The max number of cake being shared is always a ratio of the largest cake since a smaller number divide by the number of people will always be equal or less than the larger number divide by the number of people.
- ChaoSXDemon April 22, 2013No, take the above example of cakes {4, 4, 2}. The GCD is 2 and dividing all cakes by this volume yields 1.0 instead of 1.3333. Finally the (k-1)GCD_Vol is 5*1= 5.0 which is not 2.0 units of waste.
- ChaoSXDemon April 20, 2013GCD will give us no remainder, take the above example where cakes are {4, 4, 2}. Obviously the GCD is 2 since 4/2 = 2 and 2/2 = 1 and anything else will create remainders. But the optimal unit of cake is 1.3333333 and obviously that does not equal to 2. Finally (K-1)*GCD_Vol = 5*2 = 10 which is not 2.0 unit of wasted cake.
- ChaoSXDemon April 20, 20131. Sort the input cake from largest to smallest.
2. Starting at the number of input people, guess that each person gets cake[0] / k units
3. Check and verify given cake[0]/k units can be assigned to k people
4. If step 3 worked, decrease k by one and assign this bigger unit and repeat step 3
5. If during step 4 any check failed, revert to previous value and return the best result
The time complexity if O(kN) where k is number of people and N is the number of cakes. So if k = N or larger then it's basically O(N^2)
float calculateWaste(float* cakeUnits, int length, float piece, int k){
int peopleLeft = k;
float waste = 0;
for(int i=0; i<length; i++){
if(peopleLeft == 0){
waste += cakeUnits[i];
}else{
if(cakeUnits[i] < piece) return -1;
int maxPeople = (int)floor(cakeUnits[i]/piece);
maxPeople = maxPeople > peopleLeft ? peopleLeft : maxPeople;
waste += cakeUnits[i] - piece*maxPeople;
peopleLeft -= maxPeople;
}
}
return waste;
}
float* assignCake(float* cakeUnits, int length, int k){
float* result = new float[2];
int totalPeople = k;
result[0] = cakeUnits[0] / k;
result[1] = calculateWaste(cakeUnits, length, result[0], totalPeople);
float prevUnit = result[0];
float prevWaste = result[1];
while(result[1] > 0){
printf("Unit: %3.4f Wasted: %3.4f\n", result[0], result[1]);
k--;
prevUnit = result[0];
prevWaste = result[1];
result[0] = cakeUnits[0] / k;
result[1] = calculateWaste(cakeUnits, length, result[0], totalPeople);
}
result[0] = prevUnit;
result[1] = prevWaste;
return result;
}
int main(int argc, char** argv){
float cakes[] = {4, 4, 2};
int length = sizeof(cakes) / sizeof(cakes[0]);
float* result = assignCake(cakes, length, 6);
printf("%3.4f per person wasting %3.4f units\n", result[0], result[1]);
system("PAUSE");
return 0;
}
Outputs:
Unit: 0.6667 Wasted: 6.0000
Unit: 0.8000 Wasted: 5.2000
Unit: 1.0000 Wasted: 4.0000
Unit: 1.3333 Wasted: 2.0000
1.3333 per person wasting 2.0000 units
Press any key to continue . . .
Comparison based sorting algorithms has a lower bound of nlogn which is clearly not 3n/2 + c ops.
- ChaoSXDemon January 15, 2015