Ric
BAN USERA simple loop should find out all the answers. Question need to be clearified with interviewer here: How is each level filled? For example:
1. the very middle cup will be filled first and then filling two neighboor cups aftwards, or
2. for even level, filling middle two cup first, but for odd level, filling middle one cup first, or
3. other filling patterns
It will affect how to calculated to last level.
const int V = <value of V>;
const int v = <value of v>;
void code()
{
int level = 0; //level count
int numberOfCupFilled = 0;
int left = V; //leftover int he jar
int tmpSum;
while(true)
{
//the sum of each level
tmpSum = level*v;
if(tmpSum > left) //found the level here
{
numberOfCupFilled += left/v;
float percentage = (float)(left%v)/v;
cout << "the level not fully filled is " << level;
cout << "percentage is " << percentage;
cout << "number of cup filled is " << numberOfCupFilled;
break;
}
numberOfCupFilled += level;
left -= tmpSum;
level++;
}
}
We can combine an in-order traversal and post-order traversal together to solve this problem. It should be a O(n).
(1) Put a cursor to the very left and another one to the very right
(2) check the sum one by one,
(3) if sum == K, print it,
(4) if sum < K, left = left->next;
(5) if sum > k, right = right->next.
This is a very heavy question for phone interview. Maybe the interviewer just want to c if you can get a clue on how to find out this, or find out how many ways you can use to sort out this problem. It is too hard to do a perfect coding in that 20 min. I put some code together here, It is not tested, not in recursive style, but I put all sub-logic into functions to make sure it is easy to read.
The code uses two stacks to record backtracking steps, which consumes constant space as required.
/*
Given a binary search tree of n nodes, find two nodes whose sum is equal to a given number k in O(n) time and constant space
*/
Stack<treenode*> stackLeft = new Stack<treenode*> ();
Stack<treenode*> stackRight = new Stack<treenode*> ();
void PrintSum(treenode* root, int sum)
{
if(root == null)
return;
//clean up stacks
stackLeft.clear();
stackRight.clear();
//move left cursor to the very left
InitLeftStack(root);
treenode* left = GetNextLeft();
//move the right cursor to the very right
InitRightStack(root);
treenode* right = GetNextRight();
while(left != null && right != null && left != right)
{
int localSum = left->data + right->data;
if(localSum == sum)
{
cout << left->data << " " << right->data;
left = GetNextLeft();
}
else if(localSum < sum)
{
left = GetNextLeft();
}
else
{
right = GetNextRight();
}
}
}
void InitLeftStack(treenode *root)
{
treenode* cur = root;
while(true)
{
if(cur)
{
stackLeft->push(cur);
cur = cur->left;
}
else
break;
}
}
treenode* GetNextLeft()
{
if(stackLeft == null)
return null;
treenode* ret = stackLeft->pop();
InitLeftStack(ret->right);
return ret;
}
void InitRightStack(treenode *root)
{
treenode* cur = root;
while(true)
{
if(cur)
{
stackRight->push(cur);
cur = cur->right;
}
else
break;
}
}
treenode* GetNextRight()
{
if(stackRight == null)
return null;
treenode* ret = stackRight->pop();
InitRightStack(ret->left);
return ret;
}
(
- Ric February 19, 2012public void TraverseInOrder(treenode root)
{
Stack<treenode> stack = new Stack<treenode>();
treenode cur = root;
while(true)
{
if(cur != null)
{
stack.push(cur);
cur = cur.left;
}
else
{
if(stack.empty())
return;
cur = stack.pop();
//do your job here, print, eat or whatever
cur = cur.right();
}
}
}
/*
one unsorted array is given.Find out the index i and j ,j> i for which a[j] - a[i] is maximum.perform in linear time complexity
*/
bool findLargestDiff(int data[], int size, int &low, int &high)
{
int tmpLow = 0, tmpHigh = 1;
if(size < 2)
return false;
int low = 0, high = 1;
if(size == 2)
{
return true;
}
while(tmpLow < size - 1 && tmpHigh < size)
{
if(data[tmpLow] > data[tmpLow+1]) //we try to find the lowest point at first
{
tmpLow++;
if(tmpHigh <= tmpLow) tmpHigh = tmpLow + 1; //j > i is a requrement
if(data[tmpHigh] - data[tmpLow] > data[high] - data[low]) //cover {-10, -5, -3} scenario
{
low = tmpLow;
high = tmpHigh;
}
}
else //the next is biggest than the tmpLow
{
while(tmpHigh < size)
{
if(data[tmpHigh] > data[tmpLow])
{
if(data[tmpHigh] - data[tmpLow] > data[high] - data[low])
{
low = tmpLow;
high = tmpHigh;
}
tmpHigh++;
}
else //find a new low
{
tmpLow = tmpHigh;
tmpHigh++;
break;
}
}
}
}
return true;
}
As it is a sorted array, we don't need to create the 2nd array to do the job. What we need is two pointers, point from the start and the end of the array and moving towards each other. This can solve the problem in O(n).
Another way is to use binary search to locate the position for the 2nd pointer, which will have better performance.
Covering 1000 to binary, which is 11,1110,1000. The length of the result is 10. So 10 prisoners should be enough to cover 1000 barrels of wine.
- Ric February 22, 2012