penny
BAN USERthough I think using a queue instead of vector, same idea, but seems simpler for understanding....: what do you guys think ? :)
int difference(Node* root)
{
if(!root)
return 0;
int closest = 0;
int furthest = 0;
queue<pair<Node*, int>> nodes;
nodes.push(pair<Node*, int>(root,0));
while(!nodes.empty()) {
pair<Node*, int> n=nodes.front();
nodes.pop();
if(!n.first->left&&!n.first->right) {
if(closest == 0) {
closest = n.second;
} else {
furthest = n.second;
}
} else {
if(n.first->left) {
nodes.push(pair<Node*,int>(n.first->left,n.second+1));
}
if(n.first->right) {
nodes.push(pair<Node*,int>(n.first->right,n.second+1));
}
}
}
return (furthest>closest)?(furthest-closest):0;
}
O(n) solution, non-recursion... the idea is similar as the first post above: the (i+1)th element is not included in the result if the sum till (i+1)th elem is less than the sum till ith element:
int maxSum(int* arr,int len)
{
int sum1=0;
int sum2=0;
for(int i=0;i<len-1;++i) {
int temp=sum2;
sum1+=arr[i];
sum2+=arr[i+1];
if(i!=len-2) {
sum2=sum1;
if(sum1>sum2) {
++i;
} else {
sum1=temp;
}
}
}
return (sum2>sum1)?sum2:sum1;
}
there could be better ways but BST definitely would work. Storing each node is O(logn), printing descending order is O(n), insert and delete are both O(logn);
pseudo code for store:
initialize counter to 0;
code for Tree Node struct/class (int data, Node* left, Node* right);
store(int val) //called each time a new integer comes in
{
if(counter<=n)
{
counter++;
insert new node with value val in the bst; //O(logn)
return;
}
find the node with smallest value in the bst (the left most node); //O(logn)
if(val greater than left most node's value)
{
delete left most node; //O(logn)
insert new node with value val; //O(logn)
}
else //do nothing, the new val is not in the top n;
}
PrintDescendingOrder(node* root) //like in-order traversal, but right first, then self, then left
{
PrintDescendingOrder(root->right);
print root's value;
PrintDescendingOrder(root->left);
}
insert and delete is the same as inserting and deleting a value in bst......
Used recursive approach,
int incrementOne(int* arr, int len,int curr)
{
if(arr[len-1]<9)
{
arr[len-1]++;
return 0;
}
if(curr==len-1)
{
arr[curr]=0;
return 1;
}
arr[curr]+=incrementOne(arr,len,curr+1);
if(arr[curr]<=9)
return 0;
arr[curr]-=10;
return 1;
}
void incrementOne(int* arr, int len)
{
int c=incrementOne(arr, len,0);
if(c==1)
{
for(int i=len;i>0;--i)
arr[i]=arr[i-1];
arr[0]=1;
len++;
}
for(int i=0;i<=len-1;++i)
cout<<arr[i];
cout<<endl;
}
#ifdef TEST_INCREONE
void main()
{
int arr[10]={2,7,8,9};
incrementOne(arr,4);
int arr1[10]={9,9,9,9};
incrementOne(arr1,4);
int arr2[10]={2,7,8,8};
incrementOne(arr2,4);
system("pause");
}
#endif
time O(logn), space O(1)
use numc in Node struct to denote how many children the node has:
struct Node
{
int data;
Node* left;
Node* right;
int numc;
};
Pseudo code:
Node* func(Node* curr)
{
return curr if its numc is 0
otherwise:
1/(numc+1) possibility return the curr;
//implement this by: int r=random(1, numc+1);
//if(r==numc+1) return curr;
numc/(numc+1) possibility: //else
{
return func(curr->left) if curr->right is NULL;
return func(curr->right) if curr->left is NULL;
otherwise:
left/(left+right) possibility return func(curr->left);
right/(left+right) possibility return func(curr->right);
// left=left subtree size = curr->left->numc+1; right is similar as left
}
}
//implement left/(left+right) possibility by: int r=random(1,left+right);
if(r>=1&&r<=left) //means left/(left+right) possibility.
{ //do something}
No, not all while in a while is O(n^2).... I wouldn't post it if it was :)
If you look closely, every K elements, I put them in a stack, then in the inside while loop, I pop them out and add them to the list. It is not n^2 because I do it only when counter==k. So every node is being operated twice, not n times, so the time is O(2n)=O(n)
is temporary buffer allowed?
I was thinking of a non recursive solution:
Node* reverseK(Node* h, int k)
{
if(h==NULL)
return NULL;
if(k<=1)
return h;
stack<int> nstack;
Node* h1=NULL;
Node* curr=NULL;
int counter=0;
while(h!=NULL)
{
nstack.push(h->value);
h=h->next;
counter++;
if(counter==k)
{
while(counter>0)
{
int temp=nstack.top();
nstack.pop();
counter--;
if(h1==NULL)
{
h1=new Node();
h1->value=temp;
curr=h1;
}
else
{
Node* n=new Node();
n->value=temp;
curr->next=n;
curr=n;
}
}
}
}
if(curr!=NULL)
curr->next=NULL;
return h1;
}
that works for all my test cases, and the time is O(n), just not sure if the temporary stack and new list is ok?
- penny May 31, 2012
Repjudydschultz1234, Android test engineer at Eterno Infotech Pvt Ltd
Spent a weekend researching weebles in Nigeria. My current pet project is developing strategies for how to break someone's ...
agree with @che 's explanation (in a revert way) and @lfenjoy9 's code!!!
- penny November 20, 2012